自动搬运

查看原文

来自洛谷，原作者为

	D2T1 没复活就是似了 | 头发绿绿戴个帽帽，脑袋大大，喜欢唱唱

搬运于2025-08-24 22:45:23，当前版本为作者最后更新于2025-07-04 21:45:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

转化题意，对两种表演方式（设为黑/白）建二分图，左侧黑右侧白，两个点连边当且仅当在同一行或者同一列。那么答案就是这张二分图的最大匹配。

最大匹配显然是不好做的，考虑转化为 $n^2-$ 最大独立集。

最大独立集在原方阵中形如怎么样的呢？形如每一行/每一列中选的格子只会有一种颜色。也就是说可以通过如下方式得到一个独立集：枚举列、行中选择白色的集合 $S,T$，对于点 $(x,y)$，若目前为白且 $x\in T,y\in S$ 即贡献 $1$；若目前为黑且 $x\notin T,y\notin S$ 即贡献 $1$。

枚举列选择的方案，设集合 $S$ 中的列选了白，所有行都选了白。则现在的贡献是这 $S$ 列中白格子个数。

考虑每一行变为黑是否会增加答案。对于行上的点有四种情况：

1. 目前为白，所在的列选白。
2. 目前为白，所在的列选黑。
3. 目前为黑，所在的列选白。
4. 目前为黑，所在的列选黑。

若一行由白变为黑，那么对答案的贡献是情况 $4$ 的点数减去情况 $1$ 的点数。有点麻烦，稍微推推式子可以得到一个惊人的结论：对答案的贡献是行内黑格子数减去白的列数，即贡献与 $S$ 具体内容没有任何关系，只和 $|S|$ 有关！那么行与列的决策就相对独立了。

于是计算出 $a$ 数组表示每一列的白格子数，$b$ 数组表示出每一行的黑格子数，那么答案可以写作：

$$\max_{x=0}^n\{\sum_{i=1}^n\max(0,b_i-x)+\sum_{i=1}^x A_i\} $$

其中 $A$ 为 $a$ 数组降序排好序的结果。

对于第一次询问，可以扫描线预处理出 $a,b$ 数组后计算答案。考虑修改，使用线段树维护每个 $x$，上述式子的值。修改形如 $a,b$ 的单点修改，也即 $A,b$ 的单点修改，带入上述式子容易发现都是一个区间修改。使用一个区间修、询问全局 $\max$ 的线段树即可维护。

复杂度 $O(n\log n)$。

代码中 $a,b$ 表示的行列与题解描述的相反。

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;

const int N = 3e5 + 10;
int n, m, Q;
vector<int> qry[N];
vector<pair<int, int> > cg[N], cgg[N];
int qx[N], qy[N], val[N], to[N];

struct segtree{
	int t[N*4], tag[N*4];
	void psd(int p, int l, int r){
		int mid = l + r >> 1;
		if(tag[p]){
			t[p<<1] = (mid - l + 1) - t[p<<1];
			t[p<<1|1] = (r - mid) - t[p<<1|1];
			tag[p<<1] ^= 1;
			tag[p<<1|1] ^= 1;
			tag[p] = 0;
		}
	}
	void build(){
		memset(t, 0, sizeof(t));
		memset(tag, 0, sizeof(tag));
	}
	void rev(int p, int l, int r, int ql, int qr){
		if(qr < l || r < ql){
			return;
		} else if(ql <= l && r <= qr){
			t[p] = (r - l + 1) - t[p];
			tag[p] ^= 1;
		} else {
			int mid = l + r >> 1;
			psd(p, l, r);
			rev(p<<1, l, mid, ql, qr);
			rev(p<<1|1, mid+1, r, ql, qr);
			t[p] = t[p<<1] + t[p<<1|1];
		}
	}
	int ask(int p, int l, int r, int ql, int qr){
		if(qr < l || r < ql){
			return 0;
		} else if(ql <= l && r <= qr){
			return t[p];
		} else {
			int mid = l + r >> 1;
			psd(p, l, r);
			return ask(p<<1, l, mid, ql, qr) + ask(p<<1|1, mid+1, r, ql, qr);
		}
	}
} t;

int a[N], b[N];
int A[N];
int al[N], ar[N];
ll tb[N];

struct seggtree{
	ll t[N*4], tag[N*4];
	void psd(int p){
		tag[p<<1] += tag[p];
		tag[p<<1|1] += tag[p];
		t[p<<1] += tag[p];
		t[p<<1|1] += tag[p];
		tag[p] = 0;
	}
	void add(int p, int l, int r, int ql, int qr, ll v){
		if(qr < l || r < ql){
			return;
		} else if(ql <= l && r <= qr){
			t[p] += v;
			tag[p] += v;
		} else {
			int mid = l + r >> 1;
			psd(p);
			add(p<<1, l, mid, ql, qr, v);
			add(p<<1|1, mid+1, r, ql, qr, v);
			t[p] = max(t[p<<1], t[p<<1|1]);
		}
	}
	ll qrymx(){
		return t[1];
	}
} tt;

map<int, int> id[N];
int idc;

int main(){
	scanf("%d%d%d", &n, &m, &Q);
	for(int i = 1; i <= m; ++ i){
		int x, y, xx, yy;
		scanf("%d%d%d%d", &x, &y, &xx, &yy);
		cg[x].push_back(make_pair(y, yy));
		cg[xx+1].push_back(make_pair(y, yy));
		cgg[y].push_back(make_pair(x, xx));
		cgg[yy+1].push_back(make_pair(x, xx));
	}
	for(int i = 1; i <= Q; ++ i){
		int x, y;
		scanf("%d%d", &x, &y);
		qx[i] = x;
		qy[i] = y;
		qry[x].push_back(i);
	}
	t.build();
	for(int i = 1; i <= n; ++ i){
		for(pair<int, int> p : cg[i]){
			t.rev(1, 1, n, p.first, p.second);
		}
		A[i] = a[i] = n - t.ask(1, 1, n, 1, n);
		for(int p : qry[i]){
			if(!id[i][qy[p]]){
				id[i][qy[p]] = ++ idc;
			}
			val[id[i][qy[p]]] = t.ask(1, 1, n, qy[p], qy[p]);
		}
	}
	t.build();
	for(int i = 1; i <= n; ++ i){
		for(pair<int, int> p : cgg[i]){
			t.rev(1, 1, n, p.first, p.second);
		}
		b[i] = t.ask(1, 1, n, 1, n);
		++ tb[1];
		-- tb[b[i]+1];
	}
	sort(A + 1, A + n + 1);
	reverse(A + 1, A + n + 1);
	int la = n + 1;
	for(int i = 1; i <= n + 1; ++ i){
		ar[la] = i-1;
		for(int j = la - 1; j >= A[i]; -- j){
			al[j] = i;
			ar[j] = i-1;
		}
		if(la != A[i] && A[i] >= 0){
			la = A[i];
			al[A[i]] = i;
		}
	}
	for(int i = 1; i <= n; ++ i){
		tb[i] += tb[i-1];
		tt.add(1, 0, n, i, n, A[i]);
		tt.add(1, 0, n, 0, i-1, tb[i]);
	}
	printf("%lld\n", 1ll * n * n - tt.qrymx());
	for(int i = 1; i <= Q; ++ i){
		if(val[id[qx[i]][qy[i]]] == 1){
			int na = a[qx[i]];
			++ a[qx[i]];
			tt.add(1, 0, n, al[na], n, 1);
			++ al[na];
			++ ar[na+1];
			-- b[qy[i]];
			tt.add(1, 0, n, 0, b[qy[i]], -1);
		} else {
			int na = a[qx[i]];
			-- a[qx[i]];
			tt.add(1, 0, n, ar[na], n, -1);
			-- ar[na];
			-- al[na-1];
			tt.add(1, 0, n, 0, b[qy[i]], 1);
			++ b[qy[i]];
		}
		val[id[qx[i]][qy[i]]] ^= 1;
		printf("%lld\n", 1ll * n * n - tt.qrymx());
	}
	return 0;
}