枚举区间的右端点，求左端点，可以解决大多数求最大最小区间的问题。 假设当前枚举到i，当前数字为x，设 pos1 是数字x从位置 i 向左开始第一次出现的位置，pos2 是第 k 次出现的位置，pos3 是第 k - 1 次出现的位置（下面会用到），当i位置没有x之前，对于x来说，可以选择的左端点区间范围[pos1+1,i]和[1,pos2]; 当i位置有x后，对于x来说，可以选择的左端点区间范围只剩[1,pos3];原先的[pos1+1,i]对左端点的贡献集体减一，原先 [ 1 , pos2 ] 的这段区间扩大到了 [ 1 , pos3 ] 这么大，相当于 [ pos2 + 1 , pos3 ] 这段区间对左端点的贡献集体加一了。 区间加减可以用线段树维护，当一个节点的相对贡献大于等于 0 时，说明当前节点可以选做为左端点，每次处理完后，贪心去寻找相对贡献大于等于 0 的最左端的位置，然后更新答案即可。 参考博客：https://blog.csdn.net/qq_45458915/article/details/106954015
#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> using namespace std; typedef long long LL; typedef unsigned long long ull; const int inf=0x3f3f3f3f; const int N=1e5+100; vector<int>pos[N]; struct Node { int l,r,mmax,lazy; }tree[N<<2]; void pushup(int k) { tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax); } void pushdown(int k) { if(tree[k].lazy) { int lz=tree[k].lazy; tree[k].lazy=0; tree[k<<1].lazy+=lz; tree[k<<1].mmax+=lz; tree[k<<1|1].lazy+=lz; tree[k<<1|1].mmax+=lz; } } void build(int k,int l,int r) { tree[k].l=l; tree[k].r=r; tree[k].mmax=tree[k].lazy=0; if(l==r) return; int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); } void update(int k,int l,int r,int val) { if(tree[k].r<l||tree[k].l>r) return; if(tree[k].l>=l&&tree[k].r<=r) { tree[k].lazy+=val; tree[k].mmax+=val; return; } pushdown(k); update(k<<1,l,r,val); update(k<<1|1,l,r,val); pushup(k); } int query(int k) { if(tree[k].mmax<0) return inf; if(tree[k].l==tree[k].r) return tree[k].l; pushdown(k); if(tree[k<<1].mmax>=0) return query(k<<1); else return query(k<<1|1); } void init(int c) { for(int i=1;i<=c;i++) { pos[i].clear(); pos[i].push_back(0); } } int main() { int n,c,k; while(scanf("%d%d%d",&n,&c,&k)!=EOF) { init(c); build(1,1,n); int ans=0; for(int i=1;i<=n;i++) { int num; scanf("%d",&num); update(1,pos[num].back()+1,i,-1); pos[num].push_back(i); if(pos[num].size()>k) update(1,pos[num][pos[num].size()-k-1]+1,pos[num][pos[num].size()-k],1); ans=max(ans,i-query(1)+1); } printf("%d\n",ans); } return 0; }