题解 P3570 [POI2014]PRZ-Criminals

· · 题解

题意

额外提供一个LOJ的翻译

题目分析

我们考虑枚举每一个可能的相遇位置 i（即满足 c[i]=x[m]=y[l] )，我们希望两个人所访问的第一个方格尽可能地靠近 i，分别记为 x,y，然后我们检查 \left[1,x-1 \right] 和 \left[y+1,n \right] 两个区间有没有相同的颜色即可。

因此题解分为以下两个部分：

Part 1:

$R[i]:$ 相遇点为 $i$ 时，第二个人下标最小的出发点。 实际上将颜色数组 $c$ 倒叙后求 $R[i]$ 的过程与求 $L[i]$ 的基本一样，所以这里只讨论 $L[i]$ 的求法。 我们可以维护若干个序列，表示从不同的起始点 $i$（即满足 $c[i]=a[1]$）出发经过的最长的下标序列，使得这些下标上对应的颜色能匹配 $a$ 数组的前若干位。而我们想要知道的就是长度为 $m$ 的上述序列中第一个下标最大是多少。 例如对于以下情况： ```cpp c:4 7 4 3 4 7 1 3 1 a:4 7 3 1 m=4 ``` 截止到第7个位置时，几个序列如下： ```cpp 1 2 4 7 3 6 5 6 ``` 所以 $L[7]=1$。 直接维护效率过低，我们考虑优化。 $Hint 1:

如果有两个序列长度一样，那我们可以直接舍弃掉前一个序列，因为它的第一位下标比后一个小，且它们两在往后匹配的过程中遇到的情况始终是一样的。（上面例子的第2,3两个序列就是如此）

Hint 2:

我们只需要知道每个序列第一个下标是多少，以及目前需要匹配 a 数组中的第几位即可。

有了这两个想法，我们可以记 pos[i] 表示需要匹配第 i 个位置的序列编号。假设当前的 c[i]=a[x] ，那么第 pos[x] 个序列已经可以匹配第 x 个位置，所以我们可以令 pos[x+1]=pos[x]。

可是如果在这之前有序列要匹配第 x+1 个位置被覆盖了怎么办？没关系，因为根据第一个想法就算有，它也可以被舍弃了，此外这个优化还保证了每一个序列想要匹配的位置一定不一样。

附上代码：

for(int i=1;i<=m;i++)num[a[i]]=i;
pos[1]=1;//造一个空序列需要匹配第一位
int tot=1;
for(int i=1;i<=n;i++){
    if(pos[num[c[i]]]){//存在一个序列需要匹配这一位
        int x=num[c[i]];
        if(x==1)H[pos[1]]=i;//记下出发点
        pos[x+1]=pos[x];pos[x]=0;
        if(x==1)pos[1]=++tot;//跟前面同理
    }
    L[i]=(pos[m+1]!=0&&c[i]==a[m])?H[pos[m+1]]:0;//如果有序列已经匹配完m位，L[i]即为那个序列的出发点。
}
//以下是求R[i]
memset(num,0,sizeof(num));memset(pos,0,sizeof(pos));memset(H,0,sizeof(H));
for(int i=1;i<=l;i++)num[b[i]]=i;
pos[1]=1;tot=1;
for(int i=n;i>=1;i--){
    if(pos[num[c[i]]]){
        int x=num[c[i]];
        if(x==1)H[pos[1]]=i;
        pos[x+1]=pos[x];pos[x]=0;
        if(x==1)pos[1]=++tot;
    }
    R[i]=(pos[l+1]!=0&&c[i]==b[l])?H[pos[l+1]]:n+1;
}

时间复杂度: O(n)

Part 2:

对于每一种颜色 x，我们可以求出它出现的最靠后的位置在哪儿，记为 pos[x] (为了省空间用了同一个数组)。

然后对于位置 i，我们可以预处理一个前缀最大值 pre[i]=\max \limits_{1\leq j \leq i}pos[c[j]]。于是 pre[i] 就可以表示区间 \left [1,i\right]中的颜色出现的最靠后的位置，如果 pre[i] \geq r，那么我们就可以认为区间 \left [1,i\right] 和区间 \left [r,n\right] 中有一样的颜色。

附上代码：

for(int i=1;i<=n;i++)pos[c[i]]=i;
for(int i=1;i<=n;i++)pre[i]=max(pre[i-1],pos[c[i]]);
for(int i=1;i<=n;i++){
    if(c[i]!=a[m])continue;
    if(pre[L[i]-1]>R[i])ans.push_back(i);
}

时间复杂度：O(n)