P5310 [Ynoi2011] 遥远的过去 记录

· · 题解

单走一个颓废记录 ，联赛前禁止 \text{Ynoi}，如果你看到了这条记录，请不要 @\text{devinwang}

首先先新定义字符串为一个序列 a_{[1,n]} ，再定义它的 \text{rank} 数组 b

定义两个字符串相等为两个字符串相等为两者的 \text{rank} 数组相同。

给定两个字符串 A,B ，你每次进行一个对 B 字符串单点改的修，然后修改完后要输出 A 中包含几个 B ？（注意字符串相等的定义

于是你开始分析，你并不想用高斯消元后上拉格朗日乘数法套一个有限微积分算出结果，于是你使用了 \text{Hash} ，并选用了一个牛逼的模数。

你发现这个字符串相等的定义很牛逼，要求 \text{rank} ，于是你上了一个平衡树。

于是再字符串 A 中里所有长度为 |B| 的子段的 \text{Hash} 值就出来了。

接下来要动态维护 B 的 \text{Hash} 值。

你选取了一个牛逼的 \text{Hash} 方法，就是对于 \text{rank} 数组 b_{[1,n]} ，值为

\sum_{i=1}^nb_i131^{n-i}

为什么不用另一种顺着 \text{Hash} 呢，你手摸一下就会发现这样维护的信息变少了。

然后你就一眼秒了，直接上一个 \text{YK} 平衡树就行了。

现在是 2021.9.8\ 21:32 ，我开始写。

现在是 2021.9.10\ 10:43 ，我写完了。

#define maxn 500010
typedef unsigned long long ull;
ull pw[maxn];
int n,m,q;
int a[maxn],b[maxn];
int rt;
int val[maxn],rk[maxn];//幂次 
int dat[maxn];
int ch[maxn][2];
int siz[maxn];
int tag[maxn];
ull ha[maxn];//幂次和 
ull sm[maxn];//Hash 
int tot;
inline void Pushup(int x){
    siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
    ha[x]=(ha[ch[x][0]]+ha[ch[x][1]]+pw[rk[x]]);
    sm[x]=(sm[ch[x][0]]+sm[ch[x][1]]+(siz[ch[x][0]]+1)*(pw[rk[x]]+ha[ch[x][1]]));
}
inline void Pushdown(int x){
    if(tag[x]){
        if(ch[x][0]){
            tag[ch[x][0]]+=tag[x];
            rk[ch[x][0]]+=tag[x];
            ha[ch[x][0]]=ha[ch[x][0]]*pw[tag[x]];
            sm[ch[x][0]]=sm[ch[x][0]]*pw[tag[x]];
        }
        if(ch[x][1]){
            tag[ch[x][1]]+=tag[x];
            rk[ch[x][1]]+=tag[x];
            ha[ch[x][1]]=ha[ch[x][1]]*pw[tag[x]];
            sm[ch[x][1]]=sm[ch[x][1]]*pw[tag[x]];
        }
        tag[x]=0;
    }
}
inline int Build(int x,int y){
    tot++;
    siz[tot]=1;
    ch[tot][0]=ch[tot][1]=0;
    val[tot]=x,rk[tot]=y,tag[tot]=0;
    sm[tot]=ha[tot]=pw[y];
    dat[tot]=rand();
    return tot;
}
inline void Split(int rt,int k,int&x,int&y){//x is small y is big
    if(!rt)x=y=0;
    else{
        Pushdown(rt);
        if(val[rt]<=k)x=rt,Split(ch[rt][1],k,ch[rt][1],y),Pushup(x);
        else y=rt,Split(ch[rt][0],k,x,ch[rt][0]),Pushup(y);
    }
}
inline int Merge(int x,int y){//x is small y is big
    if(!x||!y)return x+y;
    Pushdown(x),Pushdown(y);
    if(dat[x]<dat[y]){
        ch[x][1]=Merge(ch[x][1],y);
        Pushup(x);
        return x;
    }else{
        ch[y][0]=Merge(x,ch[y][0]);
        Pushup(y);
        return y;
    }
}
inline void o(){
    Pushdown(rt);
    tag[rt]++,rk[rt]++;
    ha[rt]=ha[rt]*pw[1],sm[rt]=sm[rt]*pw[1];
}
inline void del(int v){
    int x,y,z;
    Split(rt,v,x,y);
    Split(x,v-1,x,z);
    z=Merge(ch[z][0],ch[z][1]);
    rt=Merge(Merge(x,z),y);
}
inline void I(int a,int b){
    int x,y;
    Split(rt,a,x,y);
    rt=Merge(Merge(x,Build(a,b)),y);
}
map<ull,int>M;
signed main(){
srand(time(NULL));
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>b[i];
    pw[0]=1;
    for(int i=1;i<=n;i++)pw[i]=pw[i-1]*13331;
    for(int i=1;i<=m;i++)I(a[i],m-i);
    M[sm[rt]]++;
    for(int i=m+1;i<=n;i++){
        del(a[i-m]);
        o();
        I(a[i],0);
        M[sm[rt]]++;
    }
    rt=tot=0;
    for(int i=1;i<=m;i++)I(b[i],m-i);
    while(q--){
        int ccc,ccccc;
        cin>>ccc>>ccccc;
        del(b[ccc]);
        b[ccc]=ccccc;
        I(b[ccc],m-ccc);
        cout<<M[sm[rt]]<<endl;
    }
}

真 \text{tmd} 难写，而且自然溢出打爆开 \text{\_\_int128} 模大质数。

原来牛逼的模数竟然是 2^{64} ，我大受震撼。