更详细的性质证明——JOISC2017 切符の手配题解

· · 题解

Update

形式化题意：

给定正整数 n,m 和 m 个三元组 (l_i,r_i,c_i)，你有一个序列 a_{1\ldots n}，初始所有元素为 0。

你需要对序列 a 进行 m 次操作，对于第 i=1,\cdots,m 次操作，你需要：

请你最小化 \max a_i 的值。

思路：

推性质神仙题。

这道题，某些人通过猜结论，调着调着就过拍了，然后交上去过了。

不得不说，这道题的性质太妙了，感觉只能通过打表看出来……

\textbf{Subtask 1}\sim\textbf{2}：

我们不妨先抛开 c_i>1 的情况，只考虑 c_i=1 时如何做。这样我们将问题转化成，初始每个区间都未反转，我们需要反转一些区间，使得操作后 \max a_i 尽可能地小。这里，我们定义反转一个区间 [l_i,r_i] 为，将其对全集 [1,n] 取补，变为集合 [1,l_i)\cup (r_i,n]。

记多重集 S 为我们选出的需要反转的区间的集合，下文我们同时称 S 为一个反转方案。

性质 1：答案具有单调性。我们记答案的上界为 T。如果存在一种反转方案，使得 \max a_i=x，则对于所有 y\in(x,T]，也存在一种反转方案使得 \max a_i=y。

这说明，我们可以尝试用二分答案解决这个问题。

性质 2：若 S 中的所有区间之交为空，则这种反转方案一定不优。

证明：显然，此时存在区间 U_1,U_2\in S，满足 U_1\cap U_2=\varnothing，如果我们同时反转这两个区间，我们讨论反转后产生的贡献：

  • 所有 i\in U_1\cup U_2 的 a_i 不变。
  • 所有 j\notin U_1\cup U_2 的 a_j 会加上 2。

由于反转后没有 a_i 会减少，所以这种反转方案不优。

也就是说，如果这 m 个区间存在一个子集有交，则存在一种最优方案，使得存在下标 t\in I，其中区间 I=[L,R] 为 S 中的所有区间之并。

我们尝试二分答案 x。接下来我们讨论如何判定 x 是否合法。

我们记 p_i 表示所有区间不反转时，所有操作进行完后 a_i 的值，q_i 表示对于当前集合 S，将 S 中的区间反转后，所有操作进行完后 a_i 的值。记 z_i=\sum_{A\in S}[i\in A]，则 q_i=p_i-z_i+|S|-z_i=p_i+z_t-2z_i。由于 q_i\leq x，我们得到 p_i+z_t-2z_i\leq x。也就是说，要使得 x 合法，必须存在一个 S，使得通过其推导出的 z_i 满足

z_i\geq \left\lceil\dfrac{p_i+z_t-x}{2}\right\rceil

此时我们能够发现，如果我们确定了 t 和 z_t，则我们可以确定所有 z_i(i\not=t) 的下界，即每个下标至少需要被 S 中的多少个区间覆盖。这时，找出一个满足条件的 S 也就变得容易了。

至此，我们可以通过枚举 t 和 z_t 的值，然后贪心地每次将 z_i 取得尽量小。具体地，我们计算出每个 z_i 的下界，然后依次遍历 i=1,\cdots,t，尝试将 z_i 累加到下界（累加不到则当前 t,z_t 不合法），每次取区间时，考虑从左端点小于等于 i 的区间中贪心地选出右端点最大的加入 S。遍历完后，只需检查 z_i(t<i\leq n) 是否不小于下界即可。这样我们就设计出了一个判定 x 是否合法的朴素算法，外层再套一个二分即可得出答案。

注意，因为 t\in I，所以对于任意 1\leq i\leq n，z_t 同时需要满足 \left\lceil\dfrac{p_i+z_t-x}{2}\right\rceil\leq z_i\leq z_t，即 z_t\geq p_i-x。也就是说，当 z_t<p_i-x 时我们可直接判定 z_t 不合法。如果我们枚举 z_t 时不从下界 \max p_i-x 开始，并且在判定 x 是否合法时，仅仅只通过判定 z_i 是否达到下界验证 x 的合法性，则算法的正确性无法保证。（想一想，为什么）

对于 c_i=1 的情况，二分答案的时间为 O(\log m)，枚举 t,z_t 的时间为 O(nm)，贪心算法的时间为 O((n+m)\log m)，则总时间复杂度为 O(nm(n+m)\log^2 m)。

对于 c_i>1 的情况，记 V=\max p_i，则二分答案的时间为 O(\log V)，枚举 t,z_t 的时间为 O(nV)，贪心算法的时间不变（在代码中非常自然地改一下即可），则总时间复杂度为 O(nV(n+m)\log m\log V)。

这里给出贪心算法的代码：

// 所有变量名与之前约定的记号含义相同
// 所有三元组 (li,ri,ci) 都存储在 vec[li] 中
// 保证 zt 从下界 max(pi) - x 开始枚举

bool valid(long long x, int t, long long zt) {
    for (int i = t + 1; i <= n; i ++) {
        z[i] = 0;
    }

    std::priority_queue<Interval> q;
    long long zi = 0;

    for (int i = 1; i <= t; i ++) {
        long long lim = (p[i] + zt - x + 1) >> 1;

        for (int j = 0; j < vec[i].size(); j ++) {
            if (vec[i][j].r > t) {
                q.push(vec[i][j]);
            }
        }

        while (q.size() && zi < lim) {
            Interval iter = q.top();
            q.pop();

            int delta = std::min(lim - zi, (long long) iter.c);
            zi += delta;
            z[iter.r] -= delta;

            if (iter.c -= delta) {
                q.push(iter);
            }
        }

        if (zi < lim) {
            return false;
        }
    }

    z[t] = zi;
    for (int i = t + 1; i <= n; i ++) {
        if (((z[i] += z[i - 1]) << 1) < p[i] + zt - x) {
            return false;
        }
    }

    return true;
}

其中 Interval 类和变量 vec 的定义如下：

class Interval {
public:
    int l, r, c;

    bool operator < (const Interval& rhs) const {
        return r < rhs.r;
    }
};

std::vector<Interval> vec[maxn];

比较明显的是，如果略去枚举 t,z_t 的时间，总时间复杂度为 O((n+m)\log m\log V)，在该题目限制下可以接受。最优的 t,z_t 只有 O(1) 种？或是说，我们只需要枚举 O(1) 个 t,z_t？

\textbf{Subtask 3}：

贪心算法的时间复杂度看起来已经不可优化了，我们尝试挖掘更多的性质，优化枚举 t,z_t 的时间。

性质 3：存在一种最优方案，满足 |S|=0 或 \max_{i\in I}q_i\geq \max q_i-1。

证明：我们假设命题不成立，并尝试推导出矛盾。根据条件，当前最优方案满足 \max_{i\in I}q_i\leq \max q_i-2。

首先我们证明，当前方案中不存在区间 U\in S 使得 U=I。

实际上，假设存在这样的区间，我们考虑将 U 从 S 中删除，即不翻转 U。记 S' 为删除 U 后的多重集 S，q_i' 为删除 U 后的 q_i。我们分析 q_i 与 q_i' 的关系：

  • 对于所有 i\notin I，q_i'=q_i-1。
  • 对于所有 j\in I，q_j'=q_j+1。

显然，q_i 满足 x=\arg\max q_i\notin I，则 q_x'=q_x-1。为了保证 S 的最优性，我们只好让 \max q_i'\geq q_x，由此可推导出 \arg\max q_i'\in I，进而得到 \max q_i'=\max_{i\in I}q_i+1\geq q_x=\max q_i，此与假设矛盾。因此，当前方案中不存在这样的区间。同时，我们可以得知当前方案中，S 中一定存在一个左端点为 L 的区间和一个右端点为 R 的区间（其中 I=[L,R]，且这两个区间不同）。

现在，我们考虑以下调整算法：

  1. 如果当前 |S|\leq 2 或者已满足 \max_{i\in I}q_i\geq \max q_i-1，结束调整。
  2. 否则，我们从 S 中分别选择一个左端点为 L 的区间和一个右端点为 R 的区间，然后将它们从 S 中删除。显然，这样调整后的方案仅仅只对于所有 i\in I 的 q_i 增加了 2，其它的 q_i 不增，不劣于最优方案。然后我们回到步骤 1。

我们对当前方案进行以上调整算法，然后得到新的多重集 S_0。

若当前方案 S_0 仍然有 \max_{i\in I}q_i\leq \max q_i-2，一方面，我们容易知道 S_0 满足 |S_0|\leq 2；另一方面，我们在之前已经证明，若当前方案满足 \max_{i\in I}q_i\leq \max q_i-2，则不存在区间 U\in S_0 使得 U=I，因此 |S_0|\not=1。综合这两方面，我们得知 |S_0|=2。

所以，我们仍然从 S_0 中分别选择一个左端点为 L 的区间和一个右端点为 R 的区间，然后将它们从 S 中删除。容易知道这样的调整一定不劣于最优方案。调整后 |S_0|=0，此与假设矛盾。

综上所述，命题成立。

这说明我们不需要大范围地枚举 z_t 了。若当前位置 t\in I 存在最优方案满足 \max_{i\in I}q_i\geq \max q_i-1，我们只需要判定 z_t=p_t-x 和 z_t=p_t-x+1 两种情况中有其中一个合法即可。

总时间复杂度降至 O(n(n+m)\log m\log V)。

\textbf{Subtask 4}\sim\textbf{5}：

既然我们优化掉了枚举 z_t 的时间，那么 t 是不是也可以像 z_t 一样，不需要枚举呢？ 我们随便猜一个结论然后跑一遍， 可以发现：

性质 4：令 t=\arg\max_{i\in I}q_i，若存在一种最优方案 S(|S|>0) 满足 q_t\geq \max q_i-1，则 S 同时满足 p_t=\max p_i。

证明：仍然考虑反证。若存在最优方案 S(|S|>0) 满足 q_t\geq \max q_i-1,p_t\leq\max p_i-1，则我们可推导出 x=\arg\max p_i\notin I，因此 S 中至少存在一个区间没有覆盖到 x，即 z_x\leq z_t-1。我们得到

p_x\geq p_t+1,z_x\leq z_t-1

注意到，q_x=p_x-2z_x+z_t,q_t=p_t-z_t，所以我们尝试对上述不等式做变换得到

\begin{aligned}p_x-2z_x&\geq p_t-2z_t+3 \\p_x-2z_x+z_t&\geq p_t-z_t+3 \\q_x&\geq q_t+3\end{aligned}

此与假设条件 q_t\geq \max q_i-1 矛盾。因此命题成立。

至此，我们又将 t 的范围缩小到 t\in\{x|p_x=\max p_i\}。

既然都到这一步了，我们继续猜测，是不是我们只要让 t 满足 p_t=\max p_i 就能够找到满足之前性质的最优解（找不到则 S=\varnothing 为最优方案之一）？

性质 5：若存在一种最优方案 S(|S|>0) 满足 \max_{i\in I}q_i\geq \max q_i-1，则 S 同时满足 \{x|p_x=\max p_i\}\subseteq I。

证明：类似性质 4 的证明，我们考虑反证。令 t=\arg\max_{i\in I}q_i，若当前最优方案 S 满足 q_t\geq \max q_i-1，且存在 x 满足 x\notin I,p_x=\max p_i，则我们有

p_x=p_t,z_x\leq z_t-1

综合上述不等式可得

\begin{aligned}p_x-2z_x+z_t&\geq p_t-z_t+2 \\q_x&\geq q_t+2\end{aligned}

此与假设条件 q_t\geq \max q_i-1 矛盾。因此命题成立。

据性质 5，我们可推断出，若存在一种最优方案 S(|S|>0) 满足 \max_{i\in I}q_i\geq \max q_i-1，则对于所有 p_x=\max p_i 的 x，q_x=p_x-z_x 都相同（想一想，为什么）。所以，我们只需要令 t 为集合 \{x|p_x=\max p_i\} 的其中一个元素，在二分时对于 (t,p_t-x) 和 (t,p_t-x+1) 两种情况分别跑一遍贪心算法，即可做到判断当前答案 x 是否大于等于最优解。

总时间复杂度降至 O((n+m)\log m\log V)，足以通过此题。