使用l,r指针游动。
然后使用记录游动过程中的最大值。
我离散化了一下。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
using namespace std;
#define maxn 110000
map<int,int>mp;
struct list
{int x;int get;int lose;int leap;
}node[maxn];
struct pian
{int ll;int now;int use;int all;
}ps[maxn];
int a[maxn];
int b[maxn];
int pre[maxn];
int st[maxn];
int last[maxn];
int main()
{int n,k;while(~scanf("%d%d",&n,&k)){mp.clear();for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];}sort(b+1,b+n+1);int qq=1;b[0]=0;b[n+1]=0;for(int i=1;i<=n;i++){if(b[i]!=b[i-1]){mp[b[i]]=qq;b[qq]=b[i];qq++;}}for(int i=1;i<=n;i++)a[i]=mp[a[i]];memset(node,0,sizeof(node));memset(ps,0,sizeof(ps));memset(pre,0,sizeof(pre));memset(st,0,sizeof(st));memset(last,0,sizeof(last));st[a[1]]=1;a[n+1]=0;for(int i=2;i<=n+1;i++){if(a[i]!=a[i-1]){int x=a[i-1];node[i-1].x=x;if(last[x]==0)node[i-1].lose=0;else node[i-1].lose=st[x]-last[x]-1;node[i-1].get=i-st[x];node[i-1].leap=1;st[a[i]]=i;pre[last[x]]=i-1;last[x]=i-1;}}/*for(int i=1;i<=n;i++){printf("%d ",node[i].lose);}cout<<endl;for(int i=1;i<=n;i++){printf("%d ",node[i].get);}cout<<endl;for(int i=1;i<=n;i++){printf("%d ",pre[i]);}cout<<endl;*/int ans=-1;for(int i=1;i<=n;i++){if(node[i].leap){int x=node[i].x;if(x==0)continue;int add=node[i].get;int sub=node[i].lose;ps[x].use+=sub;ps[x].now+=add;if(ps[x].ll==0){ps[x].ll=i;ps[x].all=max(ps[x].all,ps[x].now);ans=max(ans,ps[x].all);// cout<<i<<"-"<<ps[a[i]].now<<" "<<ps[a[i]].use<<endl;continue;}int y=ps[x].ll;while(ps[x].use>k){ps[x].now-=node[y].get;y=pre[y];ps[x].use-=node[y].lose;}ps[x].ll=y;ps[x].all=max(ps[x].all,ps[x].now);ans=max(ans,ps[x].all);}// cout<<i<<" "<<ps[a[i]].now<<" "<<ps[a[i]].use<<endl;}cout<<ans<<endl;}return 0;
}