网站建设A系列套餐报价,直播网站如何做,盘锦做网站电话,公众号推广引流正题
题目链接:https://www.luogu.com.cn/problem/P5212 题目大意
开始一个字符串SSS#xff0c;有nnn次操作
在SSS末尾加入一个字符串询问一个串在SSS中出现了多少次
强制在线 解题思路
强制在线的话#xff0c;只有SAM\text{SAM}SAM能够支持动态插字符了#xff0c;但…正题
题目链接:https://www.luogu.com.cn/problem/P5212 题目大意
开始一个字符串SSS有nnn次操作
在SSS末尾加入一个字符串询问一个串在SSS中出现了多少次
强制在线 解题思路
强制在线的话只有SAM\text{SAM}SAM能够支持动态插字符了但是我们平时统计答案的时候要先做一次拓扑排序然后上传信息。
这里要动态维护parents\text{parents}parents树的话用LCT\text{LCT}LCT就好了就是链修改加单点查询然后因为根是指定的可以少写很多操作。
时间复杂度O((nS)log∣S∣)O(\ (nS)\log |S|)O( (nS)log∣S∣) code
#includecstdio
#includecstring
#includealgorithm
#includestack
using namespace std;
const int N6e5*210;
int n,cnt,len[N],fa[N],ch[N][26];
char st[N];
struct LCT{int t[N][2],lazy[N],w[N],fa[N];stackint s;bool Nroot(int x){return fa[x]((t[fa[x]][0]x)||(t[fa[x]][1]x));}bool Direct(int x){return t[fa[x]][1]x;}void Add(int x,int val){if(x)w[x]val,lazy[x]val;return;}void PushDown(int x){if(!lazy[x])return;if(t[x][0])Add(t[x][0],lazy[x]);if(t[x][1])Add(t[x][1],lazy[x]);lazy[x]0;return;}void Rotate(int x){int yfa[x],zfa[y];int xsDirect(x),ysDirect(y);int wt[x][xs^1];if(Nroot(y))t[z][ys]x;t[y][xs]w;t[x][xs^1]y;if(w)fa[w]y;fa[y]x;fa[x]z;return;}void Splay(int x){int yx;s.push(x);while(Nroot(y))yfa[y],s.push(y);while(!s.empty())PushDown(s.top()),s.pop();while(Nroot(x)){yfa[x];if(!Nroot(y))Rotate(x);else if(Direct(y)Direct(x))Rotate(y),Rotate(x);else Rotate(x),Rotate(x);}return;}void Access(int x){for(int y0;x;yx,xfa[x])Splay(x),t[x][1]y;return;}void Link(int x,int y)//x为单点y为树{fa[x]y;Access(y);Splay(y);Add(y,w[x]);return;}void Cut(int x)//将x切断为单点{Access(x);Splay(x);Add(t[x][0],-w[x]);fa[t[x][0]]0;t[x][0]0;return;}
}T;
void decode(char *s,int l,int mask) {for (int j0;jl;j) {mask(mask*131j)%l;swap(s[j],s[mask]);}return;
}
int insert(int c,int p){int npcnt;len[np]len[p]1;T.w[np];for(;p!ch[p][c];pfa[p])ch[p][c]np;if(!p)fa[np]1,T.Link(np,1);else{int qch[p][c];if(len[p]1len[q])fa[np]q,T.Link(np,q);else{int nqcnt;len[nq]len[p]1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]fa[q];fa[np]fa[q]nq;T.Cut(q);T.Link(nq,fa[nq]);T.Link(np,nq);T.Link(q,nq);for(;pch[p][c]q;pfa[p])ch[p][c]nq;}}return np;
}
int main()
{scanf(%d,n);scanf(%s,st);int lstrlen(st);int pcnt1;int mask0;for(int i0;il;i)pinsert(st[i]-A,p);while(n--){char op[5];scanf(%s %s,op,st);lstrlen(st);decode(st,l,mask);if(op[0]Q){int x1;for(int i0;il;i)if(!ch[x][st[i]-A]){x0;break;}else xch[x][st[i]-A];if(!x)puts(0);else{T.Splay(x);printf(%d\n,T.w[x]);mask^T.w[x];}}else{for(int i0;il;i)pinsert(st[i]-A,p);}}return 0;
}
