HDU6602 Longest Subarray（线段树+思维）

清疚 2021-11-11 04:52 251阅读 0赞

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

## 思路：线段树维护覆盖的区间，参考[https://blog.csdn.net/Ratina/article/details/97503663][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("%d\n",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("%d\n",n);
                continue;
            }
            solve();
        }
    	return 0;
    }

[https_blog.csdn.net_Ratina_article_details_97503663]: https://blog.csdn.net/Ratina/article/details/97503663