题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6602

题目大意为求最长的区间，满足C种数字在区间内要么不出现，要么出现的次数都不小于K。

大致的分析一下，可以知道对于以R为右端点的区间来说，每种颜色的合法区间在[1~出现k次]和(上一次出现~下一次出现)。PS:[]为闭区间,()为开区间。

所以可以线段树维护一下，枚举区间右端点，然后在线段树上将上一次更新这种颜色的操作撤销(上次是+1，则当前-1)，然后再次更新(+1)。

对于每个区间右端点，最大的有效区间为线段树上种类为C的最左边的位置。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<vector>
 7 #define lson l,mid,i<<1
 8 #define rson mid+1,r,i<<1|1
 9 using namespace std;
10 typedef long long ll;
11 const int maxn = 2e5 + 10;
12 const ll mod = 1000000007;
13 int Max[maxn * 4], lazy[maxn * 4];
14 vector<int>cnt[maxn];
15 int num[maxn];
16 int n, c, k;
17 void up(int i) {
18     Max[i] = max(Max[i << 1], Max[i << 1 | 1]);
19 }
20 void down(int i) {
21     if (lazy[i]) {
22         lazy[i << 1] += lazy[i];
23         lazy[i << 1 | 1] += lazy[i];
24         Max[i << 1 | 1] += lazy[i];
25         Max[i << 1] += lazy[i];
26         lazy[i] = 0;
27     }
28 }
29 void build(int l, int r, int i) {
30     Max[i] = lazy[i] = 0;
31     if (l == r)
32         return;
33     int mid = l + r >> 1;
34     build(lson);
35     build(rson);
36     up(i);
37 }
38 void  update(int L, int R, int k, int l, int r, int i) {
39     if (L > R)return;
40     if (L <= l && r <= R) {
41         Max[i] += k;
42         lazy[i] += k;
43         return;
44     }
45     down(i);
46     int mid = l + r >> 1;
47     if (L <= mid)update(L, R, k, lson);
48     if (R > mid)update(L, R, k, rson);
49     up(i);
50 }
51 int query(int l, int r, int i) {
52     if (l == r)return l;
53     int ans = -1, mid = l + r >> 1;
54     down(i);
55     if (Max[i << 1] == c)ans = query(lson);
56     else if (Max[i << 1 | 1] == c)ans = query(rson);
57     return ans;
58 }
59 int a[maxn];
60 int main() {
61     while (scanf("%d%d%d", &n, &c, &k) != EOF) {
62         for (int i = 1; i <= c; i++)
63             cnt[i].clear(), cnt[i].push_back(0), num[i] = 0;
64         for (int i = 1; i <= n; i++) {
65             scanf("%d", &a[i]);
66             cnt[a[i]].push_back(i);
67         }
68         build(1, n, 1);
69         for (int i = 1; i <= c; i++) {
70             cnt[i].push_back(n + 1);
71             update(cnt[i][0] + 1, cnt[i][1] - 1, 1, 1, n, 1);
72         }
73         int ans = 0;
74         for (int i = 1; i <= n; i++) {
75             update(cnt[a[i]][num[a[i]]] + 1, cnt[a[i]][num[a[i]] + 1] - 1, -1, 1, n, 1);
76             if (num[a[i]] >= k)
77                 update(1, cnt[a[i]][num[a[i]] - k + 1], -1, 1, n, 1);
78             num[a[i]]++;
79             update(cnt[a[i]][num[a[i]]] + 1, cnt[a[i]][num[a[i]] + 1] - 1, 1, 1, n, 1);
80             if (num[a[i]] >= k)
81                 update(1, cnt[a[i]][num[a[i]] - k + 1], 1, 1, n, 1);
82             int q = query(1, n, 1);
83             if (q != -1)
84                 ans = max(ans, i - q + 1);
85         }
86         printf("%d\n", ans);
87     }
88 }