题解：P9104 [PA 2020] Królewski bal
george0929
·
·
题解
题意
用矩形若干异或的形式给出一个 n\times n 的 01 矩阵，把 0 看做左部点，1 看做右部点，如果两个不同值的点在同一行或同一列则连一条边。
有 q 次修改，每次反转矩阵中一个位置的值，你需要实时维护这个二分图的最大匹配。
### 题解
最大匹配肯定是不能直接维护的，有两种思路：
1. 维护 $cnt_{0}-\max\{|S|-|N(S)|\}$。
2. 维护 $n^2-\max |S_{独立集}|$。
实际上联立一下发现两个式子可以化为 $\max |S_{独立集}|=cnt_1+\max\{|S|-|N(S)|\}$，这个式子本身可以用调整法说明，即上述两个思路的式子等价，因此我们无需纠结到底用哪个。
考虑维护最大独立集大小，假设我们选择的若干个 $0$，那么可以选择与这些 $0$ 不同行且不同列的的 $1$，并且必定全选。
那么贪心地，我们肯定选择若干行和列，并且将这些行和列的交点上的 $0$ 全选，不在这些行列交点的 $1$ 全选。
记我们选择的行编号集合为 $S$，列编号集合为 $T$，同时计算 $S$ 和 $T$ 是不好做的，考虑使用调整法求最大独立集。
固定 $T$ 为全集，删掉若干个 $t\in T$。
令第 $i$ 行的 $0$ 个数为 $a_i$，第 $i$ 列的 $1$ 个数为 $b_i$，扫描线求得 $a$ 和 $b$。
初始时，最大独立集为 $\sum\limits_{i\in S} a_i$。
删掉一个 $t$，会删除第 $t$ 列中行编号在 $S$ 内的 $0$，加上行编号不在 $S$ 内的 $1$。
独立集大小的变化量为列内的 $S$ 外的 $1$ 个数减去 $S$ 内的 $0$ 个数，即 $S$ 外 $1$ 的个数减去 $|S|$ 再加上 $S$ 中 $1$ 的个数，即 $b_i-|S|$。
我们发现调整时每列独立，且变化量只与 $|S|$ 有关。
贪心地，我们枚举 $|S|$，选择前 $|S|$ 大的 $a$，之后求 $\sum \max(0,b_i-|S|)$。
那么我们可以轻松得到 $O(nq)$ 的做法。
写一下最大独立集大小的式子，先把 $a$ 从大到小排序。
$$
\max |S_{独立集}|=\max\limits_{x=0}^{n} \{sa_x+\sum\limits_{i=1}^{n} \max(0,b_i-x)\}
\\
\max |S_{独立集}|=\max\limits_{x=0}^{n} \{sa_x+\sum\limits_{i=1}^{n} [b_i\geq x]b_i-x\sum\limits_{i=1}^{n} [b_i\geq x]1\}
$$
我们发现这个东西可以用线段树维护，具体地令 $f(x)=sa_x+\sum\limits_{i=1}^{n} [b_i\geq x]b_i-x\sum\limits_{i=1}^{n} [b_i\geq x]1$，开一颗线段树维护 $f$，每次会把 $a$ 的某一位和 $b$ 的某一位加减 $1$，每次修改实现 $a$ 的单点加减，实时维护 $a$ 有序并维护 $a$ 的前缀和，$b$ 的修改也是好维护的。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,q;
vector<pair<ll,ll>> Row[300005],Col[300005];
ll a[300005],b[300005];
struct _sgt1{
struct node{
ll l,r,sum,tag;
}t[1200005];
void pushup(ll p){
t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
void rev(ll p){
t[p].tag^=1,t[p].sum=t[p].r-t[p].l+1-t[p].sum;
}
void pushdown(ll p){
if(t[p].tag){
rev(p*2),rev(p*2+1);
t[p].tag=0;
}
}
void build(ll p,ll l,ll r){
t[p].sum=t[p].tag=0;
t[p].l=l,t[p].r=r;
if(l==r) return;
ll mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}
void modify(ll p,ll l,ll r){
if(l<=t[p].l&&t[p].r<=r){
rev(p);
return;
}
pushdown(p);
ll mid=(t[p].l+t[p].r)/2;
if(mid>=l) modify(p*2,l,r);
if(mid<r) modify(p*2+1,l,r);
pushup(p);
}
ll query(ll p,ll pos){
if(t[p].l==t[p].r) return t[p].sum;
ll mid=(t[p].l+t[p].r)/2;
pushdown(p);
if(mid>=pos) return query(p*2,pos);
else return query(p*2+1,pos);
}
}sgt1;
struct _sgt2{
struct node{
ll l,r,mx,tag;
}t[1200015];
void pushup(ll p){
t[p].mx=max(t[p*2].mx,t[p*2+1].mx);
}
void add(ll p,ll v){
t[p].mx+=v,t[p].tag+=v;
}
void pushdown(ll p){
if(t[p].tag){
add(p*2,t[p].tag),add(p*2+1,t[p].tag);
t[p].tag=0;
}
}
void build(ll p,ll l,ll r,ll arr[]){
t[p].l=l,t[p].r=r;
if(l==r){
t[p].mx=arr[l];
return;
}
ll mid=(l+r)/2;
build(p*2,l,mid,arr);
build(p*2+1,mid+1,r,arr);
pushup(p);
}
void modify(ll p,ll l,ll r,ll v){
if(l<=t[p].l&&t[p].r<=r){
add(p,v);
return;
}
pushdown(p);
ll mid=(t[p].l+t[p].r)/2;
if(mid>=l) modify(p*2,l,r,v);
if(mid<r) modify(p*2+1,l,r,v);
pushup(p);
}
}sgt2;
struct qry{
ll x,y,col,id;
}qr[300005];
ll cntb[300005],res0[300005];
set<ll> S[300005];
struct aval{
ll a,id;
}A[300005];
ll pos[300005];
ll bound(ll x){
ll l=1,r=n,p=0;
while(l<=r){
ll mid=(l+r)/2;
if(A[mid].a>=x){
p=mid;
l=mid+1;
}else r=mid-1;
}
return p;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>q;
for(ll i=1;i<=m;i++){
ll x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
Row[x1].push_back({y1,y2});
Row[x2+1].push_back({y1,y2});
Col[y1].push_back({x1,x2});
Col[y2+1].push_back({x1,x2});
}
for(ll i=1;i<=q;i++){
cin>>qr[i].x>>qr[i].y;
qr[i].id=i;
}
sort(qr+1,qr+1+q,[&](qry x,qry y){
return x.x<y.x;
});
ll Pos=0;
sgt1.build(1,1,n);
for(ll x=1;x<=n;x++){
for(auto opt:Row[x]){
ll l=opt.first,r=opt.second;
sgt1.modify(1,l,r);
}
while(Pos<q&&qr[Pos+1].x<=x){
Pos++;
qr[Pos].col=sgt1.query(1,qr[Pos].y);
}
a[x]=n-sgt1.t[1].sum;
}
sort(qr+1,qr+1+q,[&](qry x,qry y){
return x.id<y.id;
});
sgt1.build(1,1,n);
for(ll y=1;y<=n;y++){
for(auto opt:Col[y]){
ll l=opt.first,r=opt.second;
sgt1.modify(1,l,r);
}
b[y]=sgt1.t[1].sum;
}
for(ll i=1;i<=n;i++) A[i]={a[i],i};
sort(A+1,A+1+n,[&](aval x,aval y){
return x.a>y.a;
});
for(ll i=1;i<=n;i++) res0[i]=res0[i-1]+A[i].a;
for(ll i=1;i<=n;i++) pos[A[i].id]=i;
ll sumb=0,cnt=0;
for(ll i=1;i<=n;i++){
cntb[b[i]]++;
cnt++,sumb+=b[i];
}
for(ll x=0;x<=n;x++){
res0[x]+=sumb-x*cnt;
sumb-=cntb[x]*x;
cnt-=cntb[x];
}
sgt2.build(1,0,n,res0);
cout<<n*n-sgt2.t[1].mx<<"\n";
for(ll i=1;i<=q;i++){
ll x=qr[i].x,y=qr[i].y;
if(S[x].count(y)) qr[i].col=!qr[i].col;
if(S[x].count(y)) S[x].erase(y);
else S[x].insert(y);
if(qr[i].col){
ll p=bound(A[pos[x]].a+1)+1;
ll tmpid=A[p].id;
swap(A[pos[x]].id,A[p].id);
swap(pos[x],pos[tmpid]);
A[p].a++;
sgt2.modify(1,p,n,1);
if(b[y]>0) sgt2.modify(1,0,b[y]-1,-1);
b[y]--;
}else{
ll p=bound(A[pos[x]].a);
ll tmpid=A[p].id;
swap(A[pos[x]].id,A[p].id);
swap(pos[x],pos[tmpid]);
A[p].a--;
sgt2.modify(1,p,n,-1);
sgt2.modify(1,0,b[y],1);
b[y]++;
}
cout<<n*n-sgt2.t[1].mx<<"\n";
}
return 0;
}
```