线段树神题。

题目描述

        You are given two integers $C,K$ and an array of $N$ integers $a_1,a_2,…,a_N$. It is guaranteed that the value of $a_i$ is between 1 to $C$.
        We define that a continuous subsequence $a_l,a_{l+1},…,a_r(l≤r)$ of array a is a good subarray if and only if the following condition is met:

        It implies that if a number appears in the subarray, it will appear no less than $K$ times.
        You should find the longest good subarray and output its length. Or you should print 0 if you cannot find any.

输入输出格式

输入格式

        There are multiple test cases.
        Each case starts with a line containing three positive integers $N,C,K(N,C,K≤10^5)$.
        The second line contains $N$ integer $a_1,a_2,…,a_N(1≤a_i≤C)$.
        We guarantee that the sum of $N$s, the sum of $C$s and the sum of $K$s in all test cases are all no larger than $5×10^5$.

输出格式

        For each test case, output one line containing an integer denoting the length of the longest good subarray.

输入输出样例

Sample input

7 4 2
2 1 4 1 4 3 2

Sample output

4

题解

        很巧妙的线段树题目。
        固定右端点，考虑每一种数能够确定的左端点范围。很明显，每一种数的左端点都有两个连续的区间（不选的情况以及选了k个或更多的情况），我们给这些区间加上1。这样只需要找到第一个值为$C$（表示所有种类的数均满足）的下标就可以了。
        找第一个值为$C$的数显然不能暴力，这样复杂度还是$O(n^2)$。这里注意到$C$一定是其中的最大值，于是用线段树维护区间最值，根据区间最值二分出第一个为$C$（就是最大值）的点。这里利用$C$是最大值的性质将找点操作优化到$O(logn)$。
        对于其它右端点，将右端点顺次右移，途中维护线段树即可。总时间复杂度$O(nlogn)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>

using namespace std;
int n, c, k, tree[100005 << 2], la[100005 << 2];

void build(int l = 1, int r = n, int k = 1) {
    la[k] = tree[k] = 0;
    if (l == r)la[k] = tree[k] = 0;
    else build(l, (l + r) >> 1, k << 1), build(((l + r) >> 1) + 1, r, k << 1 | 1);
}

inline void down(int x) {
    tree[x << 1] += la[x], tree[x << 1 | 1] += la[x];
    la[x << 1] += la[x], la[x << 1 | 1] += la[x], la[x] = 0;
}

void update(int l, int r, int ss, int L = 1, int R = n, int k = 1) {
    if (L >= l && R <= r) {
        la[k] += ss, tree[k] += ss;
        return;
    }
    if (la[k])down(k);
    int mid = (L + R) >> 1;
    if (l > mid)update(l, r, ss, mid + 1, R, k << 1 | 1);
    else if (r <= mid)update(l, r, ss, L, mid, k << 1);
    else update(l, mid, ss, L, mid, k << 1), update(mid + 1, r, ss, mid + 1, R, k << 1 | 1);
    tree[k] = max(tree[k << 1], tree[k << 1 | 1]);
}

int qu(int l, int r, int L = 1, int R = n, int k = 1) {
    if (tree[k] != c)return -1;
    if (L == R)return L;
    if (la[k])down(k);
    int mid = (L + R) >> 1, ss;
    if (l > mid)return qu(l, r, mid + 1, R, k << 1 | 1);
    else if (r <= mid)return qu(l, r, L, mid, k << 1);
    return ((ss = qu(l, mid, L, mid, k << 1)) == -1) ? qu(mid + 1, r, mid + 1, R, k << 1 | 1) : ss;
}

vector<int> vvp[100005];
int l[100005];

int main() {
    while (scanf("%d%d%d", &n, &c, &k) == 3) {
        build();
        int ans = 0, tmp, x;
        for (int i = 1; i <= c; i++)vvp[i].clear();
        for (int i = 1; i <= n; i++) {
            scanf("%d", &x), vvp[x].push_back(i);
            update(i, i, c);//这一格都可以不选
            update(vvp[x].size() > 1 ? vvp[x][vvp[x].size() - 2] + 1 : 1, i, -1);
            //但是，它自己必须得选上
            if (vvp[x].size() == k)l[x] = 0, update(1, vvp[x][0], 1);//已经到k个，更新区间
            else if (vvp[x].size() > k)++l[x], update(vvp[x][l[x] - 1] + 1, vvp[x][l[x]], 1);//多于k个，右移区间
            tmp = qu(1, i);
            if (tmp != -1)ans = max(ans, i - tmp + 1);
        }
        printf("%d\n", ans);
    }
    return 0;
}