线段树

每次枚举右端点，用线段树的区间加来表示合法区间的覆盖，最后找到最大值为c的最小位置就是左端点

这里为了方便，把每个数第一次出现的位置都当成0，最后一次当成n+1。

一开始需要把0～第一次出现的位置-1的区间覆盖掉，当我们枚举到i的时候，由于i这个位置的数必须选，所以他出现的次数只能是大于等于k，原来表示的不出现的区间需要减去。

然后因为出现的次数增加了，所以对应的出现k次的区间也增加了，需要再更新一次线段树。

每次枚举都统计答案，取最大值。

#include 
    
     #define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)#define __fastIn ios::sync_with_stdio(false), cin.tie(0)#define pb push_backusing namespace std;typedef long long LL;inline int lowbit(int x){ return x & (-x); }inline int read(){    int ret = 0, w = 0; char ch = 0;    while(!isdigit(ch)){        w |= ch == '-', ch = getchar();    }    while(isdigit(ch)){        ret = (ret << 3) + (ret << 1) + (ch ^ 48);        ch = getchar();    }    return w ? -ret : ret;}inline int lcm(int a, int b){ return a / __gcd(a, b) * b; }template 
     
      inline A fpow(A x, B p, C lyd){    A ans = 1;    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;    return ans;}const int N = 200005;int n, c , k, a[N], tree[N<<2], lazy[N<<2], freq[N];vector
      
        vi[N];void push_up(int rt){    tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);}void f(int rt, int val){    tree[rt] += val, lazy[rt] += val;}void push_down(int rt, int l, int r){    int mid = (l + r) >> 1;    f(rt << 1, lazy[rt]), f(rt << 1 | 1, lazy[rt]);    lazy[rt] = 0;}void buildTree(int rt, int l, int r){    if(l == r){        tree[rt] = 0;        return;    }    int mid = (l + r) >> 1;    buildTree(rt << 1, l, mid);    buildTree(rt << 1 | 1, mid + 1, r);    push_up(rt);}void add(int rt, int l, int r, int al, int ar, int val){    if(al > ar) return;    if(l == al && r == ar){        f(rt, val);        return;    }    push_down(rt, l, r);    int mid = (l + r) >> 1;    if(ar <= mid) add(rt << 1, l, mid, al, ar, val);    else if(al > mid) add(rt << 1 | 1, mid + 1, r, al, ar, val);    else add(rt << 1, l, mid, al, mid, val), add(rt << 1 | 1, mid + 1, r, mid + 1, ar, val);    push_up(rt);}int query(int rt, int l, int r){    if(l == r) return l;    push_down(rt, l, r);    int mid = (l + r) >> 1;    if(tree[rt << 1] == c) return query(rt << 1, l, mid);    else if(tree[rt << 1 | 1] == c) return query(rt << 1 | 1, mid + 1, r);    return -1;}int main(){    __fastIn;    while(cin >> n >> c >> k){        full(freq, 0), full(lazy, 0), full(tree, 0);        for(int i = 1; i <= c; i ++){            vi[i].clear();            vi[i].pb(0);        }        for(int i = 1; i <= n; i ++){            cin >> a[i];            vi[a[i]].pb(i);        }        for(int i = 1; i <= c; i ++){            vi[i].pb(n + 1);        }        buildTree(1, 1, n);        for(int i = 1; i <= c; i ++){            add(1, 1, n, 1, vi[i][1] - 1, 1);        }        int ans = 0;        for(int i = 1; i <= n; i ++){            add(1, 1, n, vi[a[i]][freq[a[i]]] + 1, vi[a[i]][freq[a[i]] + 1] - 1, -1);            freq[a[i]] ++;            add(1, 1, n, vi[a[i]][freq[a[i]]] + 1, vi[a[i]][freq[a[i]] + 1] - 1, 1);            if(freq[a[i]] >= k) add(1, 1, n, vi[a[i]][freq[a[i]] - k] + 1, vi[a[i]][freq[a[i]] - k + 1], 1);            int tmp = query(1, 1, n);            if(tmp !=  -1) ans = max(ans, i - tmp + 1);        }        printf("%d\n", ans);    }    return 0;}