专栏文章

题解：P9104 [PA 2020] Królewski bal

ggeorge0929
P9104题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min5c6w0
此快照首次捕获于
2025/12/01 20:49
3 个月前
此快照最后确认于
2025/12/01 20:49
3 个月前
查看原文

题意

用矩形若干异或的形式给出一个 n×nn\times n 的 0101 矩阵，把 00 看做左部点，11 看做右部点，如果两个不同值的点在同一行或同一列则连一条边。
有 qq 次修改，每次反转矩阵中一个位置的值，你需要实时维护这个二分图的最大匹配。
1≤n,q≤3×1051\leq n,q\leq 3\times 10^5。

题解

最大匹配肯定是不能直接维护的，有两种思路：
  1. 维护 cnt0−max⁡{∣S∣−∣N(S)∣}cnt_{0}-\max\{|S|-|N(S)|\}。
  2. 维护 n2−max⁡∣S独立集∣n^2-\max |S_{独立集}|。
实际上联立一下发现两个式子可以化为 max⁡∣S独立集∣=cnt1+max⁡{∣S∣−∣N(S)∣}\max |S_{独立集}|=cnt_1+\max\{|S|-|N(S)|\}，这个式子本身可以用调整法说明，即上述两个思路的式子等价，因此我们无需纠结到底用哪个。
考虑维护最大独立集大小，假设我们选择的若干个 00，那么可以选择与这些 00 不同行且不同列的的 11，并且必定全选。
那么贪心地，我们肯定选择若干行和列，并且将这些行和列的交点上的 00 全选，不在这些行列交点的 11 全选。
记我们选择的行编号集合为 SS，列编号集合为 TT，同时计算 SS 和 TT 是不好做的，考虑使用调整法求最大独立集。
固定 TT 为全集，删掉若干个 t∈Tt\in T。
令第 ii 行的 00 个数为 aia_i，第 ii 列的 11 个数为 bib_i，扫描线求得 aa 和 bb。
初始时，最大独立集为 ∑i∈Sai\sum\limits_{i\in S} a_i。
删掉一个 tt，会删除第 tt 列中行编号在 SS 内的 00，加上行编号不在 SS 内的 11。
独立集大小的变化量为列内的 SS 外的 11 个数减去 SS 内的 00 个数，即 SS 外 11 的个数减去 ∣S∣|S| 再加上 SS 中 11 的个数，即 bi−∣S∣b_i-|S|。
我们发现调整时每列独立，且变化量只与 ∣S∣|S| 有关。
贪心地，我们枚举 ∣S∣|S|，选择前 ∣S∣|S| 大的 aa，之后求 ∑max⁡(0,bi−∣S∣)\sum \max(0,b_i-|S|)。
那么我们可以轻松得到 O(nq)O(nq) 的做法。
写一下最大独立集大小的式子，先把 aa 从大到小排序。
max⁡∣S独立集∣=max⁡x=0n{sax+∑i=1nmax⁡(0,bi−x)}max⁡∣S独立集∣=max⁡x=0n{sax+∑i=1n[bi≥x]bi−x∑i=1n[bi≥x]1}\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)=sax+∑i=1n[bi≥x]bi−x∑i=1n[bi≥x]1f(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，开一颗线段树维护 ff，每次会把 aa 的某一位和 bb 的某一位加减 11，每次修改实现 aa 的单点加减，实时维护 aa 有序并维护 aa 的前缀和，bb 的修改也是好维护的。
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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...