「PA 2020」Królewski bal 题解

算法思路

本题使用线段树优化和组合数学来解决大规模矩阵匹配问题。核心思想是将问题建模为行列匹配，并通过维护统计信息来动态计算最大投掷次数。

关键观察

1. 问题转化

将 $n \times n$ 的矩阵看作二分图：

• 左部：$n$ 行
• 右部：$n$ 列
• 边：带呼啦圈的演员位置

最大投掷次数 = 最大匹配数

2. 数学公式

最大投掷次数可以表示为：

$$\text{答案} = n^2 - \sum_{i=1}^n a_i - \max_{0 \leq k \leq n} \left(k \cdot c_b[k] - s_a[k] - s_b[c_b[k]]\right) $$

其中：

• $a_i$：第 $i$ 行带呼啦圈的演员数
• $b_i$：第 $i$ 列带呼啦圈的演员数
• $s_a[k]$：$a$ 数组前 $k$ 小值的和
• $s_b[k]$：$b$ 数组前 $k$ 小值的和
• $c_b[k]$：$b$ 数组中 $\leq k$ 的元素个数

代码解析

数据结构定义

struct Segment {
    int sum[N << 2], tag[N << 2];  // 线段树维护区间和与懒标记
    inline void brush(reg int o, reg int len) {
        sum[o] = len - sum[o], tag[o] ^= 1;  // 区间翻转
    }
    // ... 线段树标准操作
} T1, T2;

初始化处理

// 处理顾问的矩形操作
for (reg int i = 1; i <= n; i++) {
    for (auto [l, r] : vc1[i])
        T1.modify(1, 1, n, l, r);  // 更新行状态
    a[i] = T1.sum[1];  // 获取第i行带呼啦圈的数量
    
    for (auto [l, r] : vc2[i]) 
        T2.modify(1, 1, n, l, r);  // 更新列状态
    b[i] = T2.sum[1];  // 获取第i列带呼啦圈的数量
}

关键线段树构建

void build(reg int o, reg int l, reg int r) {
    if (l == r)
        return mx[o] = l * cb[l] - sa[l] - sb[cb[l]], void();
    // 计算表达式：k * cb[k] - sa[k] - sb[cb[k]]
}

动态更新处理

for (reg int i = 1; i <= q; i++) {
    reg int x = qx[i], y = qy[i];
    
    if (col[{x, y}]) {
        // 原来有呼啦圈，现在移除
        sa[n]--;
        modify(1, 0, n, ++ca[--a[x]], n, 1);
        modify(1, 0, n, b[y]--, n, 1);
    } else {
        // 原来没有呼啦圈，现在添加
        sa[n]++;
        modify(1, 0, n, ca[a[x]++]--, n, -1);
        modify(1, 0, n, ++b[y], n, -1);
    }
    
    col[{x, y}] ^= 1;
    printf("%lld\n", getans());
}

算法正确性

匹配理论基础

根据Kőnig定理和Hall定理，在二分图中：

• 最大匹配 = 最小点覆盖
• 最大投掷次数 = $n^2 - \text{最小点覆盖}$

动态维护原理

每次单点修改只影响：

• 对应行的 $a_i$ 值
• 对应列的 $b_i$ 值
• 通过线段树高效维护统计信息

复杂度分析

• 预处理：$O(n \log n + m \log n)$
• 每次查询：$O(\log n)$
• 总复杂度：$O((n + m + q) \log n)$

关键技巧

1. 线段树维护：高效处理区间翻转和单点查询
2. 统计信息维护：动态维护排序后的前缀和
3. 表达式优化：将复杂的最优化问题转化为线段树维护
4. 增量更新：每次修改只更新受影响的部分