和哈希与随机赋权哈希

1. 定义

和哈希，又称集合哈希。

为什么叫集合哈希呢，集合与序列的不同点在于，集合是无序的，也就是说，序列要求每个位置一一相等，而集合只需要对应的元素出现次数相等即可。

我们引入一个问题：

给定一个长为$n$ 的序列$A$，每次给出两个长度相等的区间$[l_{1},r_{1}],[l_{2},r_{2}]$ 里面的数排序后是否完全相等，我们就可以说$[2,3,1,4,5]$ 和$[5,4,3,2,1]$ 是相同的。

这种情况我们很难找到一个数据结构来支持这样的查询操作，我们发现如果称两个区间相同，那么这个区间里的每一个数的出现次数和另外一个区间中这个数的出现次数相同。

我们考虑，只需要次数相同就可以的话，那么也就是说，这哈希值之和我数值具体是多少，而和位置无关，那么两个区间相等的必要条件就是$h(l_{1},r_{1})=h(l_{2},r_{2})$，现在问题在于如何设计函数使得冲突尽量小。

此时哈希函数以如下表示：

$$h(\left\{ A \right\})=\sum\limits_{i=1}^n h'(a_{x})$$

那么我们有方法，就是给每一个元素赋值一个随机数$r_{x}$，让后$h(\left\{ A \right\})=\sum\limits_{i=1}^n r_{a_{x}}$。只要随机数质量高并且值域大，冲突的概率还是比较小的。当然有的时候会被卡，考虑多做几次即可。

2. 例题

Problem #115 - ECNU Online Judge

给一个长度为$n$ 的正整数数列$a_{i}$，问有多少连续子数列，满足每个数字的出现次数均为偶数。

对于一个区间，如果每个出现次数为偶数，那么一定有$\oplus_{i=l}^r a_{i}=0$，但是这并不代表出现次数一定为偶数，考虑给每个$a_{i}$ 随机赋值，这样进行操作即可。

现在问题转化为当前位置$i$ 有多少前缀异或和等于$pre$，其中$pre$ 表示当前前缀异或，直接扫一遍就可以了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=3e5+15;
int n,a[MN],ans,st;
mt19937 mt;
map<int,int> mp,cnt;

signed main(){
    mt.seed(time(0));
    cin>>n;
    st=mt();
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(!mp.count(a[i])) mp[a[i]]=(st+=mt());
        a[i]=mp[a[i]];
    }
    int pre=0;
    cnt[0]=1;
    for(int i=1;i<=n;i++){
        pre^=a[i];
        ans+=cnt[pre];
        cnt[pre]++;
    }
    cout<<ans;
    return 0;
}

[CSP-S 2022] 星战

给定一个$n$ 个点$m$ 条边的有向图，支持四种操作：

1. 删除某条边；
2. 删除某个点的所有入边；
3. 恢复某条边；
4. 恢复某个点的所有入边。

每次操作后询问当前图是否满足：

1. 所有点出度均为 1；
2. 所有点都处于一个环中（即基环内向树森林，每个连通块恰有一个环）。

我们考虑，这个反击图是内向基环树森林，利用性质 所有点出度均为 1。那么既然是有向图，其实只要满足出度都为 1，就能判断。

暴力维护出度显然是$O(nm)$。

我们发现，维护出度是很难受的，因为删入边你还需要把遍历边才能把入边全部标记上。但是维护入度很好做啊，我们不妨令原图节点$u$ 的入度为$g(u)$，而修改后的出度为$c(u)$，初始情况下$g(u)=c(u)$，而对于这四种操作有：

• $op=1,c(u)\leftarrow c(u)-1$。
• $op=2,c(u)\leftarrow 0$。
• $op=3,c(u)\leftarrow c(u)+1$。
• $op=4,c(u)\leftarrow g(u)$。

可以发现，一张图中的出度之和与入度之和是相等的，问题转化为判断和入度和和出度和为$n$，但是这是必要条件，我们不能推出每个节点的出度均为$1$，但是我们利用和哈希就可以做到。

对于每一个节点$u$，我们不妨给他随机赋值$h(u)$，我们令$g(v)=\sum\limits_{(u,v)\in E} h(u)$，我们可以有新的操作：

• $op=1,c(u)\leftarrow c(u)-h(u)$。
• $op=2,c(u)\leftarrow 0$。
• $op=3,c(u)\leftarrow c(u)+h(u)$。
• $op=4,c(u)\leftarrow g(u)$。

维护$\sum\limits c(u)$ 即可，如果有$\sum\limits c(u)=\sum\limits h(u)$，那么原图很大概率是合法图：

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=5e5+15;
int n,m,q,hsum,now,st,h[MN],g[MN],c[MN];
mt19937 mt;

signed main(){
    mt.seed(time(0));
    cin>>n>>m;
    st=mt();
    for(int i=1;i<=n;i++){
        h[i]=(st+=mt());
        hsum+=h[i];
    }
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[v]+=h[u];
        c[v]=g[v];
        now+=h[u];
    }
    cin>>q;
    while(q--){
        int op,u,v;
        cin>>op;
        if(op==1){
            cin>>u>>v;
            now-=h[u];
            c[v]-=h[u];
        }
        if(op==2){
            cin>>u;
            now-=c[u];
            c[u]=0;
        }
        if(op==3){
            cin>>u>>v;
            now+=h[u];
            c[v]+=h[u];
        }
        if(op==4){
            cin>>u;
            now+=g[u]-c[u];
            c[u]=g[u];
        }
        if(now==hsum){
            cout<<"YES\n";
        }else cout<<"NO\n";
    }
    return 0;
}

CF1746F

发现直接在线做真的很不好做，考虑离线下来。注意到源题目只关心出现次数，而不关心具体取值，考虑和哈希。给每一个元素赋一个随机权值，那么每次询问我们查询$sum=\sum\limits_{i=l}^r h_{i}$，若$k|s$ 那么一定不满足，但是对于$k$ 不整除$s$ 这是一个必要条件，可能不成立，我们考虑多用随机值映射几次，那么成功概率就会非常高。

接下来我们只需要一个数据结构支持单调修改，区间和查询，树状数组即可，注意到答案和$a_{i}$ 具体取值无关，考虑离散化防止爆炸：

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=2e6+15,MOD=1e9+7;
int n,q,a[MN],b[MN],c[MN],rd[MN],tot,op[MN],L[MN],R[MN],K[MN];
bool ans[MN];
mt19937 mt;
unordered_map<int,int> mp;

namespace ly
{
    namespace IO
    {
        #ifndef LOCAL
            constexpr auto maxn=1<<20;
            char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(out,1,p3-out,stdout))
            #define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        namespace usr
        {
            template<typename type>
            inline type read(type &x)
            {
                x=0;bool flag(0);char ch=getchar();
                while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
                while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
                return flag?x=-x:x;
            }
            template<typename type>
            inline void write(type x)
            {
                x<0?x=-x,putchar('-'):0;
                static short Stack[50],top(0);
                do Stack[++top]=x%10,x/=10;while(x);
                while(top) putchar(Stack[top--]|48);
            }
            inline char read(char &x){do x=getchar();while(isspace(x));return x;}
            inline char write(const char &x){return putchar(x);}
            inline void read(char *x){static char ch;read(ch);do *(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
            template<typename type>inline void write(type *x){while(*x)putchar(*(x++));}
            inline void read(string &x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
            inline void write(const string &x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
            template<typename type,typename...T>inline void read(type &x,T&...y){read(x),read(y...);}
            template<typename type,typename...T>
            inline void write(const type &x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
            template<typename type>
            inline void put(const type &x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }using namespace IO::usr;
}using namespace ly::IO::usr;


struct BIT{
    int t[MN];

    int lowbit(int x){ return x&-x; }

    int query(int x){
        int ret=0;
        while(x){
            ret+=t[x];
            x-=lowbit(x);
        }
        return ret;
    }

    int query(int fl,int fr){
        return query(fr)-query(fl-1);
    }

    void modify(int x,int k){
        while(x<MN){
            t[x]+=k;
            x+=lowbit(x);
        }
    }

    void clear(){
        memset(t,0,sizeof(t));
    }

}t;



signed main(){
    mt.seed(time(0));
    int tim=clock();
    read(n,q);
    for(int i=1;i<=n;i++){
        read(a[i]);
        b[++tot]=a[i];
    }
    for(int i=1;i<=q;i++){
        read(op[i],L[i],R[i]);
        if(op[i]==1){
            b[++tot]=R[i];
        }
        else{
            read(K[i]);
            ans[i]=(R[i]-L[i]+1)%K[i]==0;
        }
    }
    sort(b+1,b+1+tot);
    tot=unique(b+1,b+1+tot)-b-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
    }
    for(int i=1;i<=q;i++){
        if(op[i]==1) R[i]=lower_bound(b+1,b+1+tot,R[i])-b;
    }
    for(;1.0*clock()-tim<=2.8*CLOCKS_PER_SEC;){
        t.clear();
        for(int i=0;i<=tot;i++){
            mp[i]=mt()%MOD;
        }
        for(int i=1;i<=n;i++) c[i]=mp[a[i]];
        for(int i=1;i<=n;i++) t.modify(i,c[i]);
        for(int i=1;i<=q;i++){
            if(op[i]==1){
                t.modify(L[i],mp[R[i]]-c[L[i]]);
                c[L[i]]=mp[R[i]];
            }else if(t.query(L[i],R[i])%K[i]) ans[i]=0;
        }
    }
    for(int i=1;i<=q;i++){
        if(op[i]!=1){
            put((ans[i]?"YES":"NO"));
        }
    }
    return 0;
}

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

重排为值域上连续的一段其实就是数值相邻，那么实际上数值相邻我们不关心数值具体是什么，我们只需要考虑它们能不能相邻就可以了，考虑随机赋权哈希，那么在值域连续的情况下。假设我们查询的区间随机数为$p_2,p_3,p_4$，那么通过前缀异或和算出$p_{2}\oplus p_{3}\oplus p_{4}$，若区间三个随机数异或和等于$p_{2}\oplus p_{3}\oplus p_{4}$，我们就认为这个区间是连续的。前缀异或和和映射前缀异或和可以用树状数组维护。

首先要离散化，但是不能瞎离散化，因为离散化后的数是连续的，我们可以考虑将离散化的时候多把每个值加 1 的数放到离散化数组里，这样本来就不连续的数离散化之后也不连续。

让后映射的数最好用 unsigned long long 自然溢出，这样的情况下极其难被 hack。若被卡随机数种子，考虑利用 random_device 这个玩意，在 Linux 下实现是一个真随机数生成器，从系统的熵池获取数据，通常用于为其他随机数引擎提供种子。这样能被 hack 概率可以忽略。

推荐使用茅台 19937 产随机数和 time(0) 初始化种子。

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
constexpr int MN=3e6+15;
int n,m,tot,a[MN],b[MN],op[MN],x[MN],y[MN];
ull rd[MN],pre[MN];
mt19937 mt; // 茅台 19937 产

struct BITsum{
    int t[MN];

    int lowbit(int x){return x&-x;}

    int query(int x){
        int ret=0;
        while(x){
            ret+=t[x];
            x-=lowbit(x);
        }
        return ret;
    }

    void modify(int x,int k){
        while(x<MN){
            t[x]+=k;
            x+=lowbit(x);
        }
    }
}t1;

struct BITXor{
    ull t[MN];

    int lowbit(int x){
        return x&-x;
    }

    ull query(int x){
        int ret=0;
        while(x){
            ret^=t[x];
            x-=lowbit(x);
        }
        return ret;
    }

    void modify(int x,ull k){
        while(x<MN){
            t[x]^=k;
            x+=lowbit(x);
        }
    }

}t2;

signed main(){
    mt.seed(time(0));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[++tot]=a[i];
        b[++tot]=a[i]+1;
    }
    for(int i=1;i<=m;i++){
        cin>>op[i]>>x[i]>>y[i];
        if(op[i]==1) b[++tot]=y[i]+1,b[++tot]=y[i];
    }
    sort(b+1,b+tot+1);
    tot=unique(b+1,b+1+tot)-b-1;
    rd[0]=mt();
    for(ull i=1,st=rd[0];i<=tot;i++){
        rd[i]=(st+=mt());
        pre[i]=pre[i-1]^rd[i];
    }
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
        t1.modify(i,a[i]);
        t2.modify(i,rd[a[i]]);
    }
    for(int i=1;i<=m;i++){
        if(op[i]==1){
            y[i]=lower_bound(b+1,b+1+tot,y[i])-b;
            t1.modify(x[i],y[i]-a[x[i]]);
            t2.modify(x[i],rd[y[i]]^rd[a[x[i]]]);
            a[x[i]]=y[i];
        }else{
            int mid=(t1.query(y[i])-t1.query(x[i]-1))/(y[i]-x[i]+1);
            int l,r;
            l=mid-(y[i]-x[i])/2;
            if((y[i]-x[i])&1) r=mid+(y[i]-x[i])/2+1;
            else r=mid+(y[i]-x[i])/2;
            if(l<=0||r>=tot) cout<<"yuanxing\n";
            else if((t2.query(y[i])^t2.query(x[i]-1))==(pre[r]^pre[l-1])){
                cout<<"damushen\n";
            } else cout<<"yuanxing\n";
        }
    }
    return 0;
}

3. 后言

属于是乱搞操作，但是又没有那么乱搞哈哈哈，学到也是赚到 lol。