Cowmpetency (USACO Silver 2024 January)

这个题我们可以找到 $\mathcal{O}(n)$ 的算法，关键是理解清楚题目中给出的 $(x,y)$ 的限制对的本质。

考虑一对限制 $(a_i,h_i)=(x,y)$ ，也就是“奶牛 $y$ 是第一头比奶牛 $1$ 到 $x$ 拥有更高cowmpetency的奶牛”，这意味着， $\max_{i=1}^x c_i < c_y$ ，且 $c_k \leq \max_{i=1}^x c_i (x < k < y)$ ，可以推出 $\max_{i=1}^{y-1} c_i < c_y$ ，也就是说 $c_y$ 是严格前缀最大值，而 $c_k (x<k<y)$ 一定不是严格前缀最大值。

定义 $b_i=-1/0/1$ ，表示 $c_i$ 一定不是/不一定是/一定是前缀最大值，我们可以 $\mathcal{O}(n)$ 求出所有 $b_i$ 。生成 $b_i$ 的方法如下：

对于每一对 $(x,y)$ ， $b_k=-1 (x+1\leq k \leq y-1)$ ，然后 $b_y=1$ 。
当多个区间有重合的时候，上面1的做法会导致 $\mathcal{O}(n^2)$ ，解决的办法，是我们观察到如果两个区间有重合，那么它们合法的条件就是两个 $y$ 值一样，如下面例子：

合法例子： (3,7)和(5,7)
            -1 -1 -1 1
                  -1 1

不合法例子：(3,7)和(4,6)
            -1 -1 -1 1
               -1 1

所以，我们一旦检测到区间有重合，只需要检查右边界( $y$ )是否一致就能判断是否合法，而且只需要设置一遍 $b_i$ 就可以。这里简单定义一个 $r_i$ 数组，记录每个位置对应的区间右边界就可以了（具体见代码）。这样，每个 $b_i$ 最多只被写入一次，所以是 $\mathcal{O}(n)$ 的。

得到 $b_i$ 之后，我们考虑结果的构造：

对于不确定的值（ $c_i=0$ ），我们简单地按照规则构造：

如果 $b_i=0$ 或 $b_i=-1$ ，那么 $c_i=1$
如果 $b_i=1$ ，那么 $c_i=\max_{j=1}^{i-1} c_j + 1$

对于已经有的值（ $c_i > 0$ ），存在以下两种可能有冲突的情况：

如果 $b_i=1$ ，且 $a_i \leq \max_{j=1}^{i-1}a_j$ ，则一定无解，因为前一步生成的已经是最小的前缀最大值，而 $a_i$ 比这个还小是无法满足的。
如果 $b_i=-1$ ，且 $a_i > \max_{j=1}^{i-1}a_j$ ，则有调整的空间：我们往前找到一个最大的 $k$ ， $c_k$ 是不确定的且 $b_k\neq-1$ ，此时设 $a_k=a_i$ ，就是字典序最小的可能结果。如果找不到这个 $k$ 则无解；如果这个调整引起 $[k+1,i-1]$ 范围内其它的限制被违反，也无解：因为冲突的位置一定是 $c$ 确定且 $b=1$ 的，没有进一步的调整的可能。这个调整的过程通过记录前面见过的可被改为更大的值的元素的方法可以 $\mathcal{O}(1)$ 实现（见代码中f）。

最后从前到后跑一遍规则的检查，就完成了。

这个题主要的困难在实现 $\mathcal{O}(n)$ 算法上面，思考难度比较高，不完全实现 $\mathcal{O}(n)$ 很多时候也是可以通过测试的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int T,N,Q,C;
int c[100005];
int b[100005];
int r[100005];    // right boundary of each [x+1,y] range
 
int main() {
    scanf("%d", &T);
    for (int t = 0; t < T; t++) {
        bool ok = true;
        scanf("%d %d %d", &N, &Q, &C);
        memset(c, 0, sizeof(c));
        memset(r, 0, sizeof(r));
        memset(b, 0, sizeof(b));
        for (int i = 1; i <= N; i++) {
            scanf("%d", &c[i]);
        }
        // fill b[i] values
        for (int q = 1; q <= Q; q++) {
            int x,y;
            scanf("%d %d", &x, &y);
            for (int i = x+1; i <= y; i++) {
                if (r[i] != 0 && r[i] != y) {
                    ok = false;
                }
                if (r[i] != 0) break;      // no need to check further as right boundary is the same
                b[i] = i == y ? 1 : -1;
                r[i] = y;
            }
        }
        // construct an answer - this is tricky
        int pmax = 0;
        int f = 0;   // free element that can be set to larger
        for (int i = 1; i <= N; i++) {
            if (b[i] == 0 && c[i] == 0) { c[i] = 1; f = i; }
            if (b[i] == -1) {
                if (c[i] == 0) c[i] = 1;
                if (c[i] > pmax) {
                    if (f == 0) {
                        ok = false;
                        break;
                    } else 
                        c[f] = c[i];
                }
            }
            if (b[i] == 1 && c[i] == 0) { c[i] = pmax + 1; f = i; }
            pmax = max(pmax, c[i]);
        }
        // check consistency
        pmax = 0;
        for (int i = 1; i <= N; i++) {
            if (b[i] == -1 && c[i] > pmax) {
                ok = false; break;
            }
            if (b[i] == 1 && c[i] <= pmax) {
                ok = false; break;
            }
            if (c[i] > C) {
                ok = false; break;
            }
            pmax = max(pmax, c[i]);
        }
        // output
        if (ok)
            for (int i = 1; i <= N; i++)
                printf("%d%s", c[i], i == N ? "\n" : " ");
        else
            printf("-1\n");
    }
 
 
    return 0;
}