Description

给你一个字符串S，你需要维护这个字符串S并支持两种操作：

1、在字符串S末尾插入一个字符。

2、记字符串T为字符串S从第 ll 个字符到第 rr 个字符所构成的子串。询问字符串T中最长的子串使得该子串在T中出现过至少两次（例如：T="ababa"，最长的子串应为aba，长度为3），并输出它的长度。如果不存在这样的子串，则输出0。

Input

第一行为一个整数 online(0≤online≤1)online(0≤online≤1) ，在下文中用到该值。

第二行为一个字符串和一个整数m，分别表示原始的字符串（仅含小写字母）和操作个数。

记 lenlen 为字符串的长度（注意它会随时改变）。

记 lastanslastans 为上次询问的答案，初始为0。

接下来m行，每行一个操作：

若操作为"1 c"格式（c为字符），表示在字符串末尾新添一个字符。新增的字符为 (c−′a′+lastans×online) mod 26+′a′(c−′a′+lastans×online) mod 26+′a′

若操作为"2 l r"格式，表示询问。记 l′=(l−1+lastans×online) mod len+1,r′=(r−1+lastans×online) mod len+1l′=(l−1+lastans×online) mod len+1,r′=(r−1+lastans×online) mod len+1 ，真正的询问区间为 [l′,r′][l′,r′] 。我们保证 1≤l′≤r′≤len1≤l′≤r′≤len （前提是你的lastans没有错）。

Output

对于每一个询问，输出一行表示答案。

Sample Input

【样例输入1】0aabda 62 1 41 b2 2 61 d2 1 72 3 7【样例输入2】1aabda 62 1 41 a2 1 51 b2 6 52 7 4

Sample Output

【样例输出1】1232【样例输出2】1232

HINT

记字符串的初始长度为 nn ，操作和询问的个数之和为 qq 。

子任务1（5分）： 1≤n,q≤50,online=11≤n,q≤50,online=1

子任务2（10分）： 1≤n,q≤250,online=11≤n,q≤250,online=1

子任务3（15分）： 1≤n,q≤1500,online=01≤n,q≤1500,online=0

子任务4（10分）： 1≤n,q≤1500,online=11≤n,q≤1500,online=1

子任务5（20分）： 1≤n,q≤30000,online=01≤n,q≤30000,online=0

子任务6（20分）： 1≤n,q≤30000,online=11≤n,q≤30000,online=1

子任务7（20分）： 1≤n,q≤50000,online=1

Solution

题目比较特殊，问的是出现至少两次，这样可以少考虑一点东西。

一个一个地加入字符，在加入到第\(r\)个字符的时候，回答\([l,r]\)的询问。

用后缀自动机来维护字符串，对每一个状态，维护一个变量\(right\)表示该状态在字符串最后出现位置的右端点，每新加入一个字符\(str_r\)，设在后缀自动机上的新节点是\(x\)，那么在parent树上，\(x\)到根节点1的\(right\)都要更新为\(r\)。这个操作用LCT维护parent树实现。

我们发现，在更新\(right\)的时候，旧的\(right\)被赋值成了新的\(r\)，但其实\(right\)和\(r\)其实刚好代表了这个状态在字符串中最后出现的两个位置。记该状态的最长后缀长度是\(len\)（后缀自动机里面的\(len\))，那么对于\(r\)时间点的所有询问，用\(len\)更新\(l\)在\([1,right-len+1)\)的询问；用\(right-l+1\)更新\(l\)在\([right-len+1,right]\)的询问，由于询问的时候\(-l+1\)是固定的，所以用\(right\)更新就好了，查询的时候\(-l+1\)。以上两个操作用两棵线段树记录。

我们发现这样更新好像忽略了很多情况，但为什么可以这样更新呢？对于同一个状态，虽然它们可能会相同地在字符串中重复很多次，但是如果我们用最右边的\(right\)更新，是可以覆盖到所有其他位置的更新操作的，所以用最右边的\(right\)来更新即可。

但是这样依然不够快，有可能\(x\)到根节点的路径比较长，这怎么办呢？

这里有个巧合：lct中，在同一条重链里面的状态，它们的\(right\)是相同的，因为这是维护时候自然体现的嘛。

我们发现可以用一条重链里面\(len\)最大的状态来代表这条链中所有的状态，按照上面说的方法更新，因为它一定能覆盖其他状态的更新。

题目要求动态加入，那么把线段树可持久化。对于询问\([l,r]\)，在\(r\)的时间点查询就好。

Tips

LCT的access操作不可调用，因为这样会破坏"同一条链的\(right\)相同的性质"，恰好连边和删边比较好做，是树上的，特殊写一下，具体见代码，真的调了好久......

对于更新操作，重写一个access操作来实现，大框架是一样的，但是注意要先断开，再更新，再连接；而不是像原版access直接换右儿子。

#include 
    
     #include 
     
      using namespace std;const int N=400005;int online,n,_n,m,ans;char str[N];inline void swap(int &x,int &y){int t=x;x=y;y=t;}inline int max(int x,int y){return x>y?x:y;}inline int rd(){    char c=getchar(); int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}inline void write(int x){    if(x>9) write(x/10);    putchar('0'+(x%10));}struct SegmentTree{/*{
    {
    {*/    int rt[N*2*19],sz,ch[N*2*19][2],maxs[N*2*19],tm[N*2*19],tmcnt;      void step(){tmcnt++;}    void insert(int u1,int &u2,int l,int r,int L,int R,int val){        if(L>R) return;        if(!u2) u2=copy(u1);        else if(tm[u2]!=tmcnt) u2=copy(u1);        if(L<=l&&r<=R){            maxs[u2]=max(maxs[u2],val);            return;        }        int mid=l+r>>1;        if(L<=mid) insert(ch[u1][0],ch[u2][0],l,mid,L,R,val);        if(mid
      
       >1;        if(pos<=mid) return query(ch[u][0],l,mid,pos,ret);        else return query(ch[u][1],mid+1,r,pos,ret);    }    inline int copy(int u){        int v=++sz;        maxs[v]=maxs[u];  tm[v]=tmcnt;        ch[v][0]=ch[u][0]; ch[v][1]=ch[u][1];        return v;    }}seg1,seg2;/*}}}*/struct Lct{/*{
    {
    {*/    int rev[N*2],ch[N*2][2],fa[N*2],val[N*2],tag[N*2],len[N*2],lenmax[N*2];    inline bool isroot(int u){return ch[fa[u]][0]!=u&&ch[fa[u]][1]!=u;}    inline int who(int u){return ch[fa[u]][1]==u;}    inline void update(int u){        lenmax[u]=max(len[u],max(lenmax[ch[u][0]],lenmax[ch[u][1]]));    }    inline void reverse(int u){        rev[u]^=1;        swap(ch[u][0],ch[u][1]);    }    inline void maketag(int u,int x){        tag[u]=x; val[u]=x;    }    inline void rotate(int u){        int f=fa[u],g=fa[f],c=who(u);        if(!isroot(f)) ch[g][who(f)]=u;        fa[u]=g;        ch[f][c]=ch[u][c^1];         if(ch[f][c]) fa[ch[f][c]]=f;        ch[u][c^1]=f; fa[f]=u;        update(f); update(u);    }    inline void pushdown(int u){        if(rev[u]){            if(ch[u][0]) reverse(ch[u][0]);            if(ch[u][1]) reverse(ch[u][1]);            rev[u]=0;        }        if(tag[u]){            if(ch[u][0]) maketag(ch[u][0],tag[u]);            if(ch[u][1]) maketag(ch[u][1],tag[u]);            tag[u]=0;        }    }    inline void pd(int u){        if(!isroot(u)) pd(fa[u]);        pushdown(u);    }    inline void splay(int u){        pd(u);        for(;!isroot(u);rotate(u))            if(!isroot(fa[u]))                rotate(who(fa[u])==who(u)?fa[u]:u);    }    inline void link(int a,int b){        splay(a);        fa[a]=b;    }    inline void cut(int a){        splay(a);        if(ch[a][0]){            fa[ch[a][0]]=fa[a]; //!!!            ch[a][0]=0;            update(a);        }        else            fa[a]=0;    }    inline int query(int u){        pd(u);        return val[u];    }    void access_special(int u,int nval){        int v;        for(v=0;u;v=u,u=fa[u]){            splay(u);            ch[u][1]=0; update(u); //!!!            int r2=val[u],maxlen=lenmax[u];            if(r2&&maxlen){                seg1.insert(seg1.rt[nval-1],seg1.rt[nval],1,_n+m,1,r2-maxlen,maxlen);                seg2.insert(seg2.rt[nval-1],seg2.rt[nval],1,_n+m,r2-maxlen+1,r2,r2);            }            ch[u][1]=v;            update(u);        }        maketag(v,nval);    }}lct;/*}}}*/struct Sam{/*{
    {
    {*/    int last,sz,len[N*2],trans[N*2][26],link[N*2];    void init(){        last=sz=1;        len[1]=link[1]=0;    }    void expand(int c){        int u=++sz,p=last;        len[u]=len[p]+1; lct.len[u]=len[u];        for(;p&&!trans[p][c];p=link[p]) trans[p][c]=u;        if(!p) link[u]=1,lct.link(u,1);        else{            int q=trans[p][c];            if(len[q]==len[p]+1) link[u]=q,lct.link(u,q);            else{                int v=++sz;                len[v]=len[p]+1; lct.len[v]=len[v]; lct.val[v]=lct.query(q);                for(int i=0;i<26;i++) trans[v][i]=trans[q][i];                lct.cut(q);                 lct.link(q,v); lct.link(u,v);                lct.link(v,link[q]);                link[v]=link[q];                 link[q]=link[u]=v;                for(;trans[p][c]==q;p=link[p]) trans[p][c]=v;            }        }        last=u;    }}sam;/*}}}*/inline void addchar(int c){    n++;    sam.expand(c);    seg1.rt[n]=seg1.rt[n-1];    seg2.rt[n]=seg2.rt[n-1];    seg1.step(); seg2.step();    lct.access_special(sam.last,n);}inline int query(int l,int r){    int ret=0;    ret=max(ret,seg1.query(seg1.rt[r],1,_n+m,l,0));    ret=max(ret,seg2.query(seg2.rt[r],1,_n+m,l,0)-l+1);    return ret;}int main(){    freopen("input.in","r",stdin);    online=rd();    scanf("%s",str+1); n=strlen(str+1);    m=rd();    _n=n; n=0;    sam.init();    for(int i=1;i<=_n;i++)         addchar(str[i]-'a');    int opt,x,y;    char inp[2];    for(int i=1;i<=m;i++){        opt=rd();        if(opt==1){            scanf("%s",inp);            inp[0]=(inp[0]-'a'+ans*online)%26+'a';            addchar(inp[0]-'a');        }        else{            x=(rd()-1+ans*online)%n+1;            y=(rd()-1+ans*online)%n+1;            write(ans=query(x,y)); putchar('\n');        }    }    return 0;}

转载于:https://www.cnblogs.com/RogerDTZ/p/8315635.html

你可能感兴趣的文章