https://ac.nowcoder.com/acm/contest/358#question
出题人有一个n个点，m条边的无向图，点有属性ai和bi，以及一个神秘常数kk
有q组询问，每组询问给出正整数v，k和k个点
对于每个询问，在原图中删去(给定的k个点所在的连通块)和(属性ai大于v的点) (只作用于这次询问)
再删去与这些点相连的边(也只作用于这次询问)
那么剩下的图就有了一些联通块
对于每个联通块，定义其贡献为连通块中的不同的属性b数量（这个连通块中存在此属性b，且出现次数为kk的倍数）
每个询问输出此时所有联通块的贡献的最大值
首先可以发现，直接在线维护并不容易，所以考虑将v值排序离线处理。每一个询问前，只将比他v值小的点加入。
维护联通块可以用并查集，难点在于联通块合并的时候联通块内合法颜色的种数不好维护，事实上可以用启发式合并的方法维护每个联通快内不同颜色的数量，然后用这样的方法维护联通块的最大值。
由于每次询问还涉及到删除联通快的操作，所以不能只保存最大的答案，考虑用一个multiset维护所有联通块的答案，每次询问的时候将k个答案移除，询问完了再加入，由于k的总值范围确定，时间复杂度事实上也有保证。
#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d ", x) #define Prl(x) printf("%lld ",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 3e6 + 10; const int maxm = 3e6 + 10; const int maxq = 3e6 + 10; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; struct Node{ int way; int v,x; Node(){} Node(int way,int v,int x):way(way),v(v),x(x){} }op[maxq + maxn]; struct Edge{ int to,next; }edge[maxm * 2]; int head[maxn],tot; int ans[maxq],fa[maxn]; vector<int>del[maxq]; int vis[maxn],c[maxn],use[maxn]; int num[maxn],size[maxn]; map<int,int>color[maxn]; bool cmp(Node a,Node b){ if(a.v != b.v) return a.v < b.v; return a.way == 1; } multiset<int>P; void init(){ for(int i = 0 ; i <= N; i ++){ head[i] = -1; fa[i] = i; size[i] = 1; } tot = 0; } void add(int u,int v){ edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; } int find(int p){ if(p == fa[p]) return p; return fa[p] = find(fa[p]); } void Union(int a,int b){ a = find(a); b = find(b); if(a == b) return; if(size[a] > size[b]) swap(a,b); fa[a] = b; size[b] += size[a]; size[a] = 0; P.erase(P.find(num[a])); P.erase(P.find(num[b])); for(map<int,int>::iterator it = color[a].begin(); it != color[a].end(); it++){ pair<int,int> x = *it; int &tmp = color[b][x.fi]; if(tmp && !(tmp % K)){ num[b]--; } tmp += x.second; if(tmp && !(tmp % K)){ num[b]++; } } P.insert(num[b]); num[a] = 0; } map<int,int>Hash; int main(){ Sca3(N,M,K); init(); int cnt = 0; for(int i = 1; i <= N ; i ++){ op[++cnt] = Node(1,read(),i); } int ttt = 0; for(int i = 1; i <= N ; i ++){ Sca(c[i]); if(!Hash[c[i]]) Hash[c[i]] = ++ttt; c[i] = Hash[c[i]]; } for(int i = 1; i <= N ; i ++){ color[i][c[i]] = 1; if(K == 1) num[i] = 1; else num[i] = 0; } for(int i = 1; i <= M; i ++){ int u,v; Sca2(u,v); add(u,v); add(v,u); } int Q; Sca(Q); for(int i = 1; i <= Q; i ++){ op[++cnt] = Node(2,read(),i); int k = read(); for(int j = 0 ; j < k; j ++){ del[i].pb(read()); } } sort(op + 1,op + 1 + cnt,cmp); for(int i = 1; i <= cnt; i ++){ if(op[i].way == 1){ P.insert(num[op[i].x]); vis[op[i].x] = 1; for(int j = head[op[i].x]; ~j; j = edge[j].next){ int v = edge[j].to; if(vis[v]){ Union(op[i].x,v); } } }else{ multiset<int>::iterator it; for(int j = 0; j < del[op[i].x].size(); j ++){ int p = find(del[op[i].x][j]); if(!vis[p]) continue; if(use[p]) continue; use[p] = 1; it = P.find(num[p]); P.erase(it); } int sum = 0; if(P.size()){ it = P.end(); it--; sum = *it; } ans[op[i].x] = sum; for(int j = 0 ; j < del[op[i].x].size(); j ++){ int p = find(del[op[i].x][j]); if(!vis[p]) continue; if(!use[p]) continue; use[p] = 0; P.insert(num[p]); } } } for(int i = 1; i <= Q; i ++) Pri(ans[i]); return 0; }