从 i=1 到 n 枚举当前右端点 r=i：
先查询 \operatorname{ask}(1, n, 1, i, n)，即左端点 \le i 时的最大答案，更新全局答案。
再更新线段树，让下一轮（r=i+1）的值正确：
若后面还有至少 S 个同类型（位置 \operatorname{tmp} 和 \operatorname{tmp2}），则：
$[\operatorname{tmp}, \operatorname{tmp2}-1]$ 加 $S$：数量从 $S+1$ 变成 $S+2$，被扔的该类型多一个，但区间长度也 $+1$，净增 $S$。
否则 $[i, n]$ 全部减 $1$。
## 时间复杂度
$O(n\log n)$。
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int a[1000005];
vector<int> pos[1000005];
int now[1000005],in[1000005];
struct node
{
int l,r,mx,add;
}t[4000005];
void downdate(int p)
{
if(t[p].add)
{
t[p*2].mx+=t[p].add;
t[p*2+1].mx+=t[p].add;
t[p*2].add+=t[p].add;
t[p*2+1].add+=t[p].add;
t[p].add=0;
}
}
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r;
t[p].add=0;
if(l==r) {t[p].mx=in[l];return;}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
t[p].mx=max(t[p*2].mx,t[p*2+1].mx);
}
void update(int l,int r,int p,int st,int ed,int k)
{
if(st<=l&&ed>=r)
{
t[p].mx+=k;
t[p].add+=k;
return;
}
downdate(p);
int mid=(l+r)/2;
if(st<=mid) update(l,mid,p*2,st,ed,k);
if(ed>mid) update(mid+1,r,p*2+1,st,ed,k);
t[p].mx=max(t[p*2].mx,t[p*2+1].mx);
}
int ask(int l,int r,int p,int st,int ed)
{
if(st<=l&&ed>=r) return t[p].mx;
downdate(p);
int val=0;
int mid=(l+r)/2;
if(st<=mid) val=max(val,ask(l,mid,p*2,st,ed));
if(ed>mid) val=max(val,ask(mid+1,r,p*2+1,st,ed));
return val;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
int T;
cin>>T;
for(int cas=1;cas<=T;cas++)
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=1000000;i++)pos[i].clear();
for(int i=1;i<=n;i++)
{
pos[a[i]].push_back(i);
now[i]=pos[a[i]].size();
}
for(int i=1;i<=1000000;i++)pos[i].push_back(n+1);
in[0]=0;
for(int i=1;i<=n;i++)
{
in[i]=in[i-1]+1;
if(now[i]==m+1) in[i]-=m+1;
else if(now[i]>m+1) in[i]--;
}
build(1,1,n);
int ans=0;
for(int i=1;i<=n;i++)
{
ans=max(ans,ask(1,n,1,i,n));
int num=a[i];
if(now[i]+m<(int)pos[num].size())
{
int tmp=pos[num][now[i]+m-1];
int tmp2=pos[num][now[i]+m];
update(1,n,1,i,tmp-1,-1);
update(1,n,1,tmp,tmp2-1,m);
}
else
update(1,n,1,i,n,-1);
}
cout<<"Case #"<<cas<<": "<<ans<<"\n";
}
return 0;
}
```