给一个无向图，0≤n,m≤1e5(n表示点，m表示边)；
每个点有权值。有0≤q≤1e5次询问，2种询问方式如下：
比如：u相连的点权值为{0，1，2，3，5}，那么4就是第一个没有出现的值。mex（u）=4;
原题链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1006&cid=879
这道题是一道银牌题（没做出来）
图得边已经固定了最多1e5，每一条边会产生2度。（u--v） u,v各增加1度。也就是最大为2e5度。
那其实计算每一个平均每个点能连接的度数为√2e5≈450。这个平均求出来的意义在于找出那些菊花点最多
有少个。平均是450，那么大于450度的点绝对不会超过450。然后题解给的350主要是没管度数是否×2。
（当然对结果不影响，由于我是根据题解的代码自己写的，下面用350讲解）
那: 2e5/350=571 即 超过350度的点不会大于571个点。那就好做了
我们把点分为两批。度数大于350的点我们把他作为大点。度数小于350的点我们左右小点。
由上述算法我们可以看到无论是查询还是修改我们的复杂度都小于600次复杂度也就为O(q√m)
哪还有查询和插入的复杂度没有计算。
这里我们用树状数组求mex。
首先给每一个点都分配一颗等于他度数大小的树状数组。
为什么是每一个等于他啦？想想mex是求第一个不会出现的整数。那度数为5的点，他的答案可能会超过5吗？他最大为5。前面把0 1 2 3 4占完了。
所以权值大于度数的值我们根本没有记录的意义。(这样在空间上就可行了)
其次怎么求？
我们把每个点的所有度数值在树状数组上加1。为什么要加1啦？
比如：u由5度。那对应的数组C[6]={0,1,1,1,1,1,1} 第一个为0是因为树状数组下标不能为0，无法修改，找到答案在-1就行了。
然后假设与权值为0 1 3的点相连，那么将这些点置0。那就变成了 {0 0 0 1 0 1 1}，这样你就发现其实就等于树状数组第一个区间求和为1的下标。
这里就是3，答案为3-1=2.树状数组有种在logn求出第一个区间和为x（这里求mex，也就是x==1）的算法。有兴趣可以看看代码如何实现的。
到此位置。思路就讲完了，然后代码如下，结合起来看就应该比较容易了
#include <bits/stdc++.h> using namespace std; const int N = 110000; const int M = 350; int A[N]; vector<int> con[N], adj[N]; struct Query { int type, u, x; Query(int type = 0, int u = 0, int x = 0) : type(type), u(u), x(x) {} } Q[N]; int Array[N * M * 2], hello[N * M * 2]; int *BIT[N], *frq[N], lim[N]; inline void add(int id, int u, int x) { for (int i = u; i <= lim[id]; i += i & -i) BIT[id][i] += x; } inline int get(int id, int u) { int ret = 0; for (int i = u; i > 0; i -= i & -i) ret += BIT[id][i]; return ret; } inline int get_lower_bound(int id, int s) { int ret = 0; for (int i = 31 - __builtin_clz(lim[id]); i >= 0; i--) { ret ^= 1<<i; if (ret > lim[id]) { ret ^= 1<<i; continue; } s -= BIT[id][ret]; if (s <= 0) { s += BIT[id][ret]; ret ^= 1<<i; } } return ++ret; } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); string s; cin>>s; int tcase; cin >> tcase; while (tcase--) { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> A[i]; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; con[u].push_back(v), con[v].push_back(u); } for (int i = 1; i <= n; i++) { for (int v : con[i]) { if (con[v].size() >= M) adj[i].push_back(v); } } int q; cin >> q; for (int i = 0; i < q; i++) { cin >> Q[i].type >> Q[i].u; if (Q[i].type == 1) { cin >> Q[i].x; } } for (int i = 1; i <= n; i++) lim[i] = con[i].size() + 1; int *p = Array, *qq = hello; for (int i = 1; i <= n; i++) { BIT[i] = p, p += lim[i] + 1; frq[i] = qq, qq += lim[i] + 1; } for (int i = 1; i <= n; i++) for (int j = 1; j <= lim[i]; j++) add(i, j, 1); for (int i = 1; i <= n; i++) if (con[i].size() < M) { for (int v : con[i]) { int val = A[i]; if (val <= lim[v]) { if (!frq[v][val]) add(v, val + 1, -1); frq[v][val]++; } } } for (int i = 0; i < q; i++) { if (Q[i].type == 1) { if (con[Q[i].u].size() < M) { int val = A[Q[i].u]; for (int v : con[Q[i].u]) { if (val <= lim[v]) { frq[v][val]--; if (!frq[v][val]) add(v, val + 1, 1); } if (Q[i].x <= lim[v]) { if (!frq[v][Q[i].x]) add(v, Q[i].x + 1, -1); frq[v][Q[i].x]++; } } A[Q[i].u] = Q[i].x; } else { A[Q[i].u] = Q[i].x; } } else { for (int v : adj[Q[i].u]) { if (A[v] <= lim[Q[i].u]) { if (!frq[Q[i].u][A[v]]) add(Q[i].u, A[v] + 1, -1); frq[Q[i].u][A[v]]++; } } cout << get_lower_bound(Q[i].u, 1) - 1 << "\n"; for (int v : adj[Q[i].u]) { if (A[v] <= lim[Q[i].u]) { frq[Q[i].u][A[v]]--; if (!frq[Q[i].u][A[v]]) add(Q[i].u, A[v] + 1, 1); } } } } for (int i = 1; i <= n; i++) { con[i].clear(), adj[i].clear(); for (int j = 0; j <= lim[i]; j++) BIT[i][j] = frq[i][j] = 0; lim[i] = 0; } } return 0; }
代码是题解代码。比我自己写的要工整些，有问题欢迎指出。
原文：https://www.cnblogs.com/grisaia/p/13363307.html