题目大意
给一张 (n) 个点 (m) 条边的无向图 ((1leq n,mleq 10^5))。结点 (u) 的点权为 (A_u)。
现在要求实现两种操作:
1 u x : 把结点 (u) 的点权修改为 (x,(0leq xleq 10^9))。
2 u : 询问结点 (u) 邻接到的所有点的点权的mex。
题解
修改每个点只会影响这个点的邻域，如果暴力去修改，因为点的度数可能很大，将会TLE。按照图论分块的套路，设结点 (u) 的度数为 (deg[u])，令度数小于等于 (sqrt m) 的点为轻点，度数大于 (sqrt m) 的点为重点。轻点向所有点连边，重点只向重点连边，这样每个点邻接的点的数量都在 (O(sqrt m)) 级别。
对于每个重点，我们开一个权值树状数组来存储它邻接到的所有点的点权，每次去二分树状数组的前缀和来求mex。对于修改操作，每次修改同时都要更新相邻的重点的树状数组。对于询问操作，如果询问的是轻点，则 (O(sqrt m)) 暴力遍历它邻接的结点求mex，如果询问的是重点，则直接树状数组求mex。
Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
#define RG register int
#define LL long long
template<typename elemType>
inline void Read(elemType &T){
elemType X=0,w=0; char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
T=(w?-X:X);
}
inline int lowbit(int x){return x&(-x);}
struct BIT{
int *Node,*cnt;
int N;
void set_Len(int len){
N=len;
delete Node;delete cnt;
Node=new int[N+1]();cnt=new int[N+1]();
}
void clear(){N=0;delete Node;delete cnt;Node=cnt=nullptr;}
void Update(int x,int Add){for(;x<=N;x+=lowbit(x)) Node[x]+=Add;}
int PrefixSum(int x){int Res=0;for(;x;x-=lowbit(x)) Res+=Node[x];return Res;}
int Query(int L,int R){return PrefixSum(R)-PrefixSum(L-1);}
void Insert(int x){
++x;if(x>N) return;
++cnt[x];
if(cnt[x]==1) Update(x,1);
}
void Delete(int x){
++x;if(x>N) return;
if(!cnt[x]) return;
--cnt[x];
if(!cnt[x]) Update(x,-1);
}
int Mex(){
int Res=0,L=1,R=N;
while(L<=R){
int mid=(L+R)>>1;
if(PrefixSum(mid)<mid){Res=mid;R=mid-1;}
else L=mid+1;
}
return Res-1;
}
};
BIT Tree[450];
struct Graph{
struct edge{int Next,to;};
edge G[200010];
int head[100010];
int cnt;
Graph():cnt(2){}
void clear(int node_num=0){
cnt=2;
if(node_num==0) memset(head,0,sizeof(head));
else fill(head,head+node_num+5,0);
}
void add_edge(int u,int v){
G[cnt].to=v;
G[cnt].Next=head[u];
head[u]=cnt++;
}
};
Graph G;
int Value[100010],deg[100010],U[100010],V[100010],ID[100010];
bool heavy[100010];
int N,M,T,Q,block,Index=0;
void Change(int u,int x){
for(int i=G.head[u];i;i=G.G[i].Next){
int v=G.G[i].to;
if(heavy[v]){
Tree[ID[v]].Delete(Value[u]);
Tree[ID[v]].Insert(x);
}
}
Value[u]=x;
}
int temp[100010];
int Query(int u){
if(heavy[u]) return Tree[ID[u]].Mex();
fill(temp,temp+deg[u]+1,0);
for(int i=G.head[u];i;i=G.G[i].Next){
int v=G.G[i].to;
if(Value[v]>deg[v]+1) continue;
++temp[Value[v]];
}
for(RG i=0;i<=deg[u]+1;++i)
if(!temp[i]) return i;
return 0;
}
int main(){
Read(T);
while(T--){
Read(N);Read(M);
for(RG i=0;i<=Index;++i)
Tree[i].clear();
G.clear(N);block=sqrt(M);Index=0;
for(RG i=1;i<=N;++i){
Read(Value[i]);
heavy[i]=false;
deg[i]=0;
}
for(RG i=1;i<=M;++i){
Read(U[i]);Read(V[i]);
++deg[U[i]];++deg[V[i]];
}
for(RG i=1;i<=N;++i){
if(deg[i]>block){
heavy[i]=true;ID[i]=++Index;
Tree[ID[i]].set_Len(deg[i]+1);
}
}
for(RG i=1;i<=M;++i){
int u=U[i],v=V[i];
if(!heavy[u] || heavy[v]) G.add_edge(u,v);
if(!heavy[v] || heavy[u]) G.add_edge(v,u);
if(heavy[u]) Tree[ID[u]].Insert(Value[v]);
if(heavy[v]) Tree[ID[v]].Insert(Value[u]);
}
Read(Q);
while(Q--){
int opt,u,x;
Read(opt);
if(opt==1){Read(u);Read(x);Change(u,x);}
else{Read(u);printf("%d
",Query(u));}
}
}
return 0;
}