本文共 3132 字，大约阅读时间需要 10 分钟。

题目

思路

分块，根据点的度数 是否超过 $\sqrt{n}$ 分成 “大点” 和 “小点” 。

“小点” 可以每次直接暴力做，所以只需要考虑维护 “大点” 。由于大点个数不超过 $\sqrt{n}$ ，可以单独计算对于每个 “大点” 的影响。

用什么维护呢？求 $mex$ 的套路：值域分块。比如就可以用值域分块的莫队。虽然实际上是回滚莫队的板题。

然后就做到了 $\mathcal{O}(n^{\frac{3}{2}}+q\sqrt{n})$ 了。但是我实现出来发现常数蛮大，调整了几次块的大小才过的。

代码

#include 
   
     #include 
    
     #include 
     
      #include 
      
       using namespace std;inline int readint(){   	int a = 0; char c = getchar(), f = 1;	for(; c<'0'||c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c&&c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}inline void writeint(int x){   	if(x > 9) writeint(x/10);	putchar((x-x/10*10)^48);}const int MaxN = 100005;struct Edge{   	int to, nxt;	Edge(){    }	Edge(int T,const int &N){   		to = T, nxt = N;	}};Edge e[MaxN<<1|1];int head[MaxN+1], cntEdge;int deg[MaxN+1]; // degreevoid addEdge(int a,int b){   	e[cntEdge] = Edge(b,head[a]);	head[a] = cntEdge ++;	++ deg[a]; // how much exports}const int Block = 300;struct SYT{   	int Cnt[MaxN/Block+1];	int cnt[MaxN+1];	void modify(int x,int v){   		if(!cnt[x] || !(cnt[x]+v))			Cnt[x/Block] += v;		cnt[x] += v; // just count	}	void clear(){   		memset(Cnt,0,(MaxN/Block+1)<<2);		memset(cnt,0,(MaxN+1)<<2);	}	int query(){   		int xez = 0;		while(Cnt[xez] == Block)			++ xez; // find that block		for(int i=xez*Block; ; ++i)			if(cnt[i] <= 0) return i;	}};SYT sy[2*MaxN/Block]; // only a few can be hereint id[MaxN+1]; // give BIG point a indexint val[MaxN+1], tmp[MaxN+1];int main(){   //	freopen("data.in","r",stdin);//	freopen("mine.out","w",stdout);	for(int T=readint(),n,m; T; --T){   		n = readint(), m = readint();		cntEdge = 0; // clear graph		for(int i=1; i<=n; ++i){   			deg[i] = 0; // clear			val[i] = min(readint(),n);			head[i] = -1; // clear		}		for(int i=0,a,b; i
       
        = Block)				id[i] = tot ++; 			else id[i] = -1;		for(int i=1; i<=n; ++i){   			if(id[i] == -1) continue;			sy[id[i]].clear(); int xez = 0;			for(int j=head[i]; ~j; j=e[j].nxt){   				sy[id[i]].modify(val[e[j].to],1);				tmp[xez ++] = e[j].to;			}			e[m<<1].nxt = head[i]; // zombie			int j = m<<1; // to delete edges			for(--xez; ~xez; --xez){   				if(id[tmp[xez]] == -1)					continue; // not wanted				j = e[j].nxt; // j is good				e[j].to = tmp[xez];			}			if(j == (m<<1)) // no edge				head[i] = -1;			else e[j].nxt = -1;		}				memset(tmp,0,(MaxN+1)<<2); // useful		int q = readint();		for(int opt,u,v; q; --q){   			opt = readint(), u = readint();			if(opt == 2){   //				printf("ans = ");				if(id[u] == -1){    // SMALL					v = head[u]; // for fun					for(int i=v; ~i; i=e[i].nxt)						tmp[val[e[i].to]] = 1;					for(int i=0; true; ++i)						if(tmp[i] == 0){   							writeint(i);							break; // find ans						}					for(int i=v; ~i; i=e[i].nxt)						tmp[val[e[i].to]] = 0;				}				else if(id[u] != -1) // BIG					writeint(sy[id[u]].query());				putchar('\n');			}			if(opt == 1){   				v = min(readint(),n);				for(int i=head[u]; ~i; i=e[i].nxt)					if(id[e[i].to] != -1){   						sy[id[e[i].to]].modify(val[u],-1);						sy[id[e[i].to]].modify(v,1);					}				val[u] = v; // change on disk			}		}	}	return 0;}