反正投不了了,随便写写(其实这是卡常记录)
算法
查给定字符串的出现次数常用 SAM,就是查 SAM 对应节点的 parent 树子树里有多少个主链上的节点,向后加字符串可以直接记录节点时间戳等实现。
但是这题有强制在线,所以要支持的操作就是在 parent 树上加点和更换父节点,查询子树和,显然可用 LCT,但也可以用平衡树维护 dfs 序实现,更换父节点即区间平移。
我写了个 fhqTreap,发现用它做这个常数比 LCT 还大,开 O2 都只有45pts。
考虑优化常数,对于新建节点原本是先直接并在 dfs 序的最后,找到父节点时再插到对应区间。于是新建节点时暂不加进平衡树,找到父节点了才直接加到父节点后面,于是就不开 O2 最劣解卡过了。
code
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<set>
#include<map>
#include<stdlib.h>
#include<time.h>
using namespace std;
#define re register
typedef long long ll;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline void cmax(int &x,int y){if(x<y) x=y;}
inline void cmin(int &x,int y){if(x>y) x=y;}
inline void swp(int &x,int &y){x^=y^=x^=y;}
const int N=1200050;
int tot,la,ch[N][2],ml[N],fa[N],rt,ls[N<<1],rs[N<<1],pr[N<<1],sz[N<<1],sm[N<<1],v[N<<1],ff[N<<1];
char ss[N];
inline void mt(int &x){sz[x]=sz[ls[x]]+sz[rs[x]]+1,sm[x]=sm[ls[x]]+sm[rs[x]]+v[x],ff[ls[x]]=ff[rs[x]]=x,ff[x]=0;}
inline int merge(int x,int y){
if(!x||!y) return x|y;
if(pr[x]<pr[y]) return rs[x]=merge(rs[x],y),mt(x),x;
return ls[y]=merge(x,ls[y]),mt(y),y;
}
inline void split(int x,int k,int &a,int &b){
if(!x) return a=b=0,void();
if(sz[ls[x]]>=k) b=x,split(ls[x],k,a,ls[x]);
else a=x,split(rs[x],k-sz[ls[x]]-1,rs[x],b);
mt(x);
}
inline int rk(int x){
int s=sz[ls[x]]+1;
for(;x;x=ff[x]) if(x==rs[ff[x]]) s+=sz[ls[ff[x]]]+1;
return s;
}
inline int xl(int &x){return (x<<1)-1;}
inline int xr(int &x){return x<<1;}
inline void newf(int x,int y,int ssm){
fa[x]=y,sz[xl(x)]=sz[xr(x)]=1,sm[xl(x)]=v[xl(x)]=ssm,
pr[xl(x)]=rand(),pr[xr(x)]=rand();
int a=merge(xl(x),xr(x)),b;split(rt,rk(xl(y)),rt,b);
rt=merge(merge(rt,a),b);
}
inline void chf(int x,int y){
fa[x]=y;int a,b;
split(rt,rk(xr(x)),rt,b),split(rt,rk(xl(x))-1,rt,a),
rt=merge(rt,b),split(rt,rk(xl(y)),rt,b),rt=merge(merge(rt,a),b);
}
inline void qry(int x,int &mask){
if(x){
int a,b;
split(rt,rk(xr(x)),rt,b),split(rt,rk(xl(x))-1,rt,a),
printf("%d\n",sm[a]),mask^=sm[a],rt=merge(merge(rt,a),b);
}
else putchar('0'),putchar('\n');
}
inline void build(int c){
int p=la,x=++tot,q;ml[x]=ml[la]+1,la=x;
while(!ch[p][c]&&p) ch[p][c]=x,p=fa[p];
if(!p) return newf(x,1,1),void();
if(ml[q=ch[p][c]]==ml[p]+1) return newf(x,q,1),void();
newf(++tot,fa[q],0),newf(x,tot,1),chf(q,tot),ml[tot]=ml[p]+1,
ch[tot][0]=ch[q][0],ch[tot][1]=ch[q][1];
while(ch[p][c]==q&&p) ch[p][c]=tot,p=fa[p];
}
inline int walk(char *s,int n){int x=1;for(re int i=0;i<n;++i) x=ch[x][s[i]-'A'];return x;}
inline int inputs(char *s,int mask){
scanf("%s",s);int n=strlen(s);
for(re int j=0;j<n;++j) mask=(mask*131+j)%n,swap(s[mask],s[j]);
return n;
}
signed main(){
srand(time(0));
int T,mask=0,n;char kd[7];
scanf("%d%s",&T,ss);
la=tot=1,sz[1]=sz[2]=0,pr[1]=rand(),pr[2]=rand(),rt=merge(1,2);
for(re int i=0,l=strlen(ss);i<l;++i) build(ss[i]-'A');
while(T--){
scanf("%s",kd);
if(kd[0]=='A') for(re int i=0,l=inputs(ss,mask);i<l;++i) build(ss[i]-'A');
else n=inputs(ss,mask),qry(walk(ss,n),mask);
}
return 0;
}