一道看起来蛮套路的题。首先如果确定了两端的起点的话这题就非常好做了。
贪心地来想，每次走到第一个该走的颜色。举个栗子，假设数据是这样的：
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;
}