牛客多校graph games（部分分块+哈希）

https://ac.nowcoder.com/acm/contest/883/A

题目大意，给出一个无向图，设S(x)表示x的临近点集合，临近点即通过一条边直接相连的点。有两种操作，1是把边集合（读入顺序）从l到r的边状态反转（相连变断开，断开变相连），2是询问两个点的临近集是否相等。

这里首先涉及到的一个难点是如何表示临近集，我们采用异或哈希的方式，首先为所有点分配一个随机权值，这里用到了一个新版的随机函数

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
for(int i=1;i<=n;i++)
    val[i]=rng();

接下来我们把某个点的所有临近点的权值异或起来，作为它的临近集表示。异或哈希的大概原理是，原始权值在每个bit上01的概率相等，而异或过程对于每个bit产生01的概率也是等价的，所以能保证随机性。这个问题解决后，就能以O（1）时间判定临近集的相等。

接下来考虑如何维护翻转，一个简单的分块考虑是，对边集分块，最开始计算出每个块对每个点的影响（add数组）（O（m^1.5）），然后对于1操作，标记块的翻转，零碎的边直接计算出来；对于2操作，把所有翻转的块中对该点的影响都异或到现有答案上。这样两个操作的复杂度都是O（m^0.5），只可惜这样会超时，由于是多组数据，而我们在每组数据中都要对add数组进行整体清零，这个复杂度是m^0.5*n的，三四组数据估计就不行了。

所以考虑缩减add数组，我们发现，如果一个点的度数比较小，那么在计算它的临近集时可以挨个枚举相连的边，复杂度是和度数成正比的。因而我们考虑，只把度数大于sqrt（m）的点用add数组维护，这样的点总共不会超过2*sqrt（m）个。剩下的小点需要再维护一下零碎边的翻转性（e数组），同时块的翻转标记也会影响到它。

ps分块题的细节真的一不留神就写错……不过思路直接还是挺容易debug的

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+2;
const int maxm=2e5+2;

#define ll long long
#define sz(x) (int)x.size()
ll val[maxn],s[maxn];
struct edge{
    int u,v;
}es[maxm];
typedef pair<int,int> pir;
vector<pir> g[maxn];
bool big[maxn];
int cnt,mp[maxn];
ll add[500][1000];
int pos[maxm],tot;
int tag[500],e[maxm];
int n,m,q,t;
string ans;
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        int block=sqrt(m);
        tot=0;
        for(int i=1;i<=m;i++){
            if((i-1)%block==0)
                tot++;
            pos[i]=tot;
        }
        for(int i=1;i<=n;i++)
            g[i].clear();
        for(int i=1;i<=m;i++){
            cin>>es[i].u>>es[i].v;
            g[es[i].u].push_back(pir(es[i].v,i));
            g[es[i].v].push_back(pir(es[i].u,i));
        }
        memset(big,0,sizeof(big));
        cnt=0;
        for(int i=1;i<=n;i++)
            if(sz(g[i])>block){
               big[i]=1;
               mp[i]=++cnt;
            }
        mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
        for(int i=1;i<=n;i++)
            val[i]=rng();


        for(int i=1;i<=tot;i++){
            for(int j=1;j<=cnt;++j)
                add[i][j]=0;
            for(int j=(i-1)*block+1;j<=min(m,i*block);j++){
                int u=es[j].u,v=es[j].v;
                if(big[u])
                    add[i][mp[u]]^=val[v];
                if(big[v])
                    add[i][mp[v]]^=val[u];
            }
        }

        for(int i=1;i<=tot;i++)
            tag[i]=1;
        memset(s,0,sizeof(s));
        memset(e,0,sizeof(e));
        cin>>q;
        ans="";
        while(q--){
            int opt;
            cin>>opt;
            if(opt==1){
                int l,r;
                cin>>l>>r;
                int lp=pos[l],rp=pos[r];
                if(lp<rp){
                    for(int i=lp+1;i<rp;i++)
                        tag[i]^=1;
                    for(int i=l;i<=block*lp;i++){
                        int u=es[i].u,v=es[i].v;
                        e[i]^=1;
                        if(big[u])
                            s[u]^=val[v];
                        if(big[v])
                            s[v]^=val[u];
                    }
                    for(int i=block*(rp-1)+1;i<=min(block*rp,r);i++){
                        int u=es[i].u,v=es[i].v;
                        e[i]^=1;
                        if(big[u])
                            s[u]^=val[v];
                        if(big[v])
                            s[v]^=val[u];
                    }
                }else{
                    for(int i=l;i<=r;i++){
                        int u=es[i].u,v=es[i].v;
                        e[i]^=1;
                        if(big[u])
                            s[u]^=val[v];
                        if(big[v])
                            s[v]^=val[u];
                    }
                }
            }else{
                int u,v;
                cin>>u>>v;
                ll valu=s[u],valv=s[v];
                if(big[u]){
                    for(int i=1;i<=tot;i++){
                        if(tag[i])
                            valu^=add[i][mp[u]];
                    }
                }else{
                    for(int i=0,id,to;i<sz(g[u]);i++){
                        id=g[u][i].second,to=g[u][i].first;
                        if(e[id]^tag[pos[id]]){
                            valu^=val[to];
                        }
                    }
                }
                if(big[v]){
                    for(int i=1;i<=tot;i++){
                        if(tag[i])
                            valv^=add[i][mp[v]];
                    }
                }else{
                    for(int i=0,id,to;i<sz(g[v]);i++){
                        id=g[v][i].second,to=g[v][i].first;
                        if(e[id]^tag[pos[id]]){
                            valv^=val[to];
                        }
                    }
                }
                if(valu==valv){
                    ans+='1';
                }else
                    ans+='0';
            }
        }
        cout<<ans<<endl;
    }
}
/*
1
5 4
1 2
1 3
4 2
4 3
3
2 1 4
1 1 1
2 1 2

*/