题解：P3570 [POI 2014] PRZ-Criminals

ACehomoxue · 2026-10-20 09:33:56 · 题解

简单题。

我们设 pre_i 表示 c 在第 i 个位置和 x 匹配到了 c_i，那么 x_1 最大可以在哪里，suf_i 表示 c 和 y 匹配匹配到了 i 和 c_i，y_1 的最小位置应该在哪里。这两个 O(n) 扫一遍是简单的。对于每一个 c_i = x_m，那么两个罪犯至少要经过的地方就应该是 [pre_i, suf_i]，简记为 [l_i, r_i]。现在判断每个是否合法，设颜色 k 出现的最早的位置在 s_k，最晚在 t_k，对于 i 合法，那么存在 [s_k, t_k] 使得 s_k < l_i \land r_i < t_k，这是一个类似二维偏序的东西，扫一遍即可。做完了。

:::success[code]

#include <bits/stdc++.h>
using namespace std;
#define int int
#define ll long long
#define usd unsigned
#define el putchar('\n')
#define lowbit(x) (x & (-x))
#define AC return 
#define AK return 0
#define YS cout << "YES"
#define NO cout << "NO"
#define Ys cout << "Yes"
#define No cout << "No"
#define ys cout << "yes"
#define no cout << "no"
#define ls(i) ch[i][0]
#define rs(i) ch[i][1]
#define debug(num) cerr << #num << ' ' << num << '\n'
#define void inline void
#define il inline
#define Mod(x) (((x) % mod + mod) % mod)
#define pii pair <int, int>
#define pll pair <ll, ll>
il char gc() { char c; while((c = getchar()) <= ' ') ; return c; }
il int rd() {
    char c; int x, f = 1;
    while(!isdigit(c = getchar())) if(c == '-') f *= -1;
    x = c ^ 48;
    while(isdigit(c = getchar())) x = (x << 3) + (x << 1) + (c ^ 48);
    return x * f;
}
void ACehomoxue();
signed main() {
    srand(time(0));
    int t = 1;
    // t = rd();
    while(t--) ACehomoxue();
    AK;
}
const int mod = 998244353, maxn = 1e6 + 6;

int n, k, c[maxn], m1, m2, s, pre[maxn], mx[maxn], suf[maxn], lst[maxn], frm[maxn], lf[maxn], rh[maxn];
vector <int> ans;

void ACehomoxue() {
    n = rd(), k = rd();
    for(int i = 1; i <= n; i++) c[i] = rd();
    m1 = rd(), m2 = rd();
    for(int i = 1; i <= k; i++) frm[i] = -1;
    for(int i = 1, pr = 0, x; i <= m1; i++) {
        x = rd();
        frm[x] = pr;
        pr = x;
        if(i == m1) s = x;
    }
    for(int i = 1; i <= n; i++) {
        if(frm[c[i]] == -1) continue;
        if(frm[c[i]] == 0) pre[i] = i;
        else pre[i] = pre[lst[frm[c[i]]]];
        lst[c[i]] = i;
    }
    suf[n + 1] = n + 1;
    for(int i = 1; i <= k; i++) frm[i] = -1, lst[i] = n + 1;
    for(int i = 1, pr = 0, x; i <= m2; i++) {
        x = rd();
        frm[x] = pr;
        pr = x;
    }
    for(int i = n; i; i--) {
        if(frm[c[i]] == -1) continue;
        if(frm[c[i]] == 0) suf[i] = i;
        else suf[i] = suf[lst[frm[c[i]]]];
        lst[c[i]] = i;
    }
    for(int i = 1; i <= n; i++) if(!lf[c[i]]) lf[c[i]] = i;
    for(int i = n; i; i--) if(!rh[c[i]]) rh[c[i]] = i;
    for(int i = 1; i <= k; i++) mx[lf[i]] = max(mx[lf[i]], rh[i]);
    for(int i = 1; i <= n; i++) mx[i] = max(mx[i], mx[i - 1]);
    for(int i = 1; i <= n; i++) {
        if(c[i] == s) {
            int l = pre[i], r = suf[i];
            if(l && r <= n && mx[l - 1] > r) ans.push_back(i);
        }
    }
    cout << ans.size(), el;
    for(int i : ans) cout << i << ' ';
    el;
}

:::