考虑分块，大于块数的动态开点权值线段树，小于的话暴力修改。
#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> #define ll long long #define PB push_back #define endl ' ' #define INF 0x3f3f3f3f #define LINF 0x3f3f3f3f3f3f3f3f #define ull unsigned long long #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r #define lowbit(x) (x & (-x)) #define rep(i, a, b) for(int i = a ; i <= b ; ++ i) #define per(i, a, b) for(int i = b ; i >= a ; -- i) #define clr(a, b) memset(a, b, sizeof(a)) #define in insert #define random(x) (rand()%x) #define PII(x, y) make_pair(x, y) #define fi first #define se second #define pi acos(-1) #define re register //std::ios::sync_with_stdio(false); using namespace std; const int maxn = 1e6 + 50; const int N = 1e5 + 10; const int M = N * 20; const ll mod = 1e9 + 9; int T, bk, cnt, n, m; int w[N], x[N], y[N], du[N], rt[N], vis[N], ls[M], rs[M], sum[M], num[M]; vector<int> g[N], G[N]; #define mid ((l + r) >> 1) char *fs,*ft,buf[1<<20]; #define gc() (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<20,stdin),fs==ft))?0:*fs++; inline int read(){ int x=0,f=1; char ch=gc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();} return x*f; } inline void update(int &p, int l, int r, int x, int y){ if(!p) {p = ++ cnt; ls[p] = rs[p] = sum[p] = num[p] = 0;} //cout << p <<endl; if(l == r) {sum[p] += y; num[p] = (sum[p]>0?1:0); return;} if(x <= mid) update(ls[p], l, mid, x, y); else update(rs[p], mid + 1, r, x, y); sum[p] = sum[ls[p]] + sum[rs[p]]; num[p] = num[ls[p]] + num[rs[p]]; } inline int query(int p, int l, int r){ if(l == r) return l; if(num[ls[p]] >= mid - l + 1) return query(rs[p], mid + 1, r); else return query(ls[p], l, mid); } void upd(int x, int y){ for(int v : G[x]){ update(rt[v], 0, 1e9, w[x], -1); update(rt[v], 0, 1e9, y, 1); } w[x] = y; } int cal(int x){ if(vis[x]) return query(rt[x], 0, 1e9); vector<int> t; for(int v : g[x]) t.PB(w[v]); sort(t.begin(), t.end()); t.erase(unique(t.begin(), t.end()), t.end()); for(int i = 0 ; i < t.size() ; ++ i) if(t[i]!=i) return i; return (int)t.size(); } signed main(){ freopen("C://std/a.in","r",stdin); //输入重定向，输入数据将从in.txt文件中读取 freopen("C://std/b.txt","w",stdout); int q, op, u, v; T = read(); while(T --){ n = read(); m = read(); bk=sqrt(log2(n+m)*(n+m)); cnt = 0; rep(i, 1, n) w[i]=read(), du[i]=rt[i]=vis[i]=0, g[i].clear(), G[i].clear(); rep(i, 1, m){ x[i] = read(); y[i] = read(); du[y[i]] ++; du[x[i]] ++; g[x[i]].PB(y[i]); g[y[i]].PB(x[i]); } rep(i, 1, n) if(du[i] >= bk) vis[i] = 1; rep(i, 1, m){ if(vis[x[i]]) G[y[i]].PB(x[i]), update(rt[x[i]], 0, 1e9, w[y[i]], 1); if(vis[y[i]]) G[x[i]].PB(y[i]), update(rt[y[i]], 0, 1e9, w[x[i]], 1); } q = read(); while(q --){ op = read(); u = read(); if(op == 1) v = read(), upd(u, v); else printf("%d ", cal(u)); } } return 0; }