Substrings 2

C++14(g++5.4) 解法, 执行用时: 2785ms, 内存消耗: 181408K, 提交时间: 2019-07-22 10:12:00

#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 REP(i,n) for(int i=(0);i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> inline void read(T &x){
    int f=0;x=0;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
    if(f)x=-x;
}

const int bas=2333,mod=998244353;
const int N=50005,T=250;
const int B=T+5,M=N/T+5;
int id[N][M],pre[N][M],b[N][B],s[N][B];
int bel[N],st[N],a[N],rk[N],p[N],las[N];
int n,sz,cnt;

inline void upd(int k,int x,int v){
	int pos=bel[x],las=id[k][pos];
	id[k][pos]=++sz;
	REP(i,st[pos+1]-st[pos]){
		if(i+st[pos]==x)b[sz][i]=v;
		else b[sz][i]=b[las][i];
		s[sz][i]=b[sz][i];
		if(i)s[sz][i]=(s[sz][i]+(ll)s[sz][i-1]*bas)%mod;
	}
	rep(i,pos,cnt){
		int len=st[i+1]-st[i];
		pre[k][i]=((ll)pre[k][i-1]*p[len]
				 		+s[id[k][i]][len-1])%mod;
	}
}
inline int qry(int k,int x){
	int pos=bel[x],len=x-st[pos]+1;
	return ((ll)pre[k][pos-1]*p[len]+s[id[k][pos]][len-1])%mod;
}
inline int val(int k,int x){
	if(x>n)return -1;int pos=bel[x];
	return b[id[k][pos]][x-st[pos]];
}
inline int getlcp(int x,int y){
	int l=0,r=n-max(x,y)+1,m;
	while(l<r){
		m=(l+r+1)>>1;
		qry(x,x+m-1)==qry(y,y+m-1)?l=m:r=m-1;
	}
	return l;
}
inline int cmp(int x,int y){
	int t=getlcp(x,y);
	return val(x,x+t)<val(y,y+t);
}

int main(){
	p[0]=1;
	rep(i,1,N-5)p[i]=(ll)p[i-1]*bas%mod;
	for(;~scanf("%d",&n);){
		sz=0;
		rep(i,1,n){
			read(a[i]);
			rk[i]=i,las[i]=0;
		}
		cnt=(n-1)/T+1;
		rep(i,1,cnt)
			bel[st[i]=(i-1)*T+1]=i;
		st[cnt+1]=n+1;
		rep(i,1,n)
			if(!bel[i])bel[i]=bel[i-1];
		memset(id[n+1],0,sizeof id[n+1]);
		memset(pre[n+1],0,sizeof pre[n+1]);
		per(i,n,1){
			rep(j,1,cnt)id[i][j]=id[i+1][j],pre[i][j]=pre[i+1][j];
			if(las[a[i]]){
				int j=las[a[i]];
				upd(i,j,j-i);
			}
			las[a[i]]=i;
		}
		sort(rk+1,rk+n+1,cmp);
		int ans=(ll)n*(n+1)/2;
		rep(i,2,n)ans-=getlcp(rk[i-1],rk[i]);
		printf("%d\n",ans);
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 2359ms, 内存消耗: 239300K, 提交时间: 2019-07-18 23:03:14

#include<bits/stdc++.h>
#define rep(i,x,y) for(auto i=(x);i<=(y);++i)
#define dep(i,x,y) for(auto i=(x);i>=(y);--i)
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define pb push_back
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N=5e4+10;
const int M=300;
const ll mo=998244353;
const ll D=18113219;
const ll DL=181321;
ll pw[M],s[N][M],nw[N][M];int n,m,b[N],l[N],r[N];
inline bool cmp(int x,int y){
	rep(i,0,m)if(s[x][i]!=s[y][i]){
		rep(j,0,m){int p=m*i+j;
			if(x+p>n)return 1;
			if(y+p>n)return 0;
			int X=l[x+p]<x?0:l[x+p]-x+1;
			int Y=l[y+p]<y?0:l[y+p]-y+1;
			if(X<Y)return 1;
			if(X>Y)return 0;
		}
	}return 0;
}
void sol(){
	if(scanf("%d",&n)==EOF)exit(0);
	map<int,int>mp;m=sqrt(n)+1;
	rep(i,1,n){int x;
		scanf("%d",&x);
		if(mp[x])r[mp[x]]=i;
		l[i]=mp[x];r[i]=0;mp[x]=i;
	}
	rep(i,0,m)nw[n][i]=s[n][i]=0;
	s[n][0]=DL;
	dep(i,n-1,1){ll ls=DL;bool lf=0;
		rep(j,0,(n-i)/m){
			int p=i+(j+1)*m,c;
			nw[i][j]=(nw[i+1][j]*D+lf)%mo;lf=0;
			if(r[i]&&(r[i]-i)/m==j)(nw[i][j]+=pw[r[i]-(i+j*m)])%=mo;
			if(p<=n&&l[p]>i){
				lf=1;(nw[i][j]+=mo-pw[m])%=mo;
			}
			if(p<=n){
				if(l[p]<=i)c=DL;else c=DL+l[p]-i;
			}else c=0;
			s[i][j]=(s[i+1][j]*D+mo-c*pw[m]%mo+ls+nw[i][j])%mo;ls=c;
		}
	}
	rep(i,1,n)b[i]=i;
	sort(b+1,b+n+1,cmp);
	ll ans=n-b[1]+1;
	rep(i,2,n){int lcp=0;
		rep(j,0,m)if(s[b[i-1]][j]!=s[b[i]][j]){
			rep(k,0,m){int p=m*j+k;
				if(max(b[i-1],b[i])+p>n||
				(l[b[i-1]+p]<b[i-1]?0:l[b[i-1]+p]-b[i-1]+1)
				!=(l[b[i]+p]<b[i]?0:l[b[i]+p]-b[i]+1))break;
				++lcp;
			}break;
		}else lcp+=m;
		ans+=n-b[i]-lcp+1;
	}
	printf("%lld\n",ans);
}
int main(){pw[0]=1;
	rep(i,1,M-1)pw[i]=pw[i-1]*D%mo;
	for(;;)sol();
}

详情