http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4100
比赛的时候封榜开始开这题，因为我的愚蠢没有开出来。
查询的最小值不用多说，维护一个当前的联通快数量num, max(num - K,1LL)就是答案，问题在于最大值。
仔细一看就会发现，首先需要将所有的联通快填满，变成一个个完全子图，这些被填满的边被称为白给的边，然后再开始计算答案，每次将两个联通快联通的时候，只用一条有效边就又会产生一堆白给的边，所以说，为了使联通快尽可能地多，我们需要每次不得不联通两个块之后尽量产生更多的白给的边。显而易见的是，联通需要从大的联通快开始合并，可以贪心的产生更多的白给边。
-----------------------------比赛想到了这一步，开始set暴力，最后十分钟发现时间复杂度很假，开始挂机-------------------------------------------
被合并的联通快的数量可以二分，二分的位置往右的所有联通快将会被变成一个大联通快，单调性显然。
问题在于维护这个过程，考虑到权值线段树，思路就明了了。
一开始先二分然后权值线段树check的操作写挂了，后面采用先权值线段树，最后一个点二分的操作就过了。
意识到先二分的话时间复杂度是nlognlogn,先权值线段树的话时间复杂度是Nlognlog(最后一个叶子节点的点数量)
#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 = 1e5 + 10; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; int fa[maxn]; LL size[maxn],edge[maxn],comp[maxn]; LL bg,num; void init(){ for(int i = 0 ; i <= N ; i ++){ fa[i] = i; size[i] = 1; edge[i] = 0; } num = N; bg = 0; } inline LL cul(LL x){ return x * (x - 1) / 2; } struct Tree{ int l,r; LL sum,num,edge; }tree[maxn << 2]; void Pushup(int t){ tree[t].edge = tree[t << 1].edge + tree[t << 1 | 1].edge; tree[t].num = tree[t << 1].num + tree[t << 1 | 1].num; tree[t].sum = tree[t << 1].sum + tree[t << 1 | 1].sum; } void Build(int t,int l,int r){ tree[t].l = l; tree[t].r = r; if(l == r){ tree[t].sum = tree[t].num = tree[t].edge = 0; if(l == 1){ tree[t].sum = tree[t].num = N; tree[t].edge = N * comp[l]; } return; } int m = l + r >> 1; Build(t << 1,l,m); Build(t << 1 | 1,m + 1,r); Pushup(t); } void update(int t,int p,int v){ if(tree[t].l == tree[t].r){ tree[t].sum += v * tree[t].l; tree[t].num += v; tree[t].edge += comp[tree[t].l] * v; return; } int m = tree[t].l + tree[t].r >> 1; if(p <= m) update(t << 1,p,v); else update(t << 1 | 1,p,v); Pushup(t); } int find(int p){ if(fa[p] == p) return p; return fa[p] = find(fa[p]); } void add(int u,int v){ u = find(u); v = find(v); if(u == v){ edge[u]++; bg--; return; } num--; bg -= comp[size[u]] - edge[u]; bg -= comp[size[v]] - edge[v]; update(1,size[u],-1); update(1,size[v],-1); fa[u] = v; size[v] += size[u]; edge[v] += edge[u] + 1; bg += comp[size[v]] - edge[v]; update(1,size[v],1); } LL cnt,E; int query(int t,LL k,LL v){ if(tree[t].l == tree[t].r){ int l = 0,r = tree[t].num; int ans = 0; while(l <= r){ int m = l + r >> 1; if(comp[v + m * tree[t].l] < comp[tree[t].l] * m + k){ ans = m + 1; l = m + 1; }else{ r = m - 1; } } return ans; } if(comp[v + tree[t << 1 | 1].sum] >= k + tree[t << 1 | 1].edge) return query(t << 1 | 1,k,v); else return query(t << 1,k + tree[t << 1 | 1].edge,v + tree[t << 1 | 1].sum) + tree[t << 1 | 1].num; } int main(){ int T; Sca(T); for(int i = 0 ; i < maxn; i ++) comp[i] = cul(i); while(T--){ Sca2(N,M); init(); Build(1,1,N); for(int i = 1; i <= M ; i ++){ int q = read(); if(q == 1){ int u,v; u = read(); v = read(); add(u,v); }else{ LL k; Scl(k); int MIN,MAX; MIN = max(num - k,1LL); if(k <= bg){ MAX = num; }else{ k -= bg; MAX = num - query(1,k,0LL) + 1; } printf("%d %d ",MIN,MAX); } } } return 0; }