题解：CF1120A Diana and Liana

Left_i_Forever · 2025-08-23 20:41:59 · 题解

首先删除数量是有限制的，留下来的至少有 nk 个，不然不够做。

考虑选择一个已经满足条件的区间，我们只需要将其中多余的删除并删除部分区间前的部分使得前面可以刚好分成若干个长为 k 的段落。

由于留下的长度只有 k，所以取的区间越长越不好，我们只需要统计每个位置开始的最短的区间，双指针即可。

#include <bits/stdc++.h>
//#define int long long
#define x first
#define y second
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-10, PI = acos (-1);
const int N = 5e5 + 10, M = 2e5 + 10;
//const int mod = 1e9 + 7;
//const int mod = 998244353;

int cntb, cnt, ans = 1e9, a[N], b[N], cb[N], c[N];
vector <int> v[N];

signed main()
{
    int m, k, n, s;
    cin >> m >> k >> n >> s;
    for (int i = 1; i <= m; i++)
        cin >> a[i], v[a[i]].push_back (i);
    for (int i = 1; i <= s; i++)
        cin >> b[i], cntb += !cb[b[i]]++;
    for (int i = 1, j = 0; i <= m; i++)
    {
        while(j < m && cnt < cntb) ++j, cnt += ++c[a[j]] == cb[a[j]];
        if(cnt == cntb)
        {
            int tot = (i - 1) % k + max(0, j - i + 1 - k);
            // printf("%d,%d:%d\n", i,j ,tot);
            if(m - tot >= n * k) ans = min(ans, tot);
        }
        cnt -= c[a[i]]-- == cb[a[i]];
    }
    if(ans == 1e9) return puts("-1"), 0;
    printf("%d\n", ans);
    vector<int> path;
    memset(c, 0, sizeof c), cnt = 0;
    for (int i = 1, j = 0; i <= m; i++)
    {
        while(j < m && cnt < cntb) ++j, cnt += ++c[a[j]] == cb[a[j]];
        if(cnt == cntb)
        {
            int tot = (i - 1) % k + max(0, j - i + 1 - k);
            if(tot == ans)
            {
                for(int p = (i - 1) / k * k + 1; p < i; p++) path.push_back(p);
                memset(c, 0, sizeof c);
                vector<int> tmp;
                for(int p = i; p <= j; p++) if(++c[a[p]] > cb[a[p]]) tmp.push_back(p);
                for(int p = 0; p < j - i + 1 - k; p++) path.push_back(tmp[p]);
                for(int p : path) printf("%d ", p);
                return 0;
            }
        }
        cnt -= c[a[i]]-- == cb[a[i]];
    }
    return 0;
}