题目链接：HDU 6602

你有一个长度为 $n$ 的序列 $a$ 和两个整数 $C, K$ 满足序列中的所有元素 $1 \le a_{i} \le C$。

我们定义一个连续子序列 $a_{l}, a_{l + 1}, \dots, a_{r}$ 是「好的」当且仅当：

$$ \forall x \in [1, C], \sum_{i = l} ^ {r} [a_{i} = x] = 0\ \text{或}\ \sum_{i = l} ^ {r} [a_{i} = x] \ge K $$

抽象地，如果一个数字在子序列中出现过，那么它的出现次数必须不少于 $K$ 次。

他需要求出「好的」连续子序列的最长长度。

本题有多组数据。

数据范围：$1 \le n, C, K \le 10 ^ 5$，$1 \le a_{i} \le C$，$1 \le \sum n, \sum C, \sum K \le 5 \times 10 ^ 5$。

Solution

发现对于每个位置 $i$，以 $i$ 为右端点时，左端点一定在一个区间内。具体地，左端点的可行区间为 $[1, \text{从}\ i\ \text{往前第}\ K\ \text{个值为}\ a_i\ \text{的位置}]$。

有一种比较简单的做法为，在不合法的区间打标记（区间 $+1$），线段树维护区间 最小值 和 最靠左的最小值位置。如果最小值为 $0$ 则最靠左的位置即为左端点的最优解。

注意每次区间修改时需要消除上一次的影响。

时间复杂度：$\mathcal O(\sum n \log n)$。

Code

#include <cstdio>
#include <algorithm>
#include <vector>

const int N = 1e5 + 5;
const int INF = 0x7f7f7f7f;

int n, c, k, a[N];
std::vector<int> vec[N];

template <int MAX>
struct SegmentTree {
    #define lson p << 1
    #define rson p << 1 | 1

    static const int N = MAX << 2;

    int tag[N];
    std::pair<int, int> mn[N];

    void pushUp(int p) {
        mn[p] = std::min(mn[lson], mn[rson]);
    }
    void update(int p, int v) {
        mn[p].first += v, tag[p] += v;
    }
    void pushDown(int p) {
        if (tag[p]) {
            update(lson, tag[p]);
            update(rson, tag[p]);
            tag[p] = 0;
        }
    }
    void build(int p, int l, int r) {
        mn[p].first = tag[p] = 0, mn[p].second = l;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(lson, l, mid);
        build(rson, mid + 1, r);
        pushUp(p);
    }
    void modify(int p, int l, int r, int x, int y, int v) {
        if (x == l && r == y) {
            update(p, v);
            return;
        }
        pushDown(p);
        int mid = (l + r) >> 1;
        if (y <= mid) {
            modify(lson, l, mid, x, y, v);
        } else if (x > mid) {
            modify(rson, mid + 1, r, x, y, v);
        } else {
            modify(lson, l, mid, x, mid, v);
            modify(rson, mid + 1, r, mid + 1, y, v);
        }
        pushUp(p);
    }
    std::pair<int, int> query(int p, int l, int r, int x, int y) {
        if (x == l && r == y) return mn[p];
        pushDown(p);
        int mid = (l + r) >> 1;
        if (y <= mid) {
            return query(lson, l, mid, x, y);
        } else if (x > mid) {
            return query(rson, mid + 1, r, x, y);
        } else {
            return std::min(query(lson, l, mid, x, mid), query(rson, mid + 1, r, mid + 1, y));
        }
    }

    #undef lson
    #undef rson
};

SegmentTree<N> seg;

int main() {
    for (; scanf("%d%d%d", &n, &c, &k) == 3; ) {
        if (k <= 1) {
            for (int i = 1; i <= n; i++) scanf("%*d");
            printf("%d\n", n);
            continue;
        }
        seg.build(1, 1, n);
        for (int i = 1; i <= c; i++) vec[i].clear();
        int ans = 0;
        for (int i = 1, x; i <= n; i++) {
            scanf("%d", &x);
            int s = vec[x].size();
            if (s > 0) {
                seg.modify(1, 1, n, s >= k ? vec[x][s - k] + 1 : 1, vec[x][s - 1], -1);
            }
            seg.modify(1, 1, n, s >= k - 1 ? vec[x][s - k + 1] + 1 : 1, i, 1);
            auto now = seg.query(1, 1, n, 1, i);
            if (now.first == 0) ans = std::max(ans, i - now.second + 1);
            vec[x].emplace_back(i);
        }
        printf("%d\n", ans);
    }
    return 0;
}