浅谈哈希

Phi_Mobius · 2026-10-03 17:46:00 · 算法·理论

upd on 2026/10/18：添加了例题 P8819 [CSP-S 2022] 星战，拜谢审核大人。

我不会哈希。

Pt.1 小时候还没长开

字符串哈希

P3370 【模板】字符串哈希

才发现我没做过字符串哈希模板……

如果每次判断第 i 个字符串是否与前 i-1 个字符串里出现过，逐位判断两个字符串是否相等，复杂度是 \Theta(n^2m) 的。发现问题在于每次判断两个字符串是否相等太费事了，怎么优化呢？

发现可以把一个字符串看成一个高进制数，转成十进制，再模一个大数，我们就可以把这个值当作原来的字符串，我们把这个结果称为字符串的哈希值。这种哈希称作多项式哈希，具体地：

其中 l,b,M 分别为串长、进制和模数。

不同的字符串转化的数值大概率也不同。于是转化成统计一共有多少种不同的哈希值，直接把串的哈希值排序，然后统计即可，总复杂度 \Theta(n\log n+nm)。

::::success[AC Code]

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int Base=1949; //进制
const int MOD=1e15+37; //模数
int n,ans;
string s;
int h[10010];
int hs(string str){
    int res=0;
    for(int i=0;i<str.size();i++)
        res=(res*Base+str[i])%MOD;
    return res; 
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
        h[i]=hs(s);
    }
    sort(h+1,h+n+1);
    for(int i=1;i<=n;i++)
        if(h[i]!=h[i-1]) ans++;
    cout<<ans;
    return 0;
}

::::

如上，我们在解决问题时，常常遇到各种复杂而难处理的结构（如序列、字符串、树等等），哈希就是把复杂的结构映射成简单的结构。

代码中的 int hs(string str) 就是哈希函数。注意，哈希函数没有固定形式，有时可能需要根据具体的问题构造非平凡的哈希函数。使用哈希时要注意哈希函数 “能用” 和 “好用” 的问题，下文会继续探讨。

但是，我们就这样把无穷的字符串集合压缩成有限的数集，不会有问题吗？

有的有的。其实哈希是个概率正确的算法，例如如果我们代码中取 Base=123,MOD=1e7+17，就会发现 WA 了。这是因为把两个不同的字符串代入我们的哈希函数后得到了相同结果，程序就会误以为它们是一个串，从而使答案过小，这就叫作哈希冲突。

当然没有人喜欢挂分，那我们如何尽量减少哈希冲突呢？这就要看我们的哈希函数了。如果我们的哈希函数是把所有字符的 ASCII 码加起来再取模，冲突概率就极高，例如 ab 和 ba 就会冲突。如果使用我们的大进制数哈希，N\ll\sqrt M 时，随机数据下产生至少一次冲突的概率约为 \frac{N^2}{2M}，否则概率接近 1。其中 N 和 M 分别为元素数和模数。

为了减少哈希冲突，我们一般选择质数作为模数（自然溢出哈希选取奇数进制即可），以便使进制与模数互质，避免较高位的字符由于进制幂次较高而在模意义下失去辨识度。

如果想彻底避免冲突，可以对每个哈希值开一个链表，然后进一步精确判断哈希值相同的字符串（或其他东西）是否相同。恭喜你发明了哈希表。

除此以外，还有随机模数、多值哈希等反卡哈希的做法，暂不深入。

子串哈希

P10468 兔子与兔子

如何快速求出子串的哈希值？预处理字符串 s 的前缀哈希值，令 H(l,r) 为子串 s[l\dots r] 的哈希值，按照把字符串看成高进制数的思路，容易得到：

其中 b,m 分别为进制和模数。

::::success[AC Code]

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#define int long long
#define ull unsigned long long
using namespace std;
const int N=1e6+7,Base=137;
int m,l1,r1,l2,r2;
string s;
ull h[N];
ull pw[N];
ull hs(int l,int r){
    return h[r]-h[l-1]*pw[r-l+1];
}
signed main(){
    pw[0]=1;
    cin>>s;
    s=" "+s;
    for(int i=1;i<s.size();i++){
        h[i]=h[i-1]*Base+(s[i]-'a'); 
        pw[i]=pw[i-1]*Base;
    }
    cin>>m;
    while(m--){
        cin>>l1>>r1>>l2>>r2;
        if(hs(l1,r1)==hs(l2,r2)) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

::::

子串哈希搭配二分，可以解决大部分提高组范围内的串串问题，例如求 LCP（最长公共前缀，如 \text{LCP}(\texttt{"abca"},\texttt{"abda"})=\texttt{"ab"} ），发现公共前缀有单调性，即如果长 i 的前缀是公共的，则长 i-1 的也是；如果长 i 的不是，长 i+1 的也不是。我们又可以 \Theta(1) 求子串哈希，判断前缀是否是公共的，搭配二分可以做到单次询问 \Theta(\log n) 求 LCP。

例题

P4503 [CTSC2014] 企鹅 QQ

考虑枚举唯一不同的位，然后在每个串的哈希值中“扣掉”这一位，即 H'=H-s_i\times b^{l-i}，然后就是【模板】字符串哈希了。

::::success[AC Code]

#include<iostream>
#include<algorithm>
#define ull unsigned long long
const int Base=197;
using namespace std;
int n,l,w;
string s[30007];
ull pw[2007];
ull x[30007*207];
ull hs[30007];
int ans;
signed main(){
    cin>>n>>l>>w;
    pw[0]=1;
    for(int i=1;i<=l;i++) pw[i]=pw[i-1]*Base;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]=" "+s[i];
        for(int j=1;j<=l;j++)
            hs[i]=hs[i]*Base+s[i][j];
    }
    for(int i=1;i<=l;i++){
        for(int j=1;j<=n;j++)
            x[j]=hs[j]-s[j][i]*pw[l-i];
        sort(x+1,x+n+1);
        int t=1;
        for(int j=1;j<=n;j++){
            if(x[j]==x[j-1]){
                ans+=t;
                t++;
            }
            else t=1;
        }
    }
    cout<<ans;
    return 0;
}

::::

P3763 [TJOI2017] DNA

考虑暴力慢在哪。发现一位一位匹配太慢了，能不能像上一题，枚举不同的位呢？要求至多三位不同，直接枚举复杂度太高，我们不妨考虑从相同的位置入手。

现在把 S 的首位对齐 S_0 的第 i 位进行匹配，先 \Theta(\log n) 求出 S_0 从 i 开始的后缀与 S 的 LCP 长度 x，然后跳过一个不同的位置，把 S 的第 x+2 位与 S_0 的第 i+x+1 位对齐，然后从这个位置开始求 LCP，如果重复至多四次（跳过了至多三个字符）S 就匹配完了，则计入答案，继续匹配 S 的首位对齐 S_0 的第 i+1 位。总复杂度 \Theta(n\log n)。

::::success[AC Code]

#include<iostream>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
const int Base=114514,MOD=998244353;
int T;
string s,t;
int n,m;
int hs[100010],ht[100010],p[100010]={1};
int hashs(int l,int r){
    return (hs[r]-hs[l-1]*p[r-l+1]%MOD+MOD)%MOD;
}
int hasht(int l,int r){
    return (ht[r]-ht[l-1]*p[r-l+1]%MOD+MOD)%MOD;
}
int lcp(int a,int b){
    int l=0,r=min(n-a+1,m-b+1),ans=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(hashs(a,a+mid-1)==hasht(b,b+mid-1)) l=mid+1,ans=mid;
        else r=mid-1;
    }
    return ans;
}
int check(int i){
    int cur1=i,cur2=1;
    for(int j=1;j<=3;j++){
        int x=lcp(cur1,cur2);
        cur1=cur1+x-1;
        cur2=cur2+x-1;
        if(cur2==m) return 1;
        cur1+=2,cur2+=2;
    }
    int x=lcp(cur1,cur2);
    cur1=cur1+x-1;
    cur2=cur2+x-1;
    return cur2==m;
}
signed main(){
    for(int i=1;i<=100001;i++) p[i]=p[i-1]*Base%MOD;
    cin>>T;
    while(T--){
        for(int i=1;i<=n;i++) hs[i]=0;
        for(int i=1;i<=m;i++) ht[i]=0;
        cin>>s>>t;
        n=s.size();m=t.size();
        s=" "+s;t=" "+t;
        for(int i=1;i<=n;i++) hs[i]=(hs[i-1]*Base+s[i]-'A')%MOD;
        for(int i=1;i<=m;i++) ht[i]=(ht[i-1]*Base+t[i]-'A')%MOD;
        int ans=0;
        for(int i=1;i+m-1<=n;i++){
            ans+=check(i);
        }
        cout<<ans<<'\n';
    }
    return 0;
}
::::

[P2757 [国家集训队] 等差子序列](https://www.luogu.com.cn/problem/P2757)

首先发现只要判断是否存在长度为 3 的等差数列即可，自然考虑枚举中间项。由于 $a$ 是排列，对于 $a_i\ne a_j$，$a_j$ 要么在 $a_i$ 之前要么在 $a_i$ 之后。从前往后扫的过程中维护一个 01 串 $s$，$s_i=1$ 表示 $i$ 在前方出现过，否则 $i$ 在后方。

假设当前扫到了 $a_i$，则需判断是否 $\exists k,\ s_{a_i-k}\ne s_{a_i+k}$，相当于**不**以 $a_i$ 为中心回文。带修改，用树状数组维护哈希值，子串哈希判断。具体地，设最大扩展半径 $r=\min(a_i-1,n-a_i)$，则判断 $H(a_i-r,a_i)\ne H^\mathrm{rev}(\mathrm{rev}(a_i+r),\mathrm{rev}(a_i))$ 即可。

其中 $H^\mathrm{rev}(l,r)$ 表示反串上的位置 $l$ 到 $r$ 的子串哈希值，$\mathrm{rev}(i)=n-i+1$。

::::success[AC Code]
```cpp line-numbers
#include<iostream>
#include<algorithm>
#include<vector>
#define int long long
#define ull unsigned long long
#define lowbit(x) ((x)&(-(x)))
#define rev(x) (n-(x)+1)
using namespace std;
const int N=5e5+7;
const ull Base=137;
int T,n,a[N];
ull h[N][2],p[N]={1};//1 rev
void add(int x,ull k,bool f){ for(;x<=n;x+=lowbit(x)) h[x][f]+=k; }
ull ask(int l,int r,bool f){
    ull res=0;l--;
    for(;r;r-=lowbit(r)) res+=h[r][f];
    for(;l;l-=lowbit(l)) res-=h[l][f];
    return res;
}
signed main(){
    for(int i=1;i<N;i++) p[i]=p[i-1]*Base;
    cin>>T;
    while(T--){
        for(int i=1;i<=n;i++)
            h[i][0]=h[i][1]=0;
        cin>>n;
        bool f=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(f) continue;
            add(a[i],p[a[i]],0);
            add(n-a[i]+1,p[n-a[i]+1],1);
            int l1=max(1ll,2*a[i]-n),r1=a[i]-1;
            int l2=rev(min(n,2*a[i]-1)),r2=rev(a[i]+1);
            int h1=ask(l1,r1,0),h2=ask(l2,r2,1);
            if(l1>l2) swap(l1,l2),swap(h1,h2);
            if(h1*p[l2-l1]!=h2){
                cout<<"Y\n";
                f=1;
            }
        }
        if(!f) cout<<"N\n";
    }
    return 0;
}

Pt.2 喝，长大了

你以为这就是哈希了吗？

回忆一下，哈希就是把复杂的结构映射成简单的结构，那这个“复杂的结构”并不一定是字符串，“简单的结构”也不一定是数，有时甚至可能把数映射到其他的东西来构造某种性质，需要同时兼顾 “能用”（冲突概率小）和 “好用”（方便解决问题）的问题。

写完发现变成杂题选讲了。

特征值哈希

起的名字。

P6688 可重集

以下 \{\} 表示可重集。

把子段看成可重集，考虑如何快速判断两个可重集是否“本质相同”，我们想要构造一个把可重集映射成数的哈希函数 H(A)，满足：

1. 由于是可重集，哈希值与数列中元素的顺序无关。
3. 冲突概率较小。（“能用”）

由于条件 1，我们的多项式哈希不再适用，我们可以考虑形如 H(A)=\sum_{x\in A}f(x) 的哈希函数。再根据条件 2，可以写出：

其中 b,M 分别为进制和模数。

则有：

现在考虑条件 3。这个哈希函数的冲突情况如何呢？先考虑不取模的情况。原哈希函数去掉取模可以写作：

其中 c_x 为 x 在 A 中的出现次数。发现这可以看作一个 b 进制数，而当 c_x\ge b 时，就会产生“进位”，例如当 b=2 时，\{1,1\} 的表现就相当于 \{2\}。于是我们选取 b\gg n 即可。

回看推导过程，发现我们还有一个地方没有解决：\{a_i+k\} 的 k。数据结构额外维护一个序列“标准值”即可。题解中大多维护极值，我的实现选择维护区间和（用于求平均数）。（懒得写线段树） 然后对于两个区间，看两个区间的区间和的差是否是长度的倍数，若不是，直接判 No，否则把两区间和之差的绝对值除以区间长度得到 k，区间和较小的区间的哈希值乘上 b^k 再取模，与另一区间哈希值比较即可。

::::success[AC Code] 毒瘤数据卡自然溢出。交了 20 遍。

#include<iostream>
#include<algorithm>
#define int long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N=1e6+7,Base=1145141,MOD=998244353;
int n,q,a[N],p[N]={1};
int s[N],h[N];
void adds(int x,int k){ for(;x<=n;x+=lowbit(x)) s[x]+=k; }
void addh(int x,int k){ for(;x<=n;x+=lowbit(x)) h[x]=(h[x]+k+MOD)%MOD; }
int asks(int l,int r){
    int res=0;l--;
    for(;r;r-=lowbit(r)) res+=s[r];
    for(;l;l-=lowbit(l)) res-=s[l];
    return res;
}
int askh(int l,int r){
    int res=0;l--;
    for(;r;r-=lowbit(r)) res=(res+h[r]+MOD)%MOD;
    for(;l;l-=lowbit(l)) res=(res-h[l]+MOD)%MOD;
    return res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    for(int i=1;i<N;i++) p[i]=p[i-1]*Base%MOD;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        adds(i,a[i]);
        addh(i,p[a[i]]);
    }
    while(q--){
        int op;
        cin>>op;
        if(op){
            int l1,r1,l2,r2;
            cin>>l1>>r1>>l2>>r2;
            int s1=asks(l1,r1),s2=asks(l2,r2);
            if(s1>s2) swap(l1,l2),swap(r1,r2),swap(s1,s2);
            int d=s2-s1,len=r1-l1+1;
            if(d%len){
                cout<<"NO\n";
                continue;
            }
            d/=len;
            int h1=askh(l1,r1),h2=askh(l2,r2);
            if(h1*p[d]%MOD==h2) cout<<"YES\n";
            else cout<<"NO\n";
        }
        else{
            int x,y;
            cin>>x>>y;
            adds(x,-a[x]);
            addh(x,-p[a[x]]);
            adds(x,y);
            addh(x,p[y]);
            a[x]=y;
        }
    }
    return 0;
}

P8819 [CSP-S 2022] 星战

竟然把这题忘了……

Anyway，让我们庆祝神帖评论破千！

钦定读者了解基环树相关知识。

突然发现 OI-Wiki 上没有基环树？

简要题意：维护一个有向图，支持删边 (u,v)，加边 (u,v)，删除点 u 的所有入边，恢复点 u 的所有入边，并在每次操作后判断图是否为内向基环树森林，即所有点的出度是否全为 1。

考虑维护图的节点出度数组的多项式 Hash，即：

其中 G,V,\deg(v),b,M 分别为图、点集、点 v 的出度、进制、模数。

若当前 G_\text{now} 满足：

则输出 YES。

然后考虑维护。我们发现操作 2、4 似乎十分困难，问题在于我们要在终点处批量处理入边，而修改的是很多节点的 \deg 值。但这仍然容易处理，我们只需预处理出原图中每个点 v 作为边的终点对整个图哈希值的贡献 \displaystyle\text{contrib}(v)=\left(\sum_{(u,v)\in E} b^{u-1}\right)\bmod M，并维护出当前图 G_\text{now} 中 v 的 \text{contrib}_{\text{now}}(v)，则四个操作修改如下（下文运算均在模 M 意义下）：

操作 1：

操作 2：

操作 3：

操作 4：

做完了。 ::::success[AC Code]

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<random>
#define int long long
#define ull unsigned long long
using namespace std;
const int N=5e5+7,base=1949;
int n,m,q;
ull pw[N],val[N],now[N],nowhs,keyhs;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    pw[0]=1;
    for(int i=1;i<=n;i++){
        pw[i]=pw[i-1]*base;
        keyhs+=pw[i];
    }
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        val[v]+=pw[u];
    }
    for(int i=1;i<=n;i++){
        now[i]=val[i];
        nowhs+=now[i];
    }
    cin>>q;
    while(q--){
        int t,u,v;
        cin>>t;
        if(t==1){
            cin>>u>>v;
            nowhs-=pw[u];
            now[v]-=pw[u];
        }
        else if(t==2){
            cin>>u;
            nowhs-=now[u];
            now[u]=0;
        }
        else if(t==3){
            cin>>u>>v;
            nowhs+=pw[u];
            now[v]+=pw[u];
        }
        else if(t==4){
            cin>>u;
            nowhs-=now[u];
            now[u]=val[u];
            nowhs+=now[u];
        }
        if(nowhs==keyhs) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

::::

P14963 [LBA-OI R2 B] 何意味

何意味？！

听说有原题。但是我觉得很神啊。

判定操作等价于问 s[l_1\dots r_1] 和 t[l_2\dots r_2] 消消乐之后是否相等。考虑如何描述消消乐操作。

1. 消消乐不具有交换律。
2. 相同元素可以消掉。

条件 1 让我们想到了我们的老朋友：矩阵！

由条件 2，假设元素 x 转化成了矩阵 \begin{pmatrix} a&b\\ c&d \end{pmatrix}，则需要满足：\begin{pmatrix} a&b\\ c&d \end{pmatrix}\times\begin{pmatrix} a&b\\ c&d \end{pmatrix}=I

其中 I 为单位矩阵。

展开得：

解得一组解：

于是元素 x 转化为矩阵 H(x)=\begin{pmatrix} x&1\\ 1-x^2&-x \end{pmatrix}。该矩阵满足 H(x)^2=I，而矩阵乘法不满足交换律，于是我们完美地刻画了消消乐。

为了让哈希强一些，先把 a_i 随机映射到 f(a_i)，再把 H(f(a_i)) 丢到线段树上，维护区间矩阵积，每次判定两个区间矩阵积是否相等即可。pushup 注意乘法顺序。 ::::success[AC Code]

#include<iostream>
#include<algorithm>
#include<vector>
#include<random>
#define int long long
#define ull unsigned long long
using namespace std;
const int N=5e5+7;
mt19937_64 rd(114514);
int n,m,s[N][2];
ull h[N];
struct matrix{
    ull a[2][2];
    matrix operator*(const matrix& mtrx)const{
        matrix res;
        res.a[0][0]=a[0][0]*mtrx.a[0][0]+a[0][1]*mtrx.a[1][0];
        res.a[0][1]=a[0][0]*mtrx.a[0][1]+a[0][1]*mtrx.a[1][1];
        res.a[1][0]=a[1][0]*mtrx.a[0][0]+a[1][1]*mtrx.a[1][0];
        res.a[1][1]=a[1][0]*mtrx.a[0][1]+a[1][1]*mtrx.a[1][1];
        return res;
    }
    bool operator==(const matrix& mtrx)const{
        return a[0][0]==mtrx.a[0][0]
            && a[0][1]==mtrx.a[0][1]
            && a[1][0]==mtrx.a[1][0]
            && a[1][1]==mtrx.a[1][1];
    }
}I={{{1,0},{0,1}}};
inline matrix hs(int x){
    ull a=h[x];
    return {{{a,(ull)1},{(ull)1-a*a,-a}}};
}
struct node{
    int l,r;
    matrix val;
}tr[N<<2][2];
void pushup(int u,bool f){
    tr[u][f].val=tr[u<<1][f].val*tr[u<<1|1][f].val;
}
void build(int u,int l,int r,bool f){
    if(l==r){
        tr[u][f]={l,r,hs(s[l][f])};
        return ;
    }
    int mid=(l+r)>>1;
    tr[u][f]={l,r,I};
    build(u<<1,l,mid,f);build(u<<1|1,mid+1,r,f);
    pushup(u,f);
}
void modify(int u,int x,int k,bool f){
    if(tr[u][f].l==tr[u][f].r){
        tr[u][f].val=hs(k);
        return ;
    }
    int mid=(tr[u][f].l+tr[u][f].r)>>1;
    if(x<=mid) modify(u<<1,x,k,f);
    else modify(u<<1|1,x,k,f);
    pushup(u,f); 
}
matrix ask(int u,int l,int r,bool f){
    if(tr[u][f].l>=l && tr[u][f].r<=r) return tr[u][f].val;
    int mid=(tr[u][f].l+tr[u][f].r)>>1;
    if(r<=mid) return ask(u<<1,l,r,f);
    if(l>mid) return ask(u<<1|1,l,r,f);
    return ask(u<<1,l,r,f)*ask(u<<1|1,l,r,f);
}
signed main(){
    for(int i=0;i<N;i++) h[i]=rd();
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>s[i][0];
    for(int i=1;i<=n;i++) cin>>s[i][1];
    build(1,1,n,0);build(1,1,n,1);
    while(m--){
        int op,l1,r1,l2,r2,x,k;
        cin>>op;
        if(op==1){
            cin>>l1>>r1>>l2>>r2;
            if(ask(1,l1,r1,0)==ask(1,l2,r2,1)) cout<<"Yes\n";
            else cout<<"No\n";
        }
        if(op==2){
            cin>>x>>k;
            modify(1,x,k,0);
        }
        if(op==3){
            cin>>x>>k;
            modify(1,x,k,1);
        }
    }
    return 0;
}

::::

随机化哈希

推荐使用 mt19937。

下文中 \bigoplus 表异或。

P3792 由乃与大母神原型和偶像崇拜

首先考虑如果我们知道了一个区间的最小和最大值，如何快速判断这个区间是否满足条件？注意到值域不太大，于是这就是个套路的哈希：给每个数值 x 随机分配一个哈希值 h_x，如果：

则可以认为这个区间满足要求。于是我们只需维护区间极值和哈希值异或和即可。

事实上我们还是不需要写线段树，我们只需维护区间加和 s(l,r)，然后假设区间符合要求，则 \max a=\min a+r-l，进而 s(l,r)=\frac{(\min a+(\min a+r-l))(r-l+1)}{2} 于是可以解出 \min a,\max a，哈希判断即可。如果“区间符合要求”假设不成立，那我们后面都是瞎算，所以最终哈希判定结果也几乎肯定是否定的。

常数又小代码又少谁不喜欢树状数组啊？

::::success[AC Code]

#include<iostream>
#include<algorithm>
#define int long long
#define ull unsigned long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N=5e5+7,V=2.5e7+7;
int n,m,a[N],sa[N];
ull h[V],sum[V],sh[N];
void adda(int x,int k){ for(;x<=n;x+=lowbit(x)) sa[x]+=k; }
void xorh(int x,ull k){ for(;x<=n;x+=lowbit(x)) sh[x]^=k; }
int aska(int l,int r){
    int res=0;l--;
    for(;r;r-=lowbit(r)) res+=sa[r];
    for(;l;l-=lowbit(l)) res-=sa[l];
    return res;
}
ull askh(int l,int r){
    ull res=0;l--;
    for(;r;r-=lowbit(r)) res^=sh[r];
    for(;l;l-=lowbit(l)) res^=sh[l];
    return res;
}
ull splitmix64(ull x) {
    x+= 0x9e3779b97f4a7c15;
    x=(x^(x>>30))*0xbf58476d1ce4e5b9;
    x=(x^(x>>27))*0x94d049bb133111eb;
    return x^(x>>31);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); 
    cin>>n>>m;
    for(int i=1;i<V;i++) h[i]=splitmix64(i+114514),sum[i]=(sum[i-1]^h[i]);
    for(int i=1;i<=n;i++) cin>>a[i],adda(i,a[i]),xorh(i,h[a[i]]);
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            int x,y;
            cin>>x>>y; 
            adda(x,-a[x]);
            xorh(x,h[a[x]]);
            adda(x,y);
            xorh(x,h[y]);
            a[x]=y;
        }
        else{
            int l,r;
            cin>>l>>r;
            int s=aska(l,r);
            if((2*s)%(r-l+1)){
                cout<<"yuanxing\n";
                continue;
            }
            s=(2*s)/(r-l+1)-r+l;
            if(s&1){
                cout<<"yuanxing\n";
                continue;
            }
            s/=2;
            if(askh(l,r)==(sum[s+r-l]^sum[s-1])) cout<<"damushen\n";
            else cout<<"yuanxing\n";
        }
    }
    return 0;
}

::::

CF1175F The Number of Subpermutations / P10833 [COTS 2023] 下 Niz

延续我们上一题的思路，我们可以 \Theta(1) 判断一个数列是否是排列。

考虑到一个序列中一定有一个 1，于是枚举所有的 a_i=1，从这个 i 开始向右枚举区间右端点 j>i，计算 \displaystyle m=\max_{k=i+1}^j a_k，则 m 也为区间长度。前缀和求出 \displaystyle x=\bigoplus_{p=j-m+1}^{j} h_{a_p}，其中 h_i 为随机权值。判断 x 是否等于 \displaystyle\bigoplus_{p=1}^m h_p，如果 a_j=1，停止枚举。这样可以求出所有最大值在 1 右侧的排列，反过来再做一遍，加上长度为 1 的排列即可。

::::success[AC Code] 注意位运算优先级。

#include<iostream>
#include<algorithm>
#include<vector>
#include<random>
#define int long long
using namespace std;
const int N=1e6+7;
mt19937_64 rd(114514);
int n,a[N],id[N],cnt,ans;
unsigned long long xors[N],x[N],h[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) h[i]=rd(),x[i]=x[i-1]^h[i];
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]==1) id[++cnt]=i;
        xors[i]=xors[i-1]^h[a[i]];
    }
    id[cnt+1]=n+1,id[0]=0;
    for(int i=1;i<=cnt;i++){
        int maxx=1;
        for(int r=id[i]+1;r<id[i+1];r++){
            maxx=max(maxx,a[r]);
            int l=r-maxx+1;
            if(l>id[i-1] && (xors[r]^xors[l-1])==x[maxx]) ans++;
        }
    }
    for(int i=cnt;i>=1;i--){
        int maxx=1;
        for(int l=id[i]-1;l>id[i-1];l--){
            maxx=max(maxx,a[l]);
            int r=l+maxx-1;
            if(r<id[i+1] && (xors[r]^xors[l-1])==x[maxx]) ans++;
        }
    }
    cout<<ans+cnt;
    return 0;
}

::::

P8819 [CSP-S 2022] 星战

对，又是这个题。

建议先阅读本文 Pt.2 \to 特征值哈希 \to 星战。假设你已经看完了这一段。

我们在特征值哈希处的做法是预处理来解决“在终点处批量修改起点”，哈希的还是出度。我们可以进一步，直接设计这样一个哈希函数：

即所有边起点的随机权值异或和，其中 G,V,E,h 分别为图、点集、边集、随机 64 位权值。

于是判定条件转化为：

即每个点都成为且仅成为了一次起点。但是注意如果一个点当了奇数次起点会被误判，所以顺便维护一下边的数量，必须额外判一下 |E_\text{now}|=n。

然后我们还是要预处理一下 v 作为终点的贡献 \text{contrib}(v)，维护一下 \text{contrib}_\text{now}(v)。下面几乎和特征值哈希做法一模一样：

操作 1：

操作 2：

操作 3：

操作 4：

就做完了。 ::::success[AC Code]

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<random>
#define int long long
#define ull unsigned long long
using namespace std;
const int N=5e5+7;
mt19937_64 rd(1145);
int n,m,q,in[N],nowin[N],cnt;
ull h[N],val[N],now[N],nowhs,keyhs;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    cnt=m;
    for(int i=1;i<=n;i++){
        h[i]=rd();
        keyhs^=h[i];
    }
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        val[v]^=h[u];
        in[v]++;
    }
    for(int i=1;i<=n;i++){
        now[i]=val[i];
        nowhs^=now[i];
        nowin[i]=in[i];
    }
    cin>>q;
    while(q--){
        int t,u,v;
        cin>>t;
        if(t==1){
            cin>>u>>v;
            nowhs^=h[u];
            now[v]^=h[u];
            cnt--;
            nowin[v]--;
        }
        else if(t==2){
            cin>>u;
            nowhs^=now[u];
            now[u]=0;
            cnt-=nowin[u];
            nowin[u]=0;
        }
        else if(t==3){
            cin>>u>>v;
            nowhs^=h[u];
            now[v]^=h[u];
            cnt++;
            nowin[v]++;
        }
        else if(t==4){
            cin>>u;
            nowhs^=(now[u]^val[u]);
            now[u]=val[u];
            cnt-=nowin[u];
            nowin[u]=in[u];
            cnt+=in[u];
        }
        if(nowhs==keyhs && cnt==n) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

::::

AT_abc455_g [ABC455G] Balanced Subarrays

我也不知道怎么想到的。 但是不到黑吧。

我不会数据结构所以考虑哈希瞎搞。（？