给定一张\(n\)个点\(m\)条边的无向图\(G=(V,E)\)。每个点\(u\)有一个点权\(a_u\)。令\(S_u=\{a_v|(u,v)\in E\}\)。令\(F_u=\operatorname{mex}(S_u)\)，其中\(\operatorname{mex}\)表示最小的、在集合里没出现过的，非负整数。
接下来会给出\(q\)次操作，操作有两种：
请你对所有操作\(2\)输出答案。
数据范围：\(1\leq n,m\leq 10^5\)，\(0\leq a_u\leq 10^9\)，\(1\leq q\leq 10^5\)。
设置一个值\(B\)。按点的度数\(>B\)或\(\leq B\)，将点分为“大点”和“小点”。每个小点的邻居数不超过\(B\)，大点的总数不超过\(\frac{n}{B}\)，这对我们来说是很好的性质。
对于一次修改操作，如果被修改的点是小点，则可以直接暴力枚举它的所有邻居，进行修改。如果被修改的点是大点，则什么也不做（有点像线段树的懒标记，先放着，等查询的时候再说）。
查询时，所有小点对当前点的影响已经维护好了。考虑大点的影响，暴力枚举所有与当前点相邻的大点，如果它被修改过，更新当前点的\(F\)值即可。因为大点的总数只有\(O(\frac{n}{B})\)个，所以一次操作最多做\(O(\frac{n}{B})\)次修改。
那么问题就转化为，如何维护出每个点的\(S\)集合，支持加入一个值、删除一个值、查询\(\operatorname{mex}\)。如果用动态开点线段树（给图上每个点都开一棵），则一次修改时间复杂度是\(O(\log a)\)的，一次查询时间复杂度是\(O(1)\)的。空间复杂度理论上最大甚至高达\(O((n+q)(B+\frac{n}{B})\log a)\)。如果\(B\)取\(\sqrt{n}\)，则时间、空间复杂度都是\(O(n\sqrt{n}\log a)\)的。虽然实际上可以AC，但还可以继续优化。
我们发现，一个点的\(F_u\)值（也就是\(\operatorname{mex}(S_u)\)），不会超过\(\operatorname{deg}(u)\)（因为\(S_u\)的大小不超过\(\operatorname{deg}(u)\)）。所以线段树的值域只需要开到\(n\)，时、空复杂度优化为\(O(n\sqrt{n}\log n)\)。
进一步优化，考虑不用线段树。我们发现，线段树的特点是，修改较慢，查询很快（是\(O(1)\)的）。但是我们恰恰需要较快的修改（因为修改操作需要进行\(O((n+q)\sqrt{n})\)次），而查询则可以慢一点（因为只会做\(O(q)\)次查询）。
于是考虑用分块替代线段树。对值域分块，用数组记录每个值的出现次数，和每个块内有多少种不同的值，这样修改是\(O(1)\)的。因为每个点值域是\(\operatorname{deg}(u)\)的，所以记录这些需要的总空间就是\(\sum \operatorname{deg}(u)=O(m)\)的。查询时，暴力枚举所有的块，时间复杂度是\(O(\sqrt{\operatorname{deg}(u)})=O(\sqrt{n})\)的。于是，我们通过分块，牺牲了查询的复杂度，实现了\(O(1)\)修改。
总时间复杂度降为\(O((n+q)\sqrt{n})\)。
参考代码：
//problem:1006
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T>inline void ckmax(T& x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T& x,T y){x=(y<x?y:x);}
const int B=300;
const int MAXN=1e5;
int n,m,q,a[MAXN+5],deg[MAXN+5];
bool is_big[MAXN+5];
vector<int>G[MAXN+5],cnt[MAXN+5],tag[MAXN+5];
vector<pii>big_nb[MAXN+5];//big neighbour
inline void ins(int u,int x){
ckmin(x,deg[u]);
cnt[u][x]++;
if(cnt[u][x]==1)
tag[u][x/B]++;
}
inline void del(int u,int x){
ckmin(x,deg[u]);
cnt[u][x]--;
if(cnt[u][x]==0){
tag[u][x/B]--;
}
}
int query_mex(int u){
for(int i=0;i<=deg[u];i+=B){
int j=min(i+B-1,deg[u]);
if(tag[u][i/B] < j-i+1){
for(int k=i;k<=j;++k)
if(!cnt[u][k])
return k;
throw;
}
}
throw;
}
void solve_case(){
cin>>n>>m;
for(int i=1;i<=n;++i){
deg[i]=0;
is_big[i]=false;
vector<int>().swap(G[i]);
vector<int>().swap(cnt[i]);
vector<int>().swap(tag[i]);
vector<pii>().swap(big_nb[i]);
//相当于 v.clear()
}
for(int i=1;i<=n;++i)
cin>>a[i];
for(int i=1;i<=m;++i){
int u,v; cin>>u>>v;
G[u].pb(v); G[v].pb(u);
deg[u]++; deg[v]++;
}
for(int i=1;i<=n;++i){
is_big[i]=(deg[i]>B);
cnt[i].resize(deg[i]+1);
tag[i].resize(deg[i]/B+1);
}
for(int u=1;u<=n;++u){
for(int i=0;i<SZ(G[u]);++i){
int v=G[u][i];
if(is_big[v])
big_nb[u].pb(mk(v,a[v]));
ins(u,a[v]);
}
}
cin>>q;
for(int tq=1;tq<=q;++tq){
int op; cin>>op;
if(op==1){
int u,new_a; cin>>u>>new_a;
if(is_big[u]){
a[u]=new_a;
}
else{
for(int i=0;i<SZ(G[u]);++i){
int v=G[u][i];
del(v,a[u]);
ins(v,new_a);
}
a[u]=new_a;
}
}
else{
int u; cin>>u;
for(int i=0;i<SZ(big_nb[u]);++i){
int v=big_nb[u][i].fi;
int old_a=big_nb[u][i].se;
if(old_a != a[v]){
del(u,old_a);
ins(u,a[v]);
big_nb[u][i].se=a[v];
}
}
cout<<query_mex(u)<<endl;
}
}
}
int main(){
int T;cin>>T;while(T--){
solve_case();
}
return 0;
}
【2020杭电多校round1 1006】HDU6766 Finding a MEX
原文：https://www.cnblogs.com/dysyn1314/p/13357864.html