题目链接：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 }
