1006 finding a mex (hdu6756)

1006 Finding a MEX(hdu6756)

The question ： Algorithm is a typical algorithm to solve the shortest path ,n A little bit m side (n,m≤1e5), Every point has a right $A_u$($A_u$≤1e9), There are two operations ( Operands ≤1e5):
operation 1 by 1 u x, It's to put u The point weight of the point is changed to x.
operation 2 by 2 u, It's asking u What is the smallest nonnegative integer that does not appear in the point weight of all points connected to the edge .

solution ： First , You can guarantee that for each vertex , operation 2 The biggest answer is its degree . And at most 1e5 side , Then the degree is greater than or equal to 350 At most, there are only 350 individual , Apply to this property , Then you can divide the point into two parts , The degree is greater than 350 And the degree is less than 350 Of . For degrees less than 350 That part. , Direct violence and truth seeking $O(n\sqrt{n})$, And for greater than 350 That part. , The minimum non negative integer that does not appear is required. You can choose bisection + Tree array , Count the number of times the weight appears , Two points answer , Use the tree array to check whether the answer is correct , We need a special verdict 0 Ow , Insert... On the tree array 0 It's a dead cycle .

Code ：

#include<cstdio>
#include<vector>
#include<cmath>
#include<cstring>
using namespace std;
const int N = 2e5+10;
int n, m, u, v, q, opt, x;
int val[N], a[455], isbig[N];
vector<int> tu[N], tr[N], btu[N], num[N];
// Tree array 
int lowbit(int x) {
     return x & -x; }
void upd(int x, int p, int d) {
    
	for( ; p <= tu[x].size(); p += lowbit(p)) tr[x][p] += d;
}
int que(int x, int p) {
    
	int ans = 0;
	for( ; p > 0; p -= lowbit(p)) ans += tr[x][p];
	return ans;
}
int main() {
    
	int T; scanf("%d", &T);
	while(T--) {
    
		
		scanf("%d%d", &n, &m);
		for(int i = 1; i <= n; ++i) {
    
			scanf("%d", &val[i]);
			isbig[i] = 0;
			tu[i].clear(); btu[i].clear(); num[i].clear(); tr[i].clear();
		}
		
		for(int i = 0; i < m; ++i) {
    
			scanf("%d%d", &u, &v);
			tu[u].push_back(v); 
			tu[v].push_back(u);
		}
		
		int sq = 450, len;
		for(int i = 1; i <= n; ++i) {
    
			if(tu[i].size() >= sq) {
    
				len = tu[i].size(); isbig[i] = 1;
				tr[i].resize(len+2, 0);
				num[i].resize(len+2, 0);
				for(int j = 0; j <= len; j++) tr[i][j] = num[i][j] = 0;
				for(int j = 0, mid; j < len; ++j) {
     
					mid = val[tu[i][j]]; btu[tu[i][j]].push_back(i);
					if(mid > len) continue;
					++num[i][mid];
					if(mid && num[i][mid] == 1) upd(i, mid, 1);
				}
			}
		}
		scanf("%d", &q);
		while(q--) {
    
			scanf("%d%d", &opt, &u);
			if(opt == 1) {
     
				scanf("%d", &x);
				if(val[u] == x) continue;
				len = btu[u].size();
				for(int i = 0, v; i < len; ++i) {
     		
					v = btu[u][i];  
					if(val[u] <= tu[v].size()) {
     
						--num[v][val[u]]; 
						if(val[u] && !num[v][val[u]]) upd(v, val[u], -1);
					} 
					if(x <= tu[v].size()) {
     
						++num[v][x];
						if(x && num[v][x] == 1) upd(v, x, 1);
					}  
				} 
				val[u] = x;
			} else {
     
				if(isbig[u]) {
     
					if(!num[u][0]) {
     
						puts("0"); continue;
					} 
					int l = 1, r = tu[u].size(), mid, ans = 0;
					while(l <= r) {
     
						mid = l + r >> 1;
						if(que(u, mid-1) == mid-1) ans = mid, l = mid + 1;
						else r = mid - 1;
					}
					printf("%d\n", ans);
				} else {
    
					len = tu[u].size();
					for(int i = 0; i <= len; i++) a[i] = 0;
					for(int i = 0, mid; i < len; ++i) {
    
						mid = val[tu[u][i]];
						if(mid <= len) ++a[mid];
					}
					for(int i = 0; i <= len; ++i) 
						if(!a[i]) {
     printf("%d\n", i); break; }
				}
			}
		}
	}
	return 0;
}