题解：P10683 [COTS 2024] 划分 Particija
harmis_yz
·
·
题解
分析
对于每个 i，a_i 和 b_i + n 连边，表示集合 a_i 和集合 b_i+n 至少有一个要选。连出来是若干个联通二分图。
对于一个联通二分图，要么左部点全选，要么右部点全选。时间复杂度 $O(n)$。
$k=1$。
等价于修改一条边 $(u,v)$ 的某个端点。不妨设 $u$ 是左部点，修改 $v$。修改后有几种情况：
1. 修改后这个联通二分图不变。答案不变。
2. 修改后两个联通二分图合并。答案增加。因为 $\min(a,b)+\min(c,d)\le \min(a+c,b+d)$。
3. 修改后这个联通二分图分裂。答案减小。理由同 $2$。
因为最小化代价，所以选择情况 $3$ 不劣。则选择的边为这个联通二分图的割边。把左部点看成黑点，右部点看成白点（染色）（可以直接钦定黑点为 $a$ 中集合的点，白点为 $b$ 中集合的点）。维护每条割边两边黑白点数量即可。时间复杂度 $O(n)$。
$k=2$。
选择情况 $2$ 不劣。分情况讨论：
1. 选择的边不是割边。记黑点数量为 $a$，白点数量为 $b$。另一个连通块黑点数量为 $c$，白点为 $d$。
1. $a+c \le b+d$。等价于 $d-c \ge a-b$。那么就是求 $d-c \ge a-b$ 中，$c -\min(c,d)$ 的最大值（因为增加量为 $-\min(a,b) + (a+c) -\min(c,d)$）。注意要求这一对 $(c,d)$ 不是当前连通块。
2. $b+d \le a+c$。等价于 $c-d \ge b-a$。那么就是求 $c-d \ge b-a$ 中，$d -\min(c,d)$ 的最大值。
2. 选择的这条边是割边。枚举分成两个连通块后是哪一个和其它某个连通块合并。然后就和情况 $1$ 一样了。
时间复杂度 $O(n\log n)$。
## 代码
```cpp
const int N = 4e5 + 10, inf = 1e9 + 7;
int n, a[N], b[N];
int dfn[N], low[N], idx;
pii E[N]; int m;
bool st[N];
struct node{ pii x, y; int col; } spt[N];
vector<pii> e[N];
int n1, n2;
int col[N], c;
pii cnt[N];
struct Node{ int dt, val, c, typ; } q1[N << 1], q2[N << 1];
int l1, l2;
int dtc[N], Len;
il pii dfs(int u, int fr){
pii Cnt = {0, 0};
if(u <= n1) ++ Cnt.x;
else ++ Cnt.y;
col[u] = c;
dfn[u] = low[u] = ++ idx;
for(auto [v, id]: e[u]) if(id != fr){
spt[id].col = c;
if(! dfn[v]){
pii Cnt_ = dfs(v, id);
low[u] = min(low[u], low[v]);
if(low[v] > dfn[u]){
st[id] = 1;
spt[id].y = Cnt_;
spt[id].col = c;
}
Cnt.x += Cnt_.x;
Cnt.y += Cnt_.y;
}
else{
low[u] = min(low[u], dfn[v]);
}
}
return Cnt;
}
il void init(bool fc = 0){
n = rd, m = 0;
n1 = 0, n2 = 0;
Len = 0;
U(i, 1, n) a[i] = rd, dtc[++ Len] = a[i];
sort(dtc + 1, dtc + Len + 1), Len = unique(dtc + 1, dtc + Len + 1) - (dtc + 1);
U(i, 1, n) a[i] = lower_bound(dtc + 1, dtc + Len + 1, a[i]) - dtc; n1 = Len;
Len = 0;
U(i, 1, n) b[i] = rd, dtc[++ Len] = b[i];
sort(dtc + 1, dtc + Len + 1), Len = unique(dtc + 1, dtc + Len + 1) - (dtc + 1);
U(i, 1, n) b[i] = lower_bound(dtc + 1, dtc + Len + 1, b[i]) - dtc; n2 = Len;
U(i, 1, n * 2) dfn[i] = low[i] = st[i] = 0, e[i].clear(); idx = 0, c = 0;
U(i, 1, n){
E[++ m] = {a[i], b[i] + n1};
// cout << a[i]<<" "<<b[i]+n1<<"\n";
e[a[i]].push_back({b[i] + n1, m});
e[b[i] + n1].push_back({a[i], m});
}
if(fc == 1){
cout << n << " " << m << "\n";
U(i, 1, n) cout<< a[i] << " "; puts("");
U(i, 1, n) cout<< b[i] << " "; puts("\n");
}
U(i, 1, n1 + n2) if(! dfn[i]){
++ c;
cnt[c] = dfs(i, 0);
}
U(i, 1, m) if(st[i]){
int u = spt[i].col;
spt[i].x = {cnt[u].x - spt[i].y.x, cnt[u].y - spt[i].y.y};
}
return ;
}
il void solve0(){
int res = 0;
U(i, 1, c) res += min(cnt[i].x, cnt[i].y);
cout << res << "\n";
return ;
}
il void solve1(){
int res = 0, sum = 0;
U(i, 1, c) res += min(cnt[i].x, cnt[i].y);
sum = res;
U(i, 1, m) if(st[i]){
int u = spt[i].col;
int res_ = sum - min(cnt[u].x, cnt[u].y);
res_ += min(spt[i].x.x, spt[i].x.y) + min(spt[i].y.x, spt[i].y.y);
res = min(res, res_);
}
cout << max(1, res) << "\n";
return ;
}
il void solve2(){
l1 = l2 = 0;
int res = 0, sum = 0;
U(i, 1, c) res += min(cnt[i].x, cnt[i].y);
sum = res;
U(i, 1, c){
int C = cnt[i].x, D = cnt[i].y;
int delt = D - C;
int val = C - min(C, D);
q1[++ l1] = {delt, val, i, 0};
}
if(n1 < n){
int C = 1, D = 0;
int delt = D - C;
int val = C - min(C, D);
q1[++ l1] = {delt, val, c + 1, 0};
}
if(n2 < n){
int C = 0, D = 1;
int delt = D - C;
int val = C - min(C, D);
q1[++ l1] = {delt, val, c + 1, 0};
}
U(i, 1, c){
int C = cnt[i].x, D = cnt[i].y;
int delt = C - D;
int val = D - min(C, D);
q2[++ l2] = {delt, val, i, 0};
}
if(n1 < n){
int C = 1, D = 0;
int delt = C - D;
int val = D - min(C, D);
q2[++ l2] = {delt, val, c + 1, 0};
}
if(n2 < n){
int C = 0, D = 1;
int delt = C - D;
int val = D - min(C, D);
q2[++ l2] = {delt, val, c + 1, 0};
}
U(i, 1, m){
int u = spt[i].col;
int res_ = res - min(cnt[u].x, cnt[u].y);
if(st[i]){
{
pii x = spt[i].x;
int A = x.x, B = x.y;
int delt = A - B;
q1[++ l1] = {delt, res_ + A + min(spt[i].y.x, spt[i].y.y), u, 1};
delt = B - A;
q2[++ l2] = {delt, res_ + B + min(spt[i].y.x, spt[i].y.y), u, 1};
}
{
pii x = spt[i].y;
int A = x.x, B = x.y;
int delt = A - B;
q1[++ l1] = {delt, res_ + A + min(spt[i].x.x, spt[i].x.y), u, 1};
delt = B - A;
q2[++ l2] = {delt, res_ + B + min(spt[i].x.x, spt[i].x.y), u, 1};
}
}
else{
{
pii x = cnt[u];
int A = x.x, B = x.y;
int delt = A - B;
q1[++ l1] = {delt, res_ + A, u, 1};
delt = B - A;
q2[++ l2] = {delt, res_ + B, u, 1};
}
}
}
sort(q1 + 1, q1 + l1 + 1, [](Node x, Node y){
if(x.dt != y.dt) return x.dt > y.dt;
return x.typ < y.typ;
});
priority_queue<pii> Q1;
U(i, 1, l1){
if(q1[i].typ == 0) Q1.push({q1[i].val, q1[i].c});
else{
if(Q1.empty()) continue;
if(Q1.top().y != q1[i].c) res = max(res, Q1.top().x + q1[i].val);
else{
pii x = Q1.top(); Q1.pop();
if(!Q1.empty()) res = max(res, Q1.top().x + q1[i].val);
Q1.push(x);
}
}
}
sort(q2 + 1, q2 + l2 + 1, [](Node x, Node y){
if(x.dt != y.dt) return x.dt > y.dt;
return x.typ < y.typ;
});
priority_queue<pii> Q2;
U(i, 1, l2){
if(q2[i].typ == 0) Q2.push({q2[i].val, q2[i].c});
else{
if(Q2.empty()) continue;
if(Q2.top().y != q2[i].c) res = max(res, Q2.top().x + q2[i].val);
else{
pii x = Q2.top(); Q2.pop();
if(!Q2.empty()) res = max(res, Q2.top().x + q2[i].val);
Q2.push(x);
}
}
}
cout << res << "\n";
return ;
}
```