BZOJ2555: SubString-白红宇

BZOJ2555: SubString

阅读量：4947 次

发布时间：2019-06-11

本文共 2885 字，大约阅读时间需要 9 分钟。

题解:　　建出SAM 用LCT维护Right集合即可

#include 
     
      const int MAXN=3e6+10;using namespace std;int key[MAXN],dis[MAXN],ch[MAXN][2],chl[MAXN][26],fa[MAXN];int pre[MAXN],sum[MAXN],sumx[MAXN];//sum xu sumx allbool rt[MAXN];int cnt,cur,root,mask;char s1[MAXN],s2[MAXN];void up(int x){sumx[x]=sumx[ch[x][0]]+sumx[ch[x][1]]+sum[x]+key[x];}void Treavel(int x){    if(x)    {        Treavel(ch[x][0]);        printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d key=%2d,sum=%2d,sumx=%2d\n",x,ch[x][0],ch[x][1],pre[x],key[x],sum[x],sumx[x]);        Treavel(ch[x][1]);    }}void debug(int rp){    printf("root:%d\n",rp);    Treavel(rp);}void read(int t){    scanf("%s",s2);    int i,l = strlen(s2);    for(i = 0 ; i < l ; i ++ ) t=(t*131+i)%l,swap(s2[i],s2[t]);}void newnode(int x,int vul){	key[x]=sumx[x]=vul;sum[x]=0;rt[x]=1;ch[x][0]=ch[x][1]=0;pre[x]=0;}void rotate(int x,int kind){	int y=pre[x];	ch[y][!kind]=ch[x][kind];pre[ch[x][kind]]=y;	if(rt[y])rt[x]=1,rt[y]=0;	else ch[pre[y]][ch[pre[y]][1]==y]=x;	pre[x]=pre[y];ch[x][kind]=y;pre[y]=x;	up(y);}void splay(int x){	while(!rt[x]){		if(rt[pre[x]])rotate(x,ch[pre[x]][0]==x);		else{			int y=pre[x];int kind=ch[pre[y]][0]==y;			if(ch[y][kind]==x)rotate(x,!kind),rotate(x,kind);			else rotate(y,kind),rotate(x,kind);		}	}	up(x);}void access(int x){	int y=0;	while(x){		splay(x);		if(ch[x][1])pre[ch[x][1]]=x,rt[ch[x][1]]=1,sum[x]+=sumx[ch[x][1]];		if(y)rt[y]=0,sum[x]-=sumx[y];		ch[x][1]=y;up(x);		y=x;x=pre[x];	}}void Link(int u,int v){	access(u);splay(u);	access(v);splay(v);	pre[u]=v;sum[v]+=sumx[u];up(v);}void destory(int u,int v){	access(u);splay(v);	ch[v][1]=0;pre[u]=0;rt[u]=1;up(v);}int querty(int x){	access(x);splay(x);	return sumx[x]-sumx[ch[x][0]];}void built(int x,int id){	int last=cur;cur=++cnt;int p=last;dis[cur]=id;newnode(cur,1);	for(;p&&!chl[p][x];p=fa[p])chl[p][x]=cur;	if(!p)fa[cur]=root,Link(cur,root);	else{		int q=chl[p][x];		if(dis[q]==dis[p]+1)fa[cur]=q,Link(cur,q);		else{			int nt=++cnt;dis[nt]=dis[p]+1;newnode(cnt,0);			memcpy(chl[nt],chl[q],sizeof(chl[q]));			destory(q,fa[q]);			fa[nt]=fa[q];Link(nt,fa[q]);fa[q]=fa[cur]=nt;Link(q,nt);Link(cur,nt);			for(;chl[p][x]==q;p=fa[p])chl[p][x]=nt;		}	}}int slove(){	read(mask);int temp=root;int len=strlen(s2);	for(int i=0;i