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

D2T1 · 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 列中白格子个数。

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

目前为白，所在的列选白。
目前为白，所在的列选黑。
目前为黑，所在的列选白。
目前为黑，所在的列选黑。

若一行由白变为黑，那么对答案的贡献是情况 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;
}