Solution. LG9870 [NOIP2023] 双序列拓展

Description

给出一个长度为 $n$ 的数组 $A$ 和长度为 $m$ 的数组 $B$，你需要在一个 $n\times m$ 的网格图上从 $(1,1)$ 走到 $(n,m)$，每次可以移动一个 $(1,0)$、$(0,1)$ 或 $(1,1)$ 的向量，需要保证途径的所有点 $(i,j)$ 都同时满足 $A_i>B_j$ 或同时满足 $A_i<B_j$，问是否存在这样的路径。共 $q$ 次询问。

$1\le n,m\le 5\times 10^5,0\le q\le 60,0\le A_i,B_i<10^9$

Solution

上面的简要题意已经对原始题意做了相当一部分转化了，主要是我左思右想写题解的话还是这种描述最清晰，尽管我考场上并没有借用这种思维方式。

首先我们钦定所有 $(i,j)$ 都满足 $A_i>B_j$，如果是小于的话只需要对每个数都取相反数即可。

在网格图上，我们逐行考虑（也即以此考虑 $A$ 中的每个数），可以发现，对于第 $i$ 行而言，~~所有可能的路径终点应当可以表示为一个区间内所有小于 $A_i$ 的数~~，特别的，我们要求区间的左右端点都满足 $A_i>B_j$。上面这句话是错误的，但这不影响下面进行的操作，原因在于区间内一个小于 $A_i$ 但不可达的数左右两侧一定都有可达且小于它的数，移动端点时可能选取到的点一定是可达的。

从第 $i$ 行移动到第 $i+1$ 行时，左端点 $l$ 需要向右移动找到第一个 $B_l<A_{i+1}$，而右端点可以先尝试向右拓展直到找到第一个 $B_{r+1}\ge A_{i+1}$，否则向左移动找到第一个 $B_r<A_{i+1}$。无解条件为：

过程中出现了 $l>r$ ；
移动到第 $n$ 行时 $r<m$。

这样我们已经有了一个 $O(nm)$ 的做法，并且可以通过线段树二分优化至 $O(n\log m)$。

很显然题目期望的应该是线性做法，此时我们的右端点既可以向左移动也可以向右移动，我们的目标是将其改为单向移动，从而得到均摊线性的做法。

注意到，左端点的移动只在判断第一个无解条件时发挥作用，然而仔细思考会发现，左端点右移时是将较大的数弹出区间，较小的数总是保留在区间内。更进一步的，有解时，$B_{1\dots r}$ 中的最大值总是在我们维护的区间内，反过来说，无解当且仅当 $A_i\le \min_{1\le j\le r}\{B_j\}$，这样左端点就没有必要维护了。

同样的道理，我们会发现右端点左移也不会对判定第一个条件产生影响，于是我们只需要关注第二个条件即可。

结合特殊性质的启发我们发现，对于 $A$ 的某个前缀最大值 $A_p$ 而言，处理其前方数时的右端点左移操作都是没有意义的，反正到了 $p$ 时右端点又会被一口气推回来。于是我们在 $A$ 的全局最大值左侧都不需要左移右端点了。

继续在全局最大值右侧时的情况，延续上面的思路，首先我们当然需要在全局最大值时右端点被推至 $m$，否则后面也不可能继续右推了。此外我们发现，右端点左移时经过的所有数的最大值不能够大于等于 $A$ 中当前位置的后缀最大值，否则右端点就会被那个最大值拦住而无法回推。你会发现，维护这个条件正好相当于将我们在最大值左侧做的操作反过来做一遍（从后往前扫，将右端点尽可能左推，要求经过的最小值小于 $A_i$）。

也可以从网格图的角度直观的理解上面的结论，我们在前缀最大值处推动右端点，其余时候只要 $A_i$ 大于前缀最小值，那么最小值那一列都是被打通的，可以直接走到下一个前缀最大值处。以全局最大值为分界线上下两部分分别做即可。

总复杂度 $O(q(n+m))$。

Code

删减过的考场代码。

namespace Main{
    const int N = 500005;
    int c, n, m, q, a[N], b[N], oa[N], ob[N];
    bool check(){
        int mn = 1e9, r = 0;
        for(int i = 1; i <= n; i++){
            while(r < m && b[r + 1] < a[i]) mn = min(mn, b[++r]);
            if(a[i] <= mn) return false;    
        }
        return r == m;
    }
    bool solve(){
        if(a[1] == b[1]) return false;
        if(a[1] < b[1]){
            for(int i = 1; i <= n; i++) a[i] = (int)1e9 - a[i];
            for(int i = 1; i <= m; i++) b[i] = (int)1e9 - b[i];
        }
        if(!check()) return false;
        reverse(a + 1, a + n + 1), reverse(b + 1, b + m + 1);
        return check();
    }
    void Main(){
        input(c, n, m, q);
        for(int i = 1; i <= n; i++) input(oa[i]);
        for(int i = 1; i <= m; i++) input(ob[i]);
        copy(oa + 1, oa + n + 1, a + 1);
        copy(ob + 1, ob + m + 1, b + 1);
        putchar('0' + solve());
        while(q--){
            int ka, kb; input(ka, kb);
            copy(oa + 1, oa + n + 1, a + 1);
            copy(ob + 1, ob + m + 1, b + 1);
            while(ka--){
                int p, v; input(p, v);
                a[p] = v;
            }
            while(kb--){
                int p, v; input(p, v);
                b[p] = v;
            }
            putchar('0' + solve());
        }
        return;
    }
}

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

Catalog

Solution. LG9870 [NOIP2023] 双序列拓展

Description

Solution

Code