杭电第一场1005 Finding a MEX 树上分块

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6756
题目大意：
有一个n点，m条边的无向图，每个点有一个权值。现在有两个操作：
1 x y：把x点的权值修改为y
2 x : 查询x的的邻接点的权值中没有出现的最小非负整数。

思路：前几天正好补了一个分块的题，今天就遇到了。
我们考虑按点的度数进行维护。
我们考虑用权值线段树去维护每个点的mex。

对于修改x：
我们去遍历它d[y]>sqrt(n)的邻接点,最多有sqrt(n)个，每个在线段树上修改，复杂度:O(sqrt(n) * logn)
对于查询x：
如果d[u]<=sqrt(n)那么我们暴力每个点查询就可以了。复杂度:O(sqrt(n))
如果d[u]>sqrt(n)那么我们直接在线段树查询就可以了，复杂度:O(sqrt(n) * logn)
如果就一直T到怀疑人生。这个地方用线段树常树太大。

我们考虑一些其他的维护方法：
1.树状数组（sqrt(n) * logn）:二分结果，前缀和查询。因为添加是O(sqrt(n) * logn)和查询(logn * log n)是分开的，那么复杂度还是添加的：sqrt(n) * logn
2.树状数组 （sqrt(n) * logn）：我们可以直接在树上二分，标程的做法
3.set（sqrt(n) * logn）：保存没有被占用的点。添加为set中删除，删除为set中添加。
3.分块(sqrt(n)): 我们根据上面的复杂度分析可以知道如果数据结构修改是O(1)，查询是O(sqrt(n))，那么总的复杂度就是O(n * sqrt(n))。

具体做法：
我们按权值分块，用laz数组维护这个块非o的数量。用桶记一下个数，O(1)修改
查询到每一块if laz[i]!=len， 说明这个块有没有被占用的，去块里找，复杂度：O(sqrt(n))

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

int f[200015], d[200015];
vector<int> G[200015], son[200015], pos;
int vis[200015];
struct FK{
    vector<int> w[200015], laz[200015];
    int len;
    void init(int n){
        len=sqrt(n)+1;
        for(int i=1; i<=n; i++){
            w[i].clear(); w[i].resize(2*d[i]+5);
            laz[i].clear(); laz[i].resize(2*d[i]+5);
        }
        for(int i=1; i<=n; i++){
            if(d[i]>len){
                int siz=d[i]/len;
                for(int k=0; k<=siz; k++){
                    laz[i][k]=len;
                }
            }
        }
    }
    void up_data(int pos, int x, int y){//x->y
        if(x<=d[pos]){
            w[pos][x]--;
            if(w[pos][x]==0){
                laz[pos][x/len]++;
            }

        }
        if(y<=d[pos]){
            w[pos][y]++;
            if(w[pos][y]==1){
                laz[pos][y/len]--;
            }
        }
    }
    int qurey(int pos){
        int siz=d[pos]/len;
        int p=siz;
        for(int i=0; i<=siz; i++){
            if(laz[pos][i]){
                p=i; break;
            }
        }
        for(int i=len*p; i<len*(p+1); i++){
            if(!w[pos][i]){
                return i;
            }
        }
    }

}F;

int main(){

    int t; scanf("%d", &t);
    while(t--){
        int n, m, q, x, y, z; scanf("%d%d", &n, &m);
        for(int i=1; i<=n; i++){
            f[i]=d[i]=0;
            G[i].clear();
            son[i].clear();
        }
        for(int i=1; i<=n; i++){
            scanf("%d", &f[i]);
        }
        for(int i=1; i<=m; i++){
            scanf("%d%d", &x, &y);
            G[x].push_back(y);
            G[y].push_back(x);
            d[x]++, d[y]++;
        }
        for(int i=1; i<=n; i++){
            sort(G[i].begin(), G[i].end(), [](int &a, int &b){return d[a]<d[b];});
        }
        int len=sqrt(n)+1;
        F.init(n);
        for(int i=1; i<=n; i++){
            for(auto x: G[i]){
                if(d[x]>len){
                    son[i].push_back(x);
                }
            }
        }
        for(int i=1; i<=n; i++){
            for(auto x: son[i]){
                F.up_data(x, 1e5+5, f[i]);
            }
        }

        scanf("%d", &q);
        while(q--){
            scanf("%d%d", &x, &y);
            if(x==1){
                scanf("%d", &z);
                for(auto x: son[y]){
                    if(d[x]>len){
                        F.up_data(x, f[y], z);
                    }
                }
                f[y]=z;
            }
            else{
                if(d[y]>len){
                    for(auto x: son[y]){
                        F.up_data(x, 1e5+5, f[x]);
                    }
                    printf("%d\n", F.qurey(y));
                    for(auto x: son[y]){
                        F.up_data(x, f[x], 1e5+5);
                    }
                }
                else{
                    for(int i=0; i<G[y].size(); i++){
                        if(f[G[y][i]]<n+5){
                            pos.push_back(f[G[y][i]]);
                            vis[f[G[y][i]]]=1;
                        }
                    }
                    for(int i=0; i<=n+5; i++){
                        if(!vis[i]){
                            printf("%d\n", i);
                            break;
                        }
                    }
                    for(auto x: pos){
                        vis[x]=0;
                    }
                    pos.clear();
                }
            }
        }
    }

    return 0;
}