P9361 [ICPC2022 Xi'an R] Contests 题解

under_the_time · 2023-10-02 15:33:53 · 题解

update on 2025-11-20

注意到我 2023 年写的题解有点不知所云，因此进行重构。感谢管理审核 'w'

题意

给定 m 个 1\sim n 的排列 p_1,p_2,\cdots,p_m，令 q_{i,j} 表示第 i 个元素在 p_j 中的排名，Q 次询问，每次给定 x,y，求出最小的 l，使得存在两个长度为 l+1 的序列 \set{b_i},\set{c_i}，使得 b_1=x,b_{l+1}=y 并且 \forall i\in[1,l]\cap \Z,q_{b_i,c_i}<q_{b_{i+1},c_{i+1}}；或者报告无解。

题解

对于一组询问 (x,y)，不妨考虑当 b_1=x 时 b_2 有哪些取值。可以发现就是所有 p 中以 x 开头的后缀取并集；再走一步，b_3 就是把 b_2 可以取的所有元素拿出来，把它们在每个排列中以它们开头的后缀拿出来再取并集；对于同一个 p_i，一个后缀和另一个后缀取并集留下的仍然是一段后缀（并且是较长的那个）。因此我们总可以通过 m 个排列各取一个后缀 [t_{i,1},t_{i,2},\cdots,t_{i,m}] 然后取并集来描述某个 b_i 的所有取值。而某个 l 合法当且仅当存在一个 k\in[1,m] 使得 y\ge t_{l+1,k}。

注意到合法的 l 在值域上一定是一段后缀，具有单调性，因此可以考虑二分 / 倍增算法。二分显然不现实，不同的 b_1 得到的 t 显然不一样，因此无法预处理 t。考虑倍增，设 f(x,i) 表示当 b_1=x 时 t_{2^i\color{red}+1} 的形态（也就是说 f(i,j) 是一个长度为 m 的序列），特殊处理 f(x,0) 的值，现在希望计算 f(x,i+1)。处理出 h(u,v,i) 为一个长度为 m 的序列，满足

意思就是把 p_u 长度为 v 的后缀中元素取出来，求出以它们为 b_1 得到的合法 b_{2^i+1} 的并集。那么就有

每一轮倍增先算 h 再转移 f，这部分复杂度 O(nm^2\log n)。

对于一次询问，倍增过程中维护当前 l 的和以及合法 b_{l+1} 的集合 [t_1,t_2,\cdots,t_m]（第一步跳的时候是一个单点 x），用倍增预处理出的 h 即可得到从当前状态走 2^i 得到的状态，若下一步状态仍不能覆盖到 y 则就跳。复杂度 O(Qm^2\log n)。

代码

#include <bits/stdc++.h>
bool MemoryST; using namespace std;
#define ll long long
#define mk make_pair
#define open(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define lowbit(x) ((x) & (-(x)))
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define BCNT __builtin_popcount
#define cost_time (1e3 * clock() / CLOCKS_PER_SEC) << "ms"
#define cost_space (abs(&MemoryST - &MemoryED) / 1024.0 / 1024.0) << "MB"
const int inf = 0x3f3f3f3f; 
const ll linf = 1e18; 
mt19937 rnd(random_device{}());
template<typename T> void chkmax(T& x, T y) { x = max(x, y); }
template<typename T> void chkmin(T& x, T y) { x = min(x, y); }
template<typename T> T abs(T x) { return (x < 0) ? -x : x; }
const int maxn = 1e5 + 5, maxm = 10;
int n, Q, m; int p[maxm][maxn], rnk[maxn][maxm];
int f[maxn][20][maxm], h[maxm][maxn][20][maxm];
int t[maxm], nxt[maxm];
bool vld(int y) {
    for (int i = 1; i <= m; i ++) if (nxt[i] <= rnk[y][i]) return 1;
    return 0;
}
bool MemoryED; int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i ++) 
        for (int j = 1; j <= n; j ++) scanf("%d", &p[i][j]), rnk[p[i][j]][i] = j;
    for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) f[i][0][j] = rnk[i][j];
    for (int i = 0; i <= 18; i ++) {
        for (int k = 1; k <= m; k ++)
            for (int u = 1; u <= m; u ++) {
                for (int v = n; v; v --) 
                    h[u][v][i][k] = min(v == n ? inf : h[u][v + 1][i][k], f[p[u][v]][i][k]); 
            }
        if (i == 18) break;
        for (int x = 1; x <= n; x ++)
            for (int k = 1; k <= m; k ++) {
                f[x][i + 1][k] = inf;
                for (int j = 1; j <= m; j ++) chkmin(f[x][i + 1][k], h[j][f[x][i][j]][i][k]);
            }
    } scanf("%d", &Q);
    for (int _ = 1, x, y; _ <= Q; _ ++) {
        scanf("%d %d", &x, &y); int ans = 0; bool beg = 0, ok = 0;
        for (int i = 18; ~i; i --) {
            if (!beg) for (int j = 1; j <= m; j ++) nxt[j] = f[x][i][j];
            else for (int j = 1; j <= m; j ++) {
                nxt[j] = inf;
                for (int k = 1; k <= m; k ++) chkmin(nxt[j], h[k][t[k]][i][j]);
            } if (vld(y)) ok = 1;
            else { ans += (1 << i), beg = 1; for (int j = 1; j <= m; j ++) t[j] = nxt[j]; }
        } if (!ok) puts("-1");
        else printf("%d\n", ans + 1);
    }
    return 0;
}