题解：P3570 [POI 2014] PRZ-Criminals

AeeE5x · 2026-05-07 15:44:43 · 题解

前言

怎么翻译题面不带数据范围的。

这个有紫吗？

Solution

考虑枚举两个人初始的位置，显然应该是某个颜色第一次出现和最后一次出现的位置最优。

现在考虑左侧的人从 i 出发，最终会走到的位置 L_i。

因为保证走过的所有关键颜色不同，所以我们对每个位置而言，找到在关键颜色序列上的下一个关键颜色，建一个指针指向下一个关键颜色在当前位置之后第一次出现的位置。

现在 L_i 就是 i 右侧第一个 x_1 颜色位置的指针的终点，这个过程可以路径压缩维护。

右侧的人同理，最后走到的区间就是可能的答案集合。

复杂度 O(n)。

Code

:::success[代码]

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;

int n,m;
int a[1000010];
int color_begin[1000010],color_end[1000010];

int k1,k2;
int p1[1000010],p2[1000010];

int bkt[1000010];

int nxt_color[1000010];
int nxt[1000010],prv[1000010];

int L[1000010],R[1000010];
static inline int findnxt(int x){while(x!=nxt[x]) x=nxt[x]=nxt[nxt[x]];return x;}
static inline int findprv(int x){while(x!=prv[x]) x=prv[x]=prv[prv[x]];return x;}

int val[1000010];

int main(){
    cin.tie(0)->sync_with_stdio(false);

    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++) color_end[a[i]]=i;
    for(int i=n;i>=1;i--) color_begin[a[i]]=i;

    cin>>k1>>k2;
    for(int i=1;i<=k1;i++) cin>>p1[i];
    for(int i=1;i<=k2;i++) cin>>p2[i];

    for(int i=0;i<=m;i++) nxt_color[i]=0,bkt[i]=n+1;
    for(int i=1;i<=k1;i++) nxt_color[p1[i]]=p1[i+(i!=k1)];

    nxt[n+1]=n+1;
    for(int i=n;i>=1;i--){
        bkt[a[i]]=i,nxt[i]=bkt[nxt_color[a[i]]];
        L[i]=findnxt(bkt[p1[1]]);
    }

    for(int i=0;i<=m;i++) nxt_color[i]=0,bkt[i]=0;
    for(int i=1;i<=k2;i++) nxt_color[p2[i]]=p2[i+(i!=k2)];

    prv[0]=0;
    for(int i=1;i<=n;i++){
        bkt[a[i]]=i,prv[i]=bkt[nxt_color[a[i]]];
        R[i]=findprv(bkt[p2[1]]);
    }

    for(int i=1;i<=m;i++) if(color_begin[i]){
        int l=color_begin[i],r=color_end[i];
        if(l+1<=r-1&&L[l+1]<=R[r-1]) val[L[l+1]]++,val[R[r-1]+1]--;
    }

    vector<int> ans;
    for(int i=1,nowv=0;i<=n;i++){
        nowv+=val[i];
        if(nowv&&a[i]==p1[k1]) ans.push_back(i);
    }

    cout<<ans.size()<<"\n";
    for(int x:ans) cout<<x<<" ";
    cout<<"\n";

    # ifdef TakanashiHoshino
    cerr<<"\n\033[1;38;2;234;200;225mUsed time: "<<clock()*1.0/CLOCKS_PER_SEC<<"s.\033[0m\n";
    # endif
    return 0;
}

:::