题目概述

NIO with String Game

解题报告

感觉赛时榜都歪飞了……这题明明不难却只有20个队过。

由于对 $t_i$ 只有单字符加的操作，因此最终所有 $t_i$ 长度和不会很长，可以考虑离线之后把最终 $t_i$ 插入到Trie中。然后在Trie上求DFS序就可以得知所有节点的字典序顺序。

对于 $s$ 有大量的重复字符插入，不难想到利用倍增快速查找Trie上的位置。如果 $s$ 在某次大量字符插入时在Trie上无法找到相应的节点，那么就记录最终停止的节点 $p$ 以及无法再继续走下去的字符 $fl$ ，后续继续插入大量字符时仍保持 $p$ 和 $fl$ 即可。

查询严格小于 $s$ 字符串个数时，只需要在DFS序上查找一个前缀，如果 $fl$ 为空说明 $s$ 正好停在Trie上的节点 $p$ 上，此时查询 $1$ 到 $p$ 入栈序 $-1$ ，否则说明 $s$ 已经不在Trie上出现，我们先找到最大的 $ch<fl$ 使得 $son_{p,ch}$ 非空，令 $u=son_{p,ch}$ ，此时查询 $1$ 到 $u$ 的出栈序，如果 $u$ 找不到，则直接查询 $1$ 到 $p$ 的入栈序。我们利用树状数组来维护每个 $t_i$ 当前出现在Trie的哪个节点上，即可求出前缀和。

注意倍增需要一个技巧：如果从上往下一直跳某个字符，每个节点需要对于每个字符都开倍增数组，这样是不可接受的，不难发现如果我们记录 $who_{x,ch}$ 表示节点 $x$ 往下一直跳 $ch$ 字符最深能到哪里，就可以通过从下往上跳规避掉这个问题。

示例程序

注意第二个操作读入的 $p$ 需要开long long……

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=200000,maxq=200000,maxl=200000,maxt=maxl+maxq,LOG=18;

int n,Q;char s[maxl+5];
int L[maxn+5],R[maxn+5];char t[maxl+5];
int pos[maxn+5],now[maxn+5];
int pl,ro,son[maxt+5][26],lt[maxt+5],rt[maxt+5];
int who[maxt+5][26],ST[maxt+5][LOG+1],dep[maxt+5];
struct giao {int tp,w;LL x;} q[maxq+5];
int c[maxt+5];
int T;struct seg {LL R;int w,p,fl;} S[maxt+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
int reads(char *s){
    int len=0;char ch=readc();
    while (!islower(ch)) {if (ch==EOF) return EOF;ch=readc();}
    while (islower(ch)) s[++len]=ch,ch=readc();
    s[len+1]=0;return len;
}
char getlwr() {char ch=readc();while (!islower(ch)) ch=readc();return ch;}
inline int Extend(int p,int w) {if (!son[p][w]) son[p][w]=++pl;return son[p][w];}
void DFS(int x,int pre=0){
    lt[x]=++lt[0];ST[x][0]=pre;dep[x]=dep[pre]+1;
    for (int j=1;j<=LOG;j++) ST[x][j]=ST[ST[x][j-1]][j-1];
    for (int i=0,u;i<26;i++)
        if (u=son[x][i])
            DFS(u,x),who[x][i]=who[u][i]; else who[x][i]=x;
    rt[x]=lt[0];
}
void Add(int x,int y) {for (;x<=lt[0];x+=x&-x) c[x]+=y;}
int Sum(int x) {int sum=0;for (;x;x-=x&-x) sum+=c[x];return sum;}
inline void Update(int &p,int w) {Add(lt[p],-1);p=son[p][w];Add(lt[p],1);}
void Find(int &p,int &fl,int q,int cnt,int w){
    int x=who[q][w];
    if (cnt>dep[x]-dep[q]) p=x,fl=w; else {
        cnt=dep[x]-dep[q]-cnt;
        for (int j=LOG;~j;j--) if (cnt>>j&1) x=ST[x][j];
        p=x;fl=-1;
    }
}
int main(){
    readi(n);readi(Q);T=reads(s);
    for (int i=1;i<=n;i++){
        L[i]=R[i-1]+1;R[i]=reads(t+L[i]-1);
        R[i]+=L[i]-1;
    }
    ro=++pl;
    for (int i=1;i<=n;i++){
        pos[i]=ro;
        for (int j=L[i];j<=R[i];j++) pos[i]=Extend(pos[i],t[j]-'a');
    }
    for (int i=1;i<=n;i++) now[i]=pos[i];
    for (int i=1;i<=Q;i++){
        readi(q[i].tp);
        if (q[i].tp<=3) readi(q[i].x);
        if (q[i].tp==1 || q[i].tp==3) q[i].w=getlwr()-'a';
        if (q[i].tp==1) now[q[i].x]=Extend(now[q[i].x],q[i].w);
    }
    DFS(ro);
    S[0].p=ro;S[0].fl=-1;
    for (int i=1,u;i<=T;i++){
        S[i].R=S[i-1].R+1;S[i].w=s[i]-'a';
        if (S[i-1].fl>=0) S[i].p=S[i-1].p,S[i].fl=S[i-1].fl; else {
            if (u=son[S[i-1].p][S[i].w]) S[i].p=u,S[i].fl=-1;
            else S[i].p=S[i-1].p,S[i].fl=S[i].w;
        }
    }
    for (int i=1;i<=n;i++) now[i]=pos[i],Add(lt[now[i]],1);
    for (int i=1;i<=Q;i++){
        if (q[i].tp==1) Update(now[q[i].x],q[i].w); else
        if (q[i].tp==2){
            LL x=q[i].x;
            while (T && x>=S[T].R-S[T-1].R) x-=S[T].R-S[T-1].R,T--;
            if (x){
                S[T].R-=x;
                if (S[T-1].fl>=0) S[T].p=S[T-1].p,S[T].fl=S[T-1].fl;
                else Find(S[T].p,S[T].fl,S[T-1].p,S[T].R-S[T-1].R,S[T].w);
            }
        } else if (q[i].tp==3){
            T++;S[T].R=S[T-1].R+q[i].x;S[T].w=q[i].w;
            if (S[T-1].fl>=0) S[T].p=S[T-1].p,S[T].fl=S[T-1].fl;
            else Find(S[T].p,S[T].fl,S[T-1].p,S[T].R-S[T-1].R,S[T].w);
        } else {
            if (S[T].fl>=0){
                int x=S[T].p,j=S[T].fl-1;
                while (j>=0 && !son[x][j]) j--;
                if (j<0) printf("%d\n",Sum(lt[x]));
                else printf("%d\n",Sum(rt[son[x][j]]));
            } else printf("%d\n",Sum(lt[S[T].p]-1));
        }
    }
    return 0;
}