杭电第一场1005 Finding a MEX 树上分块
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6756
题目大意：
有一个n点，m条边的无向图，每个点有一个权值。现在有两个操作：
1 x y：把x点的权值修改为y
2 x : 查询x的的邻接点的权值中没有出现的最小非负整数。
思路：前几天正好补了一个分块的题，今天就遇到了。
我们考虑按点的度数进行维护。
我们考虑用权值线段树去维护每个点的mex。
对于修改x：
我们去遍历它d[y]>sqrt(n)的邻接点,最多有sqrt(n)个，每个在线段树上修改，复杂度:O(sqrt(n) * logn)
对于查询x：
如果d[u]<=sqrt(n)那么我们暴力每个点查询就可以了。复杂度:O(sqrt(n))
如果d[u]>sqrt(n)那么我们直接在线段树查询就可以了，复杂度:O(sqrt(n) * logn)
如果就一直T到怀疑人生。这个地方用线段树常树太大。
我们考虑一些其他的维护方法：
1.树状数组（sqrt(n) * logn）:二分结果，前缀和查询。因为添加是O(sqrt(n) * logn)和查询(logn * log n)是分开的，那么复杂度还是添加的：sqrt(n) * logn
2.树状数组 （sqrt(n) * logn）：我们可以直接在树上二分，标程的做法
3.set（sqrt(n) * logn）：保存没有被占用的点。添加为set中删除，删除为set中添加。
3.分块(sqrt(n)): 我们根据上面的复杂度分析可以知道如果数据结构修改是O(1)，查询是O(sqrt(n))，那么总的复杂度就是O(n * sqrt(n))。
具体做法：
我们按权值分块，用laz数组维护这个块非o的数量。用桶记一下个数，O(1)修改
查询到每一块if laz[i]!=len， 说明这个块有没有被占用的，去块里找，复杂度：O(sqrt(n))
#include <bits/stdc++.h>
using namespace std;
int f[200015], d[200015];
vector<int> G[200015], son[200015], pos;
int vis[200015];
struct FK{
vector<int> w[200015], laz[200015];
int len;
void init(int n){
len=sqrt(n)+1;
for(int i=1; i<=n; i++){
w[i].clear(); w[i].resize(2*d[i]+5);
laz[i].clear(); laz[i].resize(2*d[i]+5);
}
for(int i=1; i<=n; i++){
if(d[i]>len){
int siz=d[i]/len;
for(int k=0; k<=siz; k++){
laz[i][k]=len;
}
}
}
}
void up_data(int pos, int x, int y){//x->y
if(x<=d[pos]){
w[pos][x]--;
if(w[pos][x]==0){
laz[pos][x/len]++;
}
}
if(y<=d[pos]){
w[pos][y]++;
if(w[pos][y]==1){
laz[pos][y/len]--;
}
}
}
int qurey(int pos){
int siz=d[pos]/len;
int p=siz;
for(int i=0; i<=siz; i++){
if(laz[pos][i]){
p=i; break;
}
}
for(int i=len*p; i<len*(p+1); i++){
if(!w[pos][i]){
return i;
}
}
}
}F;
int main(){
int t; scanf("%d", &t);
while(t--){
int n, m, q, x, y, z; scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++){
f[i]=d[i]=0;
G[i].clear();
son[i].clear();
}
for(int i=1; i<=n; i++){
scanf("%d", &f[i]);
}
for(int i=1; i<=m; i++){
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
d[x]++, d[y]++;
}
for(int i=1; i<=n; i++){
sort(G[i].begin(), G[i].end(), [](int &a, int &b){return d[a]<d[b];});
}
int len=sqrt(n)+1;
F.init(n);
for(int i=1; i<=n; i++){
for(auto x: G[i]){
if(d[x]>len){
son[i].push_back(x);
}
}
}
for(int i=1; i<=n; i++){
for(auto x: son[i]){
F.up_data(x, 1e5+5, f[i]);
}
}
scanf("%d", &q);
while(q--){
scanf("%d%d", &x, &y);
if(x==1){
scanf("%d", &z);
for(auto x: son[y]){
if(d[x]>len){
F.up_data(x, f[y], z);
}
}
f[y]=z;
}
else{
if(d[y]>len){
for(auto x: son[y]){
F.up_data(x, 1e5+5, f[x]);
}
printf("%d\n", F.qurey(y));
for(auto x: son[y]){
F.up_data(x, f[x], 1e5+5);
}
}
else{
for(int i=0; i<G[y].size(); i++){
if(f[G[y][i]]<n+5){
pos.push_back(f[G[y][i]]);
vis[f[G[y][i]]]=1;
}
}
for(int i=0; i<=n+5; i++){
if(!vis[i]){
printf("%d\n", i);
break;
}
}
for(auto x: pos){
vis[x]=0;
}
pos.clear();
}
}
}
}
return 0;
}
美团开奖761人在聊