产品设计公司网站,南京网站快速排名提升,南京免费发布信息网站,通州广州网站建设题目#xff1a;https://www.lydsy.com/JudgeOnline/problem.php?id3881 对 S 建 SAM #xff0c;每个 T 会让 S 的 parent 树的链并答案1#xff1b;在 T 走每一步的时候#xff0c;走到的节点用 LCT access 一下#xff0c;就能找到该点到 parent 根的链。 给链打标记。…题目https://www.lydsy.com/JudgeOnline/problem.php?id3881 对 S 建 SAM 每个 T 会让 S 的 parent 树的链并答案1在 T 走每一步的时候走到的节点用 LCT access 一下就能找到该点到 parent 根的链。 给链打标记。在 access 的过程中如果遇到已经打过这个 T 标记的点就停止 access 。 注意实现的时候在判断 fa[x] 有没有标记之前要先 splay(fa[x]) 。 #includecstdio
#includecstring
#includealgorithm
#define ls c[cr][0]
#define rs c[cr][1]
using namespace std;
int rdn()
{int ret0;bool fx1;char chgetchar();while(ch9||ch0){if(ch-)fx0;chgetchar();}while(ch0ch9)retret*10ch-0,chgetchar();return fx?ret:-ret;
}
const int N1e55,M2e65,K26;
int n,ps[N],tot1,c[M][K],tc[M][K],fl[M],q[M];
int tim,dfn[M],fa[M],vl[M],tg[M],sta[M];
char s[M];
bool isrt(int x){return c[fa[x]][0]!xc[fa[x]][1]!x;}
void cz(int cr)
{if(!tg[cr])return; int wtg[cr];tg[cr]0;vl[ls]w; vl[rs]w;tg[ls]w; tg[rs]w;dfn[ls]dfn[rs]dfn[cr];///
}
void rotate(int x)
{int yfa[x],zfa[y],d(xc[y][1]);if(!isrt(y))c[z][yc[z][1]]x;fa[x]z; fa[y]x; fa[c[x][!d]]y;c[y][d]c[x][!d]; c[x][!d]y;
}
void splay(int x)
{int top; sta[top1]x;for(int kx;!isrt(k);kfa[k])sta[top]fa[k];for(int itop;i;i--)cz(sta[i]);for(int yfa[x],zfa[y];!isrt(x);rotate(x),yfa[x],zfa[y])if(!isrt(y))((yc[z][0])^(xc[y][0]))?rotate(x):rotate(y);
}
void access(int x)
{splay(x); if(dfn[x]tim)return;int t0;while(1){c[x][1]t;if(!fa[x]){ tg[x];vl[x];dfn[x]tim;return;}splay(fa[x]);//splay firstif(dfn[fa[x]]tim){ tg[x];vl[x];dfn[x]tim;return;}tx; xfa[x];}
}
void link(int x,int y){ fa[y]x;}
int Ins()
{int cr1,lenstrlen(s1);for(int i1;ilen;i){int ws[i]-a;if(!tc[cr][w])tc[cr][w]tot;crtc[cr][w];}return cr;
}
void get_fl()
{int he0,tl0;for(int i0,v;iK;i)if((vtc[1][i])){q[tl]v;fl[v]1;link(1,v);}else tc[1][i]1;while(hetl){int kq[he],prfl[k];for(int i0,v;iK;i)if((vtc[k][i])){ q[tl]v;fl[v]tc[pr][i];link(tc[pr][i],v);}else tc[k][i]tc[pr][i];}
}
void solve()
{tim; int cr1,lenstrlen(s1);for(int i1;ilen;i){crtc[cr][s[i]-a];access(cr);}
}
int main()
{nrdn();for(int i1;in;i){ scanf(%s,s1); ps[i]Ins();}get_fl();int Qrdn(),op,x;while(Q--){oprdn();if(op1){ scanf(%s,s1); solve();}else{xrdn(); xps[x];splay(x); printf(%d\n,vl[x]);}}return 0;
} 转载于:https://www.cnblogs.com/Narh/p/10804518.html
