题目链接

传送门

题意

要你找一个最长的区间使得区间内每一个数出现次数都大于等于(K)。

思路

我们通过固定右端点考虑每个左端点的情况。

首先对于每个位置，我们用线段树来维护它作为(C)种元素的左端点的可行性。

对于每个元素我们用(vector)存下它出现的所有下标。

枚举右端点(i)，对于([i,i])这区间除去(a_i)这个数外其他元素都没有出现过，那么它作为左端点的可行性为(C-1)；对于(a_i)上一次出现的位置(pos)，则([pos+1,i-1])这一段区间做左端点，由于(a_i)在(i)出现过了，那么([pos+1,i-1])在线段树内的结点均存了(a_i)没有出现的情况，因此需要减去。假设从(y)是(a_i)从(i)往左数恰好出现(K)次的位置，(x)是恰好出现(K+1)次的位置，那么([x+1,y])在线段树内的结点没有存(a_i)出现(K)次的情况，因此需要加上。

查询：对于(i)，我们考虑从(i)往左延伸到第一个不满足作为左端点可行性为(C)的位置加一的(x)，那么此时可以选择的区间长度为(i-x+1)，然后对于所有情况取(max)即可。

代码实现如下

#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> pLL;
typedef pair<LL,int> pLi;
typedef pair<int,LL> pil;;
typedef pair<int,int> pii;
typedef unsigned long long uLL;

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("/home/dillonh/CLionProjects/Dillonh/in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0)

const double eps = 1e-8;
const int mod = 1000000007;
const int maxn = 100000 + 7;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;

int N,C,K,x;
vector<int> vec[maxn];

struct node {
    int l,r,mx,lazy,ans;
}segtree[maxn<<2];

void push_up(int rt) {
    segtree[rt].mx = max(segtree[lson].mx,segtree[rson].mx);
    //预存从i这个位置一直可以延伸的位置
    if(segtree[rt].mx == segtree[lson].mx) segtree[rt].ans = segtree[lson].ans;
    else segtree[rt].ans = segtree[rson].ans;
}

void push_down(int rt) {
    int x = segtree[rt].lazy;
    segtree[rt].lazy = 0;
    segtree[lson].lazy += x;
    segtree[rson].lazy += x;
    segtree[lson].mx += x;
    segtree[rson].mx += x;
}

void build(int rt,int l,int r) {
    segtree[rt].l = segtree[rt].ans = l,segtree[rt].r = r;
    segtree[rt].mx = segtree[rt].lazy = 0;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(lson,l,mid);
    build(rson,mid + 1,r);
}

void update(int rt,int  l,int r,int val) {
    if(segtree[rt].l == l && segtree[rt].r == r) {
        segtree[rt].mx += val;
        segtree[rt].lazy += val;
        return;
    }
    push_down(rt);
    int mid = (segtree[rt].l + segtree[rt].r) >> 1;
    if(r <= mid) update(lson,val);
    else if(l > mid) update(rson,val);
    else {
        update(lson,mid,val);
        update(rson,val);
    }
    push_up(rt);
}

int query(int rt,int r) {
    if(segtree[rt].mx != C) return -1;
    if(segtree[rt].l >= l && segtree[rt].r <= r) return segtree[rt].ans;
    push_down(rt);
    int mid = (segtree[rt].l + segtree[rt].r) >> 1;
    if(r <= mid) return query(lson,r);
    else if(l > mid) return query(rson,r);
    else {
        int tmp = query(lson,mid);
        if(tmp != -1) return tmp;
        return query(rson,r);
    }
}

int main() {
    while(~scanf("%d%d%d",&N,&C,&K)) {
        for(int i = 1; i <= C; ++i) vec[i].clear(),vec[i].push_back(0);
        build(1,1,N);
        int ans = 0;
        for(int i = 1; i <= N; ++i) {
            scanf("%d",&x);
            update(1,i,C - 1);  //单独只考虑[i,i]这个区间，此时其他i-1个元素均没有出现，因此i的作为左端点可行性为C-1
            if(vec[x].back() < i - 1) update(1,vec[x].back() + 1,i - 1,-1); //将前面考虑过ai没有出现的情况减去
            vec[x].push_back(i);
            if(vec[x].size() >= K + 1) {
                int pos = vec[x].size() - K - 1;
                update(1,vec[x][pos] + 1,vec[x][pos+1],1);  //把前面没有考虑ai出现k次的情况加上
            }
            int tmp = query(1,i);
            if(tmp == -1) continue;
            ans = max(ans,i - tmp + 1);
        }
        printf("%dn",ans);
    }
    return 0;
}