郑州网站开发公司名称大全,电商网站建,成都网络推广,辽宁省建设科学研究院网站解析
所谓SAM套LCT#xff0c;真的就只是SAM套LCT。。。
考试写起来应该有亿点点恶心
每次在SAM节点修改的时候在LCT对应位置修改即可。 注意#xff01; 克隆节点之前需要先splay一下把所有标记接收。 没了。
#includebits/stdc.h
using namespace std;
#define…解析
所谓SAM套LCT真的就只是SAM套LCT。。。
考试写起来应该有亿点点恶心
每次在SAM节点修改的时候在LCT对应位置修改即可。 注意 克隆节点之前需要先splay一下把所有标记接收。 没了。
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N3e6100;
const int M1e6100;
const int mod1e9;
int clo;struct SAM;struct LCT{int tr[N][2],f[N],val[N],rev[N],add[N];#define ls(o) tr[o][0]#define rs(o) tr[o][1]inline bool isroot(int x){return ls(f[x])!xrs(f[x])!x;}inline bool which(int x){return tr[f[x]][1]x;}inline void Rev(int x){if(x){rev[x]^1;swap(ls(x),rs(x));}return;}inline void Add(int x,int w){if(x){val[x]w;add[x]w;}return;}inline void pushdown(int x){if(rev[x]){rev[x]0;Rev(ls(x));Rev(rs(x));}if(add[x]){int wadd[x];add[x]0;Add(ls(x),w);Add(rs(x),w);}return;}inline void rotate(int x){int faf[x],gfaf[fa];int dwhich(x),sontr[x][d^1];pushdown(gfa);pushdown(fa);pushdown(x);f[x]gfa;if(!isroot(fa)) tr[gfa][which(fa)]x;f[fa]x;tr[x][d^1]fa;if(son){f[son]fa;}tr[fa][d]son;}int zhan[N];inline void splay(int x){int yx,top0;zhan[top]y;while(!isroot(y)) zhan[top]yf[y];while(top) pushdown(zhan[top--]);for(int fa;faf[x],!isroot(x);rotate(x)){if(!isroot(fa)) which(fa)which(x)?rotate(fa):rotate(x);}return;}inline void access(int x){for(int y(0);x;yx,xf[x]){splay(x);tr[x][1]y;if(y) f[y]x;}return;}inline void makeroot(int x){access(x);splay(x);Rev(x);return;}inline int findroot(int x){access(x);splay(x);while(pushdown(x),tr[x][0]) xtr[x][0];return x;}inline void split(int x,int y){makeroot(x);access(y);splay(y);return;}inline void link(int x,int y){//printf(link: %d - %d\n,x,y);makeroot(x);makeroot(y);if(findroot(x)findroot(y)){assert(0);printf(!!\n);return;}f[x]y;}inline void cut(int x,int y){//printf(cut: %d - %d\n,x,y);split(x,y);if(tr[y][0]!x||tr[x][1]){assert(0);printf(??\n);return;}tr[y][0]0;f[x]0;return;}void newnode(int x,int f,int c1){link(x,f);split(1,x);Add(x,c);return;}void print(int x){if(!x) return;printf(x%d fa%d ls%d rs%d val%d rev%d add%d\n,x,f[x],ls(x),rs(x),val[x],rev[x],add[x]);print(ls(x));print(rs(x));}void Debug(){printf(---debug:\n);for(int i1;iclo;i){if(isroot(i)) print(i);}putchar(\n);}
}lct;struct SAM{int len[N],fa[N],tr[N][2],tot,lst;SAM(){totlst1;}void ins(int c){c-A; int curtot,plst;lsttot;len[cur]len[p]1;//printf(\n---ins: %d\n,c);for(;p!tr[p][c];pfa[p]) tr[p][c]cur;if(!tr[p][c]) fa[cur]1;else{int qtr[p][c];if(len[q]len[p]1) fa[cur]q;else{int nqtot;len[nq]len[p]1;fa[nq]fa[q];for(int i0;i2;i) tr[nq][i]tr[q][i];lct.splay(q);lct.val[nq]lct.val[q];lct.cut(q,fa[q]);lct.link(nq,fa[q]);lct.link(q,nq); fa[q]fa[cur]nq;for(;ptr[p][c]q;pfa[p]) tr[p][c]nq;//printf( clone(%d) %d len%d\n,q,nq,len[nq]);}}clotot;lct.newnode(cur,fa[cur]);//lct.Debug();return;}int work(char *s,int n){int now1;for(int i1;in;i){int cs[i]-A;//printf(now%d c%d tr%d\n,now,c,tr[now][c]);if(!tr[now][c]){//printf(!);return 0;}nowtr[now][c];}//printf(now%d\n,now);lct.splay(now);return lct.val[now];}
}sam;
int n,m;
char s[N],op[12],s0[N];
void get(int msk){for(int i0;in;i) s0[i]s[i1];for(int i0;in;i){msk(msk*131i)%n;swap(s0[i],s0[msk]);//printf(i%d msk%d\n,i,msk);}for(int i1;in;i) s[i]s0[i-1];return;
}
int msk;signed main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifmread();scanf( %s,s1);nstrlen(s1);for(int i1;in;i){sam.ins(s[i]);}for(int i1;im;i){//debug(%d\n,i);scanf( %s %s,op1,s1); nstrlen(s1);get(msk);//printf(%s\n,s1);if(op[1]A){for(int j1;jn;j) sam.ins(s[j]);}else{int ressam.work(s,n);printf(%d\n,res);msk^res;}}return 0;
}
/*
8
AAAAAAA
Q A
Q AA
Q AAA
A BAB
Q A
Q AABB
Q AB
Q AABAB
*/
