ZOJ 4100

题意

给定一个初始无边的$n$个点图,有$q$询问。

每次要么连接两个点,保证这两个点之前不相邻;
要么询问保证该图是简单图的情况下连接$k$条边所能得到的连通块数目最大最小值分别是多少(询问不修改图)。

$1 \leq n \leq 10^5, 1 \leq q \leq 2 \times 10^5, 1 \leq k \leq \frac{n(n-1)}{2}$

做法

  • 连通块数目最小值
    • 显而易见一条边可以使连通块数目减少$1$
  • 连通块数目最大值
    • 一个直观的感受是,我们先把每个连通块处理成完全图,此时连通块数目不减
    • 接下来如果还有边,我们应当从按点数从大到小合并连通块,并继续使图将新的连通块补全成完全图
    • 利用关于连通块点数的权值线段树维护这个过程,结点需要保存
      • 子树内所有连通块的点数
      • 子树内的连通块个数
      • 假设每个连通块已经是完全图,将子树内所有连通块合并成一个完全图需要的边数
    • 然后可以利用线段树上二分得到连通块大小的边界
    • 再二分该大小的连通块需要合并几个即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
/*****************************************
Author: lizi
Email: zyli@smail.nju.edu.cn
*****************************************/

#include<bits/stdc++.h>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %d: ",x)
#define pn1(x) printf("Case %d:\n",x)
#define pr2(x) printf("Case #%d: ",x)
#define pn2(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))
#define fi first
#define se second
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

struct FastIO {
static const int S = 5 << 20; //MB
int wpos; char wbuf[S];
FastIO() : wpos(0) {}
inline int xchar() {
static char buf[S];
static int len = 0, pos = 0;
if(pos == len)
pos = 0, len = fread(buf, 1, S, stdin);
if(pos == len) return -1;
return buf[pos ++];
}
inline int xuint() {
int c = xchar(), x = 0;
while(~c && c <= 32) c = xchar();
for(; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x;
}
inline LL xull() {
int c = xchar();
LL x = 0;
while(~c && c <= 32) c = xchar();
for(; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x;
}
inline int xint() {
int s = 1, c = xchar(), x = 0;
while(c <= 32) c = xchar();
if(c == '-') s = -1, c = xchar();
for(; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x * s;
}
inline void xstring(char* s) {
int c = xchar();
while(c <= 32) c = xchar();
for(; c > 32; c = xchar()) * s++ = c;
*s = 0;
}
inline void wchar(int x) {
if(wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
wbuf[wpos ++] = x;
}
inline void wll(LL x) {
if(x < 0) wchar('-'), x = -x;

char s[30];
int n = 0;
while(x || !n) s[n ++] = '0' + x % 10, x /= 10;
while(n--) wchar(s[n]);
}
inline void wstring(const char* s) {
while(*s) wchar(*s++);
}
~FastIO() {
if(wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
}
} io;

const int maxn = 200005;
struct node
{
int l, r, ls, rs;
LL nodes, edges, comps;
bool isone() {return l == r;}
bool match(int x, int y) {return l == x && r == y;}
void clear(int x, int y){l = x; r = y; ls = rs = nodes = edges = comps = 0;}
}tr[maxn << 1];
int f[maxn], nodenum, T, n, m, s[maxn];
LL inner_edges, already_edges, all_edges, compcnt, e[maxn];

LL calmaxedges(LL hasnd, LL node, LL edge) {return hasnd * node + edge;}

LL calcompedge(LL num, LL sz) {return ((num * (num - 1)) >> 1) * sz * sz;}

void mt(int x, int y)
{
tr[nodenum].clear(x, y);
if(x == y) return;
int mid = (x + y) >> 1, t = nodenum;
nodenum ++; tr[t].ls = nodenum; mt(x, mid);
nodenum ++; tr[t].rs = nodenum; mt(mid + 1, y);
}

void pushup(int t)
{
int ls = tr[t].ls, rs = tr[t].rs;
if(ls + rs == 0) return;
tr[t].nodes = tr[ls].nodes + tr[rs].nodes;
tr[t].edges = tr[ls].edges + tr[rs].edges + tr[ls].nodes * tr[rs].nodes;
tr[t].comps = tr[ls].comps + tr[rs].comps;
}

void modify(int rt, int pos, LL val)
{
if(tr[rt].isone())
{
tr[rt].nodes += val;
LL now = tr[rt].nodes / tr[rt].l;
tr[rt].comps = now;
now = (now * (now - 1)) >> 1;
tr[rt].edges = 1ll * tr[rt].l * tr[rt].l * now;
return;
}
int mid = (tr[rt].l + tr[rt].r) >> 1;
if(pos <= mid) modify(tr[rt].ls, pos, val);
if(pos > mid) modify(tr[rt].rs, pos, val);
pushup(rt);
}

LL nodesum(int rt, int l, int r)
{
if(tr[rt].match(l, r)) return tr[rt].nodes;
int mid = (tr[rt].l + tr[rt].r) >> 1;
LL ret = 0;
if(l <= mid) ret += nodesum(tr[rt].ls, l, min(mid, r));
if(r > mid) ret += nodesum(tr[rt].rs, max(mid + 1, l), r);
return ret;
}

pair<LL, LL> edgesum(int rt, int l, int r)
{
if(tr[rt].match(l, r)) return mp(tr[rt].edges, tr[rt].nodes);
int mid = (tr[rt].l + tr[rt].r) >> 1;
pair<LL, LL> ret1 = mp(0ll, 0ll), ret2 = mp(0ll, 0ll);
if(l <= mid) ret1 = edgesum(tr[rt].ls, l, min(mid, r));
if(r > mid) ret2 = edgesum(tr[rt].rs, max(mid + 1, l), r);
return mp(ret1.fi + ret2.fi + ret1.se * ret2.se, ret1.se + ret2.se);
}

LL compsum(int rt, int l, int r)
{
if(tr[rt].match(l, r)) return tr[rt].comps;
int mid = (tr[rt].l + tr[rt].r) >> 1;
LL ret = 0;
if(l <= mid) ret += compsum(tr[rt].ls, l, min(mid, r));
if(r > mid) ret += compsum(tr[rt].rs, max(mid + 1, l), r);
return ret;
}

int findbound(int rt, LL last, LL hasnode)
{
if(tr[rt].isone()) return tr[rt].l;
int ls = tr[rt].ls, rs = tr[rt].rs;
LL tmpcal = calmaxedges(hasnode, tr[rs].nodes, tr[rs].edges);
if(tmpcal >= last) return findbound(rs, last, hasnode);
else return findbound(ls, last - tmpcal, hasnode + tr[rs].nodes);
}

int find(int t)
{
if(f[t] == t) return t;
else return f[t] = find(f[t]);
}

int main()
{
//IN;OUT;
T = io.xuint();
while(T --)
{
n = io.xuint(); m = io.xuint();
for(int i = 1; i <= n; ++ i) f[i] = i, e[i] = 0, s[i] = 1;
compcnt = n; inner_edges = 0; already_edges = 0; all_edges = (1ll * n * (n - 1)) >> 1;
nodenum = 1; mt(1, n);
for(int i = 1; i <= n; ++ i) modify(1, 1, 1);
while(m --)
{
int opt = io.xuint();
if(opt == 1)
{
already_edges ++; inner_edges --;
int x = io.xuint(), y = io.xuint();
x = find(x); y = find(y);
if(x == y) e[x] ++;
else
{
compcnt --;
inner_edges += 1ll * s[x] * s[y];
modify(1, s[x], -s[x]);
modify(1, s[y], -s[y]);
e[x] += e[y] + 1;
s[x] += s[y];
f[y] = f[x];
modify(1, s[x], s[x]);
}
}else
{
LL k = io.xull();
if(k + already_edges >= all_edges) {io.wstring("1 1\n"); continue;}
LL ansmi = max(1ll, compcnt - k), ansma;

// Solve for Maximum
k -= inner_edges;
if(k <= 0) {io.wll(ansmi); io.wchar(' '); io.wll(compcnt); io.wchar('\n'); continue;}
int bd = findbound(1, k, 0ll);
LL nds = nodesum(1, bd + 1, n);
k -= edgesum(1, bd + 1, n).fi;
LL ll = 1, rr = compsum(1, bd, bd);
while(rr - ll > 1)
{
LL mid = (ll + rr) >> 1;
if(calmaxedges(nds, mid * bd, calcompedge(mid, (LL)bd)) >= k) rr = mid; else ll = mid;
}
while(calmaxedges(nds, ll * bd, calcompedge(ll, (LL)bd)) < k) ++ ll;
ansma = compcnt - ll - compsum(1, bd + 1, n) + 1;
io.wll(ansmi); io.wchar(' '); io.wll(ansma); io.wchar('\n');
}
}
}
return 0;
}