题解：P3570 [POI 2014] PRZ-Criminals

Iruka_Okazaki · 2026-10-22 19:20:35 · 题解

心梗题。

对于每一个 c_i = x_m，我们考虑维护 L_i,R_i 分别表示以这个点为最终点时，第一个抢劫的房子的位置离 i 最近是哪一个点。由于 x,y 互不相同，所以我们可以 \mathrm O(n) 快速维护 L_i,R_i。

for(int i = 1;i <= n;i++)pre[i] = 0,nxt[i] = n + 1;
for(int i = 1;i <= n;i++)
{
    if(!posx[a[i]])continue;
    if(posx[a[i]] == 1)pre[a[i]] = i;
    else pre[a[i]] = pre[x[posx[a[i]] - 1]];
    L[i] = pre[a[i]];
}
for(int i = n;i >= 1;i--)
{
    if(!posy[a[i]])continue;
    if(posy[a[i]] == 1)nxt[a[i]] = i;
    else nxt[a[i]] = nxt[y[posy[a[i]] - 1]];
    R[i] = nxt[a[i]];
}

然后对于每一个 i 要求就是有一个颜色在 L_i 前和 R_i 后同时出现过。所以我们考虑对于每一个颜色需要维护他第一次出现的位置和最后一次出现的位置，然后对于 i 号房子，其能作为重点当且仅当 \exist j \in [1,k],[{L_i,R_i}] \subset [\text{fir}_j,\text{lst}_j]，其中 \text{fir}_j 和 \text{lst}_j 是颜色 j 第一次出现和最后一次出现的位置。

然后你会想直接做二位数点，但是你发现一个问题就是空间不支持你这么做。然后你又发现，实际上只需要维护所有 \text{fir}_j < l 的最大 \text{lst}_j 即可判断。那不就直接维护前缀 max 了吗，然后就做到了 \mathrm O(n) 了。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
int n,k,m,l,a[maxn],L[maxn],R[maxn];
int pre[maxn],nxt[maxn],fir[maxn],lst[maxn];
int x[maxn],y[maxn],posx[maxn],posy[maxn];
int mx[maxn];vector<int> ans;
signed main()
{
    cin >> n >> k;
    for(int i = 1;i <= n;i++)cin >> a[i];
    cin >> m >> l;
    for(int i = 1;i <= m;i++)cin >> x[i],posx[x[i]] = i;
    for(int i = 1;i <= l;i++)cin >> y[i],posy[y[i]] = i;

    for(int i = 1;i <= n;i++)pre[i] = 0,nxt[i] = n + 1;
    for(int i = 1;i <= n;i++)
    {
        if(!posx[a[i]])continue;
        if(posx[a[i]] == 1)pre[a[i]] = i;
        else pre[a[i]] = pre[x[posx[a[i]] - 1]];
        L[i] = pre[a[i]];
    }
    for(int i = n;i >= 1;i--)
    {
        if(!posy[a[i]])continue;
        if(posy[a[i]] == 1)nxt[a[i]] = i;
        else nxt[a[i]] = nxt[y[posy[a[i]] - 1]];
        R[i] = nxt[a[i]];
    }
    for(int i = 1;i <= n;i++)lst[a[i]] = i;
    for(int i = n;i >= 1;i--)fir[a[i]] = i;

    for(int i = 1;i <= k;i++)if(lst[i] && fir[i])mx[fir[i]] = max(mx[fir[i]],lst[i]);
    for(int i = 1;i <= n;i++)mx[i] = max(mx[i - 1],mx[i]);
    for(int i = 1;i <= n;i++)
    {
        if(a[i] != x[m])continue;
        if(L[i] && R[i] != n + 1 && mx[L[i] - 1] > R[i])ans.push_back(i);
    }
    cout << ans.size() << '\n';
    for(auto i : ans)cout << i << " ";
    return 0;
}