Submission #48086018

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 1e6+10,base=19260817,INF=1e9;
const ll base2=1145141,mod=1e9+9;

int n;
ull pw[MAXN],h[MAXN],rh[MAXN];
ll pw2[MAXN],h2[MAXN],rh2[MAXN];
string s;

int len[MAXN];

struct DSU{
	int fa[MAXN];
	void Init(){
		rep(i,1,n+1)fa[i]=i;
	}
	int find(int x){
		return (fa[x]==x)?(x):(fa[x]=find(fa[x]));
	}
	void merge(int x,int y){
		fa[x]=find(y);
	}
}dsu;

ll ans,buc[MAXN];

vector<int>o[MAXN];

int main(){
	ios::sync_with_stdio(false);

	cin>>s;n=s.length();s=" "+s;

	pw[0]=1;rep(i,1,n)pw[i]=pw[i-1]*base;
	pw2[0]=1;rep(i,1,n)pw2[i]=pw2[i-1]*base2%mod;
	rep(i,1,n)h[i]=h[i-1]*base+(s[i]-'a'+1);
	rep(i,1,n)h2[i]=(h2[i-1]*base2+(s[i]-'a'+1))%mod;
	per(i,n,1)rh[i]=rh[i+1]*base+(s[i]-'a'+1);
	per(i,n,1)rh2[i]=(rh2[i+1]*base2+(s[i]-'a'+1))%mod;

	dsu.Init();
	rep(i,1,n){
		int L=1,R=min(i-1,n-i),ret=0;
		while(L<=R){
			int mid=(L+R)>>1;
			ull H=h[i-1]-h[i-mid-1]*pw[mid],rH=rh[i+1]-rh[i+mid+1]*pw[mid];
			
			ll H2=h2[i-1]-h2[i-mid-1]*pw2[mid],rH2=rh2[i+1]-rh2[i+mid+1]*pw2[mid];
		
			H2=(H2%mod+mod)%mod;rH2=(rH2%mod+mod)%mod;

			if(H==rH && H2==rH2)ret=mid,L=mid+1;
			else R=mid-1;
		}	
		for(int p=dsu.find(i-ret);p<i;p=dsu.find(p)){
			dsu.merge(p,p+1);
			o[2*i-p].push_back(p);
		}
	}
	//
	ll sum=0;
	dsu.Init();
	rep(i,1,n){
		sort(o[i].begin(),o[i].end());
		buc[i]++;sum+=i;
		for(auto j:o[i])if(buc[j]){
			int k=dsu.find((i+j)/2);
			dsu.merge(j,k);
			sum+=buc[j]*(k-j);
			buc[k]+=buc[j];buc[j]=0;
		}
		ll val=1ll*(i+1)*i-sum;
		ans+=val;
	}

	//
	cout<<ans<<endl;
    return 0;
}

Submission Info

Judge Result