## Description:

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$ .

$$\begin{equation*} \forall x \in [1, C], \; \sum\limits_{i = l}^r[a_i = x] = 0 \; or \; \sum\limits_{i = l}^r[a_i = x] \geq K \end{equation*}$$

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.

## Input:

There are multiple test cases.

Each case starts with $a$ line containing three positive integers $N,C,K(N,C,K \leq 10^5)$ .

The second line contains $N$ integer $a_1, a_2, ..., a_N(1 \leq a_i \leq 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 \times 10^5$ .

## Output:

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

7 4 2
2 1 4 1 4 3 2

## Sample Output:

4

### 题目链接

1. 区间 $[r,r]$ 的满足数量为 $C-1$ ，这个区间只有 $x$ 不满足条件
2. $r$ 左边第 $1$ 个 $x$ 的位置为 $pos$ ，区间 $[pos+1,r-1]$ 之间的满足数量在之前的基础上 $-1$ ，因为这些位置做左端点已经不能满足 $x$ 数字的条件，之前这些位置按照 $x$ 出现 $0$ 次进行计算，现在按照出现 $1$ 次计算
3. $r$ 左边第 $k$ 个 $x$ 的位置为 $pos$ ，$r$ 左边第 $k-1$ 个 $x$ 的位置为 $pos'$，将区间 $[pos+1,pos']$ 的满足数量在之前的基础上 $+1$ ，因为这些位置做左端点已经可以满足 $x$ 数字的条件

## AC代码:

#include <bits/stdc++.h>
const int maxn = 1e5 + 5;
struct SegTree {
int n;
int max[maxn * 4], lazy[maxn * 4], pos[maxn * 4];
void Pull(int o) {
max[o] = std::max(max[o * 2], max[o * 2 + 1]);
pos[o] = max[o * 2] >= max[o * 2 + 1] ? pos[o * 2] : pos[o * 2 + 1];
}
void Push(int o) {
if (lazy[o] != 0) {
max[o * 2] += lazy[o];
max[o * 2 + 1] += lazy[o];
lazy[o * 2] += lazy[o];
lazy[o * 2 + 1] += lazy[o];
lazy[o] = 0;
}
}
void Build(int o, int l, int r) {
max[o] = lazy[o] = 0; pos[o] = l;
if (l == r) return;
int m = (l + r) / 2;
Build(o * 2, l, m);
Build(o * 2 + 1, m + 1, r);
Pull(o);
}
void Init(int _n) {
n = _n;
Build(1, 1, n);
}
void Modify(int o, int l, int r, int ll, int rr, int v) {
if (ll <= l && rr >= r) {
max[o] += v;
lazy[o] += v;
return;
}
Push(o);
int m = (l + r) / 2;
if (ll <= m) Modify(o * 2, l, m, ll, rr, v);
if (rr > m) Modify(o * 2 + 1, m + 1, r, ll, rr, v);
Pull(o);
}
void Modify(int ll, int rr, int v) {
Modify(1, 1, n, ll, rr, v);
}
int Query(int o, int l, int r, int ll, int rr, int v) {
if (ll <= l && rr >= r) {
if (max[o] == v) return pos[o];
else return rr + 1;
}
Push(o);
int m = (l + r) / 2;
if (max[o * 2] == v) return pos[o * 2];
else if (max[o * 2 + 1] == v) return pos[o * 2 + 1];
else return rr + 1;
Push(o);
}
int Query(int ll, int rr, int v) {
return Query(1, 1, n, ll, rr, v);
}
};
SegTree T;
std::vector<int> pos[maxn];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, c, k;
while (std::cin >> n >> c >> k) {
for (int i = 1; i <= c; ++i) {
pos[i].clear();
pos[i].push_back(0);
}
T.Init(n);
int ans = 0;
for (int r = 1, x; r <= n; ++r) {
std::cin >> x;
T.Modify(r, r, c - 1);
if (pos[x].back() + 1 <= r - 1) T.Modify(pos[x].back() + 1, r - 1, -1);
pos[x].push_back(r);
if (pos[x].size() > k) {
int idx = pos[x].size() - k - 1;
T.Modify(pos[x][idx] + 1, pos[x][idx + 1], 1);
}
ans = std::max(ans, r - T.Query(1, r, c) + 1);
}
std::cout << ans << '\n';
}
return 0;
}
Last modification：August 26th, 2019 at 05:29 pm