是个树状数组好题,但是我对建立多个树状数组并不是太了解写法,所以自己手写一下.
题目给定n个点,以及他们代表的数,然后给你m条边,然后支持两种操作,1是修改,2是查询.修改是把u节点的值改成x.查询是查询与u节点相邻点的mex.
思路:思路很清晰,考虑每个节点连接sqrt(m)的数量不可能超过sqrt(m)个,我们将点分为重点,轻点.重点就是超过sqrt(m)个的点,轻点就是没超过sqrt(m)的点.然后对于重点我们二分树状数组解决,对于轻点我们直接暴力求解,此外对于修改操作,对于其连接点是重点,我们要对其连接点的树状数组进行单点修改,且改变它本身的权值,对于轻点来说直接改变自己的权值即可.

#include <bits/stdc++.h>
#define debug cout<<"***" 
using namespace std;
const int N=3e5+5;
vector<int>v[N],cnt[N],tree[N],G[N];
int zero[N],vis[N],w[N];
inline int lowbit(int x)
{
    return x&(-x);
}

inline void add(int pos,int val,int id)
{ 
    while(pos<G[id].size()+5)
    {
        tree[id][pos]+=val;
        pos+=lowbit(pos);
    }
}

inline int get_sum(int pos,int id)
{
    int res=0;
    while(pos)
    {
        res+=tree[id][pos];
        pos-=lowbit(pos);
    }
    return res;
}

void change(int u,int x)
{
    if(!w[u]) for(auto i:v[u]) zero[i]--;
    else
    {
        for(auto i:v[u])
        {
            if(w[u]>G[i].size())
                continue;
            cnt[i][w[u]]--;
            if(!cnt[i][w[u]]) add(w[u],-1,i);
        }
    }
    if(!x)
    {
        for(auto i:v[u]) zero[i]++;
        w[u]=x;
        return;
    }
    for(auto i:v[u])
    {
        if(x>G[i].size())   continue;
        cnt[i][x]++;
        if(cnt[i][x]==1) add(x,1,i);
    }
    w[u]=x;
}

int query1(int u)
{
    for(int i=0;i<=G[u].size();i++) vis[i]=0;
    for(int i=0;i<G[u].size();i++)
    {
        int to=G[u][i];
        if(w[to]>G[u].size())   continue;
        vis[w[to]]++;
    }
    for(int i=0;i<=v[u].size();i++)
    {
        if(!vis[i]) return i;
    }
}//暴力

int query2(int u)
{
    if(!zero[u]) return 0;
    int l=1,r=G[u].size(),res=G[u].size();
    while(l<=r)
    {
        int mid=l+r>>1;
        if(get_sum(mid,u)<mid) r=mid-1,res=mid;
        else                   l=mid+1;
    }
    return res;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int qf=sqrt(m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&w[i]);
        }
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            G[x].push_back(y);
            G[y].push_back(x);
            //v[x].push_back(y);
            //v[y].push_back(x);
        }
        for(int i=1;i<=n;i++) {
            for(int j=0;j<G[i].size();j++) {
                int nx=G[i][j];
                if(G[nx].size()>=qf)    v[i].push_back(nx);
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(G[i].size()>=qf)
            {
                tree[i].resize(G[i].size()+10);
                cnt[i].resize(G[i].size()+10);
                for(int j=0;j<=G[i].size();j++) tree[i][j]=cnt[i][j]=0;
                for(int j=0;j<G[i].size();j++)
                {
                    int to=G[i][j];
                    if(w[to]>G[i].size()) continue;
                    if(!w[to]) {zero[i]++;continue;}
                    cnt[i][w[to]]++;
                    if(cnt[i][w[to]]==1) add(w[to],1,i);
                }
            }
        }
        int Q;
        scanf("%d",&Q);
        while(Q--)
        {
            int a,b,c;
            scanf("%d",&a);
            if(a==1)
            {
                scanf("%d%d",&b,&c);
                change(b,c);
            }
            else
            {
                scanf("%d",&b);
                if(G[b].size()<=qf)
                {
                    printf("%d\n",query1(b));
                }
                else    printf("%d\n",query2(b));
            }
        }
        for(int i=1;i<=n;i++)   v[i].clear(),zero[i]=0,G[i].clear();
    }
    return 0;
}