联赛前练练码力.
code:
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200006
#define ll long long
#define lson t[x].ch[0]
#define rson t[x].ch[1]
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
struct data
{
int tim,id;
data(int tim=0,int id=0):tim(tim),id(id){}
};
struct node
{
int ch[2],f,val[21],tag[21];
}t[N<<1];
ll sub;
int lastans;
char str[N];
int last,tot,n;
vector<data>G[21];
int ch[N<<1][11],pre[N<<1],len[N<<1],sta[N<<1];
inline int get(int x)
{
return t[t[x].f].ch[1]==x;
}
inline int isrt(int x)
{
return !(t[t[x].f].ch[0]==x||t[t[x].f].ch[1]==x);
}
inline void mark(int x,int p,ll v)
{
t[x].val[p]+=v,t[x].tag[p]+=v;
}
void pushdown(int x)
{
if(!x) return;
for(int i=1;i<=n;++i)
{
if(t[x].tag[i])
{
if(lson) mark(lson,i,t[x].tag[i]);
if(rson) mark(rson,i,t[x].tag[i]);
t[x].tag[i]=0;
}
}
}
void rotate(int x)
{
int old=t[x].f,fold=t[old].f,which=get(x);
if(!isrt(old)) t[fold].ch[t[fold].ch[1]==old]=x;
t[old].ch[which]=t[x].ch[which^1],t[t[old].ch[which]].f=old;
t[x].ch[which^1]=old,t[old].f=x,t[x].f=fold;
}
void splay(int x)
{
int u=x,fa,v=0;
for(sta[++v]=u;!isrt(u);u=t[u].f) sta[++v]=t[u].f;
for(;v;--v) pushdown(sta[v]);
for(u=t[u].f;(fa=t[x].f)!=u;rotate(x))
if(t[fa].f!=u) rotate(get(fa)==get(x)?fa:x);
}
void Access(int x)
{
for(int y=0;x;y=x,x=t[x].f)
{
splay(x);
rson=y;
}
}
// y 无父亲
void link(int x,int y)
{
t[y].f=x;
}
// x 是 y 的父亲
void cut(int x,int y)
{
Access(y),splay(y);
t[t[y].ch[0]].f=0;
t[y].ch[0]=0;
}
void extend(int id,int c)
{
if(ch[last][c])
{
int p=last;
int q=ch[p][c];
if(len[q]==len[p]+1) last=q;
else
{
int nq=++tot;
len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
cut(pre[q],q);
for(int j=1;j<=n;++j) t[nq].val[j]=t[q].val[j];
link(pre[q],nq);
link(nq,q);
pre[nq]=pre[q],pre[q]=nq;
for(;p&&ch[p][c]==q;p=pre[p]) ch[p][c]=nq;
last=nq;
}
}
else
{
int np=++tot,p=last;
len[np]=len[p]+1,last=np;
for(;p&&!ch[p][c];p=pre[p]) ch[p][c]=np;
if(!p) pre[np]=1,link(1,np);
else
{
int q=ch[p][c];
if(len[q]==len[p]+1) pre[np]=q,link(q,np);
else
{
int nq=++tot;
len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
cut(pre[q],q);
for(int j=1;j<=n;++j) t[nq].val[j]=t[q].val[j];
link(pre[q],nq);
link(nq,q);
link(nq,np);
pre[nq]=pre[q],pre[q]=pre[np]=nq;
for(;p&&ch[p][c]==q;p=pre[p]) ch[p][c]=nq;
}
}
sub+=len[np]-len[pre[np]];
}
Access(last),splay(last),mark(last,id,1ll);
}
int main()
{
// setIO("input");
int i,j,ty,m;
scanf("%d%d",&n,&ty);
for(tot=i=1;i<=n;++i)
{
scanf("%s",str+1);
int len=strlen(str+1);
for(last=j=1;j<=len;++j) extend(i,str[j]-'0');
G[i].push_back(data(0,last));
}
scanf("%d",&m);
for(i=1;i<=m;++i)
{
int op,x,y,z;
scanf("%d",&op);
if(op==1)
{
scanf("%d%d",&x,&y);
y=(y^(lastans*1ll*ty))%10;
last=G[x][G[x].size()-1].id;
extend(x,y);
G[x].push_back(data(i,last));
}
if(op==2)
{
scanf("%d%d%d",&x,&y,&z);
int l=0,r=G[x].size()-1,mid=0,pp=0;
while(l<=r)
{
mid=(l+r)>>1;
if(G[x][mid].tim<=y) pp=G[x][mid].id,l=mid+1;
else r=mid-1;
}
Access(pp),splay(pp);
printf("%d
",lastans=t[pp].val[z]);
}
if(op==3)
{
printf("%lld
",sub);
}
if(op==4)
{
scanf("%s",str+1);
int len=strlen(str+1),pp=1,flag=0;
for(j=1;j<=len;++j)
{
if(ch[pp][str[j]-'0']) pp=ch[pp][str[j]-'0'];
else { flag=1;break; }
}
// 能匹配
if(!flag)
{
Access(pp);
int best=0;
for(j=1;j<=n;++j) best=max(best,t[pp].val[j]);
lastans=best;
}
else lastans=0;
printf("%d
",lastans);
}
}
return 0;
}