2020 Multi-University Training Contest 1 ---- HDU--6756、Finding a MEX（图上根据度数分块）

题面：

题意：
给定一张图，点有点权，有两种操作：
（1）将 x 点的点权改为 y。
（2）查询与 x 相连的点的点权的 mex 。（这里的mex就是找没有出现过的最小非负整数）
这个图应该是简单图，没有自环和重边。

题解：
（1）每次查询点 x 的mex一定出现在 0–d [ x ] 之间，其中 d [ x ] 表示 x 的度数。
（2）度数大于等于 $\sqrt{n}$ 的点的一定小于等于 $\sqrt{n}$ 个。

对于每个度数大于等于 $\sqrt{n}$ 的点，我们维护一个 d [ x ] 大小的树状数组。如果某个val出现过，就在这个树状数组的val处+1。查询这个点的mex时，用倍增logn即可查询。这样可以在一个log的时间复杂度内维护这个节点的mex。

对于每个节点，我们维护与其相连的节点中那些度数大于等于 $\sqrt{n}$ 的节点。这样的节点一定小于等于 $\sqrt{n}$ 个。初始时我们遍历每条边，对于每个节点维护与其相连的节点中那些度数大于等于 $\sqrt{n}$ 的节点并且对于每个度数大于等于 $\sqrt{n}$ 维护其树状数组。

考虑操作1，将 x 点的权值修改为 y ：
我们维护与 x 相连的度数大于等于 $\sqrt{n}$ 的树状数组中点x的贡献。可以证明，每次操作1的时间复杂度时 $O (\sqrt{n} l o g n)$ 的。

考虑操作2，查询 x 点的mex：
如果 d [ x ] < $\sqrt{n}$ ，那么我们暴力 $O (\sqrt{n})$ 找mex即可
如果 d [ x ] >= $\sqrt{n}$ ，这个时候我们已经维护了这个节点的树状数组， $O (l o g n)$ 查询即可。

总的时间复杂度为：
$O (n \sqrt{n} <mtext> </mtext> l o g n)$

虽然时间复杂度比较大，可能过不去，但是要敢莽。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+9;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=200100;
const int maxm=100100;
const int up=100000;

vector<int>vc[maxn];
int d[maxn],val[maxn];
int n,m,sq;
vector<int>c[maxn],cc[maxn];
bool in[maxn];

int head[maxn],ver[maxn],nt[maxn],tot=1;
void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}


void add(int id,int x,int val,int n)
{
    if(x>n) return ;
    cc[id][x]+=val;
    if(x==0) return ;
    if(val>0&&cc[id][x]==1||val<0&&cc[id][x]==0)
        for(;x<=n;x+=x&(-x))
            c[id][x]+=val;
}

int ask(int id,int n)
{
    if(cc[id][0]==0) return 0;
    int pos=0,sum=0,t=log2(n)+1;
    for(int i=t;i>=0;i--)
    {
        if(pos+(1<<i)<=n&&sum+c[id][pos+(1<<i)]==pos+(1<<i))
            sum+=c[id][pos+(1<<i)],pos+=(1<<i);
    }
    return pos+1;
}

void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        vc[i].clear();
        c[i].clear();
        cc[i].clear();
        head[i]=d[i]=0;
    }
    tot=1;
    sq=sqrt(n)+1;
}

int ask1(int x)
{
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(val[y]<=d[x]) in[val[y]]=true;
    }
    int ans=-1;
    for(int i=0;;i++)
    {
        if(in[i]==false)
        {
            ans=i;
            break;
        }
    }
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(val[y]<=d[x]) in[val[y]]=false;
    }
    return ans;
}

int ask2(int x)
{
    return ask(x,d[x]);
}

int main(void)
{
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d%d",&n,&m);
        init(n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&val[i]);
        }
        int x,y;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
            d[x]++,d[y]++;
        }
        for(int i=1;i<=n;i++)
        {
            if(d[i]>=sq)
            {
                c[i]=vector<int>(d[i]+1,0);
                cc[i]=vector<int>(d[i]+1,0);
            }
        }
        for(int x=1;x<=n;x++)
        {
            for(int i=head[x];i;i=nt[i])
            {
                int y=ver[i];
                if(d[y]>=sq)
                {
                    add(y,val[x],1,d[y]);
                    vc[x].pb(y);
                }
            }

        }
        int q,op;
        scanf("%d",&q);
        for(int i=1;i<=q;i++)
        {
            scanf("%d",&op);
            if(op==1)
            {
                scanf("%d%d",&x,&y);
                for(int i=0;i<vc[x].size();i++)
                {
                    int yy=vc[x][i];
                    add(yy,val[x],-1,d[yy]);
                    add(yy,y,1,d[yy]);
                }
                val[x]=y;
            }
            else
            {
                scanf("%d",&x);
                if(d[x]<sq) printf("%d\n",ask1(x));
                else printf("%d\n",ask2(x));
            }
        }
    }
    return 0;
}