HDU6602 Longest Subarray（线段树+思维）

题意：长度为n的序列，求最大的子序列长度，要求子序列中所出现的数字个数>=k。

思路：线段树维护覆盖的区间，参考https://blog.csdn.net/Ratina/article/details/97503663。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+5;
int n,c,k,a[N],mx[4*N],lz[4*N];
vector<int> pos[N];
void bd(int o,int l,int r) {
if(l==r) {
mx[o]=lz[o]=0;
return ;
}
int m=(l+r)/2;
bd(2*o,l,m);
bd(2*o+1,m+1,r);
mx[o]=max(mx[2*o],mx[2*o+1]);
lz[o]=max(lz[2*o],lz[2*o+1]);
}
void pd(int o,int l,int r) {
if(lz[o]) {
lz[2*o]+=lz[o];
lz[2*o+1]+=lz[o];
mx[2*o]+=lz[o];
mx[2*o+1]+=lz[o];
lz[o]=0;
}
}
void up(int o,int l,int r,int ql,int qr,int val) {
if(ql<=l&&qr>=r) {
mx[o]+=val;
lz[o]+=val;
return ;
}
pd(o,l,r);
int m=(l+r)/2;
if(qr<=m) up(2*o,l,m,ql,qr,val);
else if(ql>m) up(2*o+1,m+1,r,ql,qr,val);
else {
up(2*o,l,m,ql,qr,val);
up(2*o+1,m+1,r,ql,qr,val);
}
mx[o]=max(mx[2*o],mx[2*o+1]);
}
int qu(int o,int l,int r,int val) {
if(l==r) return l;
pd(o,l,r);
int m=(l+r)/2;
if(mx[2*o]==val) return qu(2*o,l,m,val);
else if(mx[2*o+1]==val) return qu(2*o+1,m+1,r,val);
else return -1;
}
int cur[N];
void solve() {
int ans=0;
memset(cur,0,sizeof(cur));
memset(mx,0,sizeof(mx));
memset(lz,0,sizeof(lz));
for(int i=1;i<=n;i++) {
int p=++cur[a[i]];
up(1,1,n,i,i,c-1);
if(pos[a[i]][p]-pos[a[i]][p-1]>1)
up(1,1,n,pos[a[i]][p-1]+1,pos[a[i]][p]-1,-1);
if(p>=k)
up(1,1,n,pos[a[i]][p-k]+1,pos[a[i]][p-k+1],1);
int res = qu(1,1,n,c);
if(res!=-1) ans=max(ans,i-res+1);
}
printf("%dn",ans);
}
int main(){
while(~scanf("%d%d%d",&n,&c,&k)) {
for(int i=1;i<=c;i++) pos[i].clear();
for(int i=1;i<=c;i++) pos[i].push_back(0);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
pos[a[i]].push_back(i);
}
if(k==1) {
printf("%dn",n);
continue;
}
solve();
}
return 0;
}

最后

以上就是娇气烤鸡为你收集整理的HDU6602 Longest Subarray（线段树+思维）的全部内容，希望文章能够帮你解决HDU6602 Longest Subarray（线段树+思维）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。