部分分块

Posted on | In

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

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

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

1
2
3
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的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#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

*/