POI2014 PRZ-Criminals

· · 题解

一道看起来蛮套路的题。首先如果确定了两端的起点的话这题就非常好做了。

贪心地来想，每次走到第一个该走的颜色。举个栗子，假设数据是这样的：

10 5
1 2 3 2 4 3 5 2 2 1
3 2
2 3 4
2 4

那么如果第一个人的位置是 1，下一个他会到位置 2 的 2，然后再到位置 3 的 3，再到位置 5 的 4。可以证明这样一定是最优的，选越前面的后面更有机会被选到。同理从后往前的那个人也是如此。于是这个问题可以 O(n) 解决。

但是这道题起点不固定，那么我们只好枚举起点，注意到起点的颜色必须相同，那我们枚举颜色就好了。同上面的贪心，两个点应越靠近两边越好。可是这样子时间复杂度变为 O(nk)，不能通过此题。我们考虑把上述后一个的关系建成一张图。对于每个节点，统计其下一个第一个 x_1 的位置，对于每个 x_1 的位置，统计其下一个 x_2 的位置，对于每个 x_i 的位置，统计其后的最近的 x_{i+1} 的位置。

这可以通过从后往前统计每种颜色最前的位置来实现。

统计好了之后暴力跳的复杂度还是 O(nk)，但是我们可以路径压缩，类似并查集的复杂度证明可以知道这样是均摊 O(k\log{n}) 的。

因为这题卡空间所以我把一个数组用在了很多地方来节省空间。。。

#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &X) {
    T f = 1;
    char ch = getchar();
    for (; '0' > ch || ch > '9'; ch = getchar()) if (ch == '-') f = -1;
    for (X = 0; '0' <= ch && ch <= '9'; ch = getchar()) X = X * 10 + ch - '0';
    X *= f;
}
int n, k;
int c[1000001];
int m, l;
int x[1000001], y[1000001];
int ans, tmp;
int nxt1[1000001], nxt2[1000001];
int fa1[1000001], fa2[1000001];
int tail[1000001]; 
int Find1(int X) {
    if (fa1[X] == -1) return -1; 
    return fa1[X] == n + 1 ? X : fa1[X] = Find1(fa1[X]);
}
int Find2(int X) {
    if (fa2[X] == -1) return -1;
    return fa2[X] == 0 ? X : fa2[X] = Find2(fa2[X]);
}
void work1() {
    int lst = n + 1;
    for (int i = n; i >= 1; i--) {
        nxt1[i] = lst;
        if (c[i] == x[1]) {
            lst = i;
        }

    }
}
void work2() {
    int lst = 0;
    for (int i = 1; i <= n; i++) {
        nxt2[i] = lst;
        if (c[i] == y[1]) {
            lst = i;
        }
    }
}
void work3() {
    for (int i = 1; i <= k; i++) tail[i] = -1;
    for (int i = n; i; i--) {
        if (nxt1[c[i]]) fa1[i] = tail[nxt1[c[i]]];
        if (c[i] == tmp) fa1[i] = n + 1;
        tail[c[i]] = i;
    }
}
void work4() {
    for (int i = 1; i <= k; i++) tail[i] = -1;
    for (int i = 1; i <= n; i++) {
        if (nxt2[c[i]]) fa2[i] = tail[nxt2[c[i]]];
        if (c[i] == tmp) fa2[i] = 0;
        tail[c[i]] = i;
    }
}
int main() {
    memset(fa1, -1, sizeof(fa1));
    memset(fa2, -1, sizeof(fa2));
    read(n); read(k);
    for (int i = 1; i <= n; i++) read(c[i]);
    read(m); read(l);
    for (int i = 1; i <= m; i++) read(x[i]);
    for (int i = 1; i < m; i++) nxt1[x[i]] = x[i + 1];
    tmp = x[m];
    for (int i = 1; i <= l; i++) read(y[i]);
    for (int i = 1; i < l; i++) nxt2[y[i]] = y[i + 1];
    work3();//把所有 x_i 后的最近的 x_{i+1} 找出来 
    work4();//把所有 y_i 前的最近的 y_{i+1} 找出来 
    work1();//把所有位置后的最近的 x_1 找出来 
    work2();//把所有位置前的最近的 y_1 找出来 
    for (int i = 1; i <= k; i++) x[i] = 0;
    for (int i = 1; i <= n; i++) if (!x[c[i]]) x[c[i]] = i;
    for (int i = 1; i <= k; i++) tail[i] = 0;
    for (int i = n; i >= 1; i--) if (!tail[c[i]]) tail[c[i]] = i;
    for (int i = 1; i <= n; i++) y[i] = 0;
    for (int i = 1; i <= k; i++) {//枚举开始颜色 
        if (!x[i]) continue;
        if (nxt1[x[i]] == n + 1 || nxt2[tail[i]] == 0) continue; 
        int fir = Find1(nxt1[x[i]]), sec = Find2(nxt2[tail[i]]);
        if (fir == -1 || sec == -1) continue;
        if (fir <= sec) {
            y[fir]++;
            y[sec + 1]--;
        }
    }
    for (int i = 1; i <= n; i++) {
        y[i] += y[i - 1];
        if (y[i] > 0) {
            if (c[i] == tmp) {
                ans++;
            }
        }
    }
    printf("%d\n", ans);
    for (int i = 1; i <= n; i++) if (y[i] > 0) if (c[i] == tmp) printf("%d ", i);
    return 0;
}