HDU - 6756 Finding a MEX

传送门：HDU - 6756

思路分析

对度数进行分块，度数大于根号$\sqrt{n}$的点用树状数组求mex，小于的暴力

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N = 1e5+10;

int w[N],a[N],b[N],in[N],vis[N];
vector<int>e[N],g[N],bit[N],live[N];

void add(int id,int x,int k){
    if(x==0){
        bit[id][0]+=k;
        return ;
    }
    for(int i=x;i<=in[id];i+=lowbit(i)) bit[id][i]+=k;
}

int get(int id,int x){
    int ans=0;
    for(int i=x;i;i-=lowbit(i)) ans+=bit[id][i];
    return ans;
}

int cal(int x) {
    for(int i=0;i<=in[x];i++) vis[i]=0;
    for(int v:e[x]) {
        if(w[v]<=in[v]) vis[w[v]]=1;
    }
    for(int i=0;i<=in[x];i++) if(!vis[i]) return i;
}

int main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int T;
    read(T);
    while(T--) {
        int n,m;
        read(n,m);
        int M = sqrt(n);
        for(int i=1; i<=n; i++) {
            read(w[i]);
            e[i].clear();
            in[i]=0;
            g[i].clear();
        }
        for(int i=1; i<=m; i++) {
            read(a[i],b[i]);
            int u=a[i];
            int v=b[i];
            e[u].pb(v);
            e[v].pb(u);
            in[u]++;
            in[v]++;
        } 
        for(int i=1; i<=n; i++) {
            if(in[i]>M){
                bit[i].resize(in[i]+2);
                live[i].resize(in[i]+2);
                for(int j=0;j<in[i]+2;j++) bit[i][j]=live[i][j]=0;
                for(auto v:e[i]){
                    if(w[v]<=in[i]){
                        live[i][w[v]]++;
                        if(live[i][w[v]]==1) add(i,w[v],1);
                    }
                }
            }
            for(auto v:e[i]) if(in[v]>M) g[i].pb(v);
        }
        int q;
        read(q);
        for(int i=1; i<=q; i++) {
            int op,x,y;
            read(op,x);
            if(op==1) {
                read(y);
                if(w[x]==y) continue;
                for(auto v:g[x]){
                    if(w[x]<=in[v]){
                        live[v][w[x]]--;
                        if(live[v][w[x]]==0) add(v,w[x],-1);
                    }
                    if(y<=in[v]){
                        live[v][y]++;
                        if(live[v][y]==1) add(v,y,1);
                    }
                }
                w[x]=y;
            } else {
                if(in[x]>M){
                    if(!bit[x][0]) {
                        puts("0");
                        continue;
                    }
                    int l=1,r=in[x];
                    int ans=-1;
                    while(r>=l){
                        int mid=l+r>>1;
                        if(get(x,mid)<mid){
                            r=mid-1;
                            ans=mid;
                        }else{
                            l=mid+1;
                        }
                    }
                    printf("%d\n",ans);
                }else {
                    printf("%d\n",cal(x));
                }
            }
        }
        for(int i=1;i<=n;i++) {
            if(in[i]>M){
                bit[i].clear();
                live[i].clear();
            }
        }
    }


    return 0;
}