1006 cpp 1const itn maxn = 1e5 + 10; 2 3int n, m, w[maxn]; 4struct star{int to, next;}; 5 6int head[maxn], top = 0; 7int du[maxn], K; 8star edge[maxn << 1]; 9void add(int u, int v){ 10 edge[top].to = v; 11 edge[top].next = head[u]; 12 head[u] = top++; 13} 14 15unordered_map<int, int> mp[maxn]; 16unordered_map<int, int> conv; 17 18int c[700][maxn], bitcnt = 0, zero[maxn]; 19void add(int id, int i, int x, int n){ 20 while(i <= n){ c[id][i] += x; i += lowbit(i);} 21} 22int query(int id, int i){ 23 int ans = 0; 24 while(i){ans += c[id][i]; i -= lowbit(i);} return ans; 25} 26 27void bitupdate(int u, int key, int op){ 28 assert(conv.count(u) == 1); 29 int id = conv[u]; add(id, key, op, du[u]); 30} 31 32//将u节点的邻接权值key的数量 += op 33void update(int u, int key, int op){ 34 if(key > du[u]) return; 35 36 //特判断0 37 if(key == 0){ 38 zero[u] += op; return; 39 } 40 41 mp[u][key] += op; 42 // 1 - >0 43 if(mp[u][key] == 0){ 44 bitupdate(u, key, -1); 45 mp[u].erase(key); 46 } 47 //0 -> 1 48 if(mp[u][key] == 1 && op == 1) bitupdate(u, key, 1); 49 50} 51 52//检查u节点的邻点中 权值x及其之前是否填满 53bool check(int u, int x){ 54 if(x == 0){ 55 if(zero[u] == 0) return 0; 56 return 1; 57 } 58 int cnt = query(conv[u], x); 59 return x == cnt; 60} 61 62int temp[maxn]; 63int mex(int u){ 64 if(du[u] < K){ 65 for(int i = 0; i <= du[u]; i++) temp[i] = 0; 66 for(int i = head[u]; ~i; i = edge[i].next){ 67 if(w[edge[i].to] > du[u]) continue; 68 temp[w[edge[i].to]] = 1; 69 } 70 for(int i = 0; i <= du[u]; i++) if(!temp[i]) return i; 71 return -1; 72 } 73 else{ 74 if(zero[u] == 0) return 0; 75 76 int left = 0, right = du[u], middle; 77 while(left < right){ 78 middle = (left + right) >> 1; 79 if(check(u, middle)) left = middle + 1; 80 else right = middle; 81 } 82 return left; 83 } 84} 85 86unordered_set<int> vec[maxn]; 87 88struct NODE{ 89 int x, y; 90 NODE(int _x, int _y){ 91 x = min(_x, _y); 92 y = max(_x, _y); 93 } 94 bool operator <(const NODE &b)const{ 95 if(x != b.x) return x < b.x; 96 else return y < b.y; 97 } 98}; 99set<NODE> EDGE; 100 101int main(){ 102// Fastin; 103 int t; scanf("%d", &t); while(t--){ 104 clr(head, -1); top = 0; clr(du, 0); clr(zero, 0); bitcnt = 0; 105 106 n = read(); m = read(); 107 108 for(int i = 1; i <= n; i++) mp[i].clear(); conv.clear(); 109 110 K = sqrt(m); 111 for(int i = 1; i <= n; i++){ 112 w[i] = read(); vec[i].clear(); 113 } 114 115 EDGE.clear(); 116 for(int i = 0; i < m; i++){ 117 int u, v; u = read(); v = read(); 118 EDGE.insert(NODE(u, v)); 119 } 120 for(auto edge: EDGE){ 121 if(edge.x != edge.y){ 122 add(edge.x, edge.y); add(edge.y, edge.x); 123 du[edge.x]++; du[edge.y]++; 124 } 125 else{ 126 add(edge.x, edge.y); 127 du[edge.x]++; 128 } 129 } 130 //只有O(sqrt(m))个点的度>= K = sqrt(m) 131 for(int i = 1; i <= n; i++) if(du[i] >= K){ 132 memset(c[bitcnt], 0, sizeof (c[bitcnt])); 133 conv[i] = bitcnt++; 134 for(int j = head[i]; ~j; j = edge[j].next){ 135 int to = edge[j].to; vec[to].insert(i); 136 update(i, w[to], 1); 137 } 138 } 139 140 int q; scanf("%d", &q); while(q--){ 141 itn op, x, y; scanf("%d", &op); 142 if(op == 1){ 143 x = read(); y = read(); 144 //w[x] := y; 145 //v是所有的相邻大度点 146 for(auto v: vec[x]){ 147 update(v, w[x], -1); 148 update(v, y, 1); 149 } 150 w[x] = y; 151 } 152 else{ 153 x = read(); 154 printf("%d\n", mex(x)); 155 } 156 } 157 } 158 return 0; 159} 160