HDU6602线段树+思维_hdu6602详解

http://acm.hdu.edu.cn/showproblem.php?pid=6602

题意：给出一个1e5规模数列，数字范围也在1e5内，给出K，求最长子序列，使得序列中出现的任一数字都至少出现K次。

考虑枚举右端点，尺取法不好做，因为左端点没有简单的找法，，我们这样拆分问题：首先考虑每个数字的合法左端点的取法，易知对于数字a，若i出现不足K次，则左端点只能在最后一次a出现之后，即（最后一次a出现的位置,i]；如果a已经出现了K次，则还可以在[1,往前数第K次的位置）取到。于是我们考虑到，可以沿着数列a[i]更新区间状态，对于每个a[i]，根据a[i]是否已出现K次有两种更新左端点合理区间的操作。所以可以用线段树，使得对于每个数来说合理的左端点区间取值为1，不合理为0。最后query时，若某个点上值为c(数值上限），则说明该区间可取，因为每个数字在这个区间上都是合理的（要么不出现，要么已出现K次）。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
 
#define ls (rt<<1)
#define rs (rt<<1|1)
const int maxn=100010;
int n,c,k;
int a[maxn];
vector<int> pos[maxn];
struct Node{
    int dat,lazy;
    //dat的值为该段的合法点数量，需为c
}tr[maxn<<2];
 
int now[maxn];//表示某个数值的当前坐标
 
void pushup(int rt){
    tr[rt].dat=max(tr[ls].dat,tr[rs].dat);
    //有一个合法则该段合法
}
void pushdown(int rt){
    if(tr[rt].lazy){
        tr[ls].dat+=tr[rt].lazy;
        tr[rs].dat+=tr[rt].lazy;
        tr[ls].lazy+=tr[rt].lazy;
        tr[rs].lazy+=tr[rt].lazy;
        tr[rt].lazy=0;
    }
}
void build(int rt,int l,int r){
    tr[rt].lazy=0;
 
    if(l==r){
        tr[rt].dat=0;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(rt);
}
void update(int rt,int l,int r,int L,int R,int val){
    if(L>R)
        return;
    if(L<=l&&r<=R){
        tr[rt].dat+=val;
        tr[rt].lazy+=val;
        return;
    }
    pushdown(rt);   //要对该区间继续向下更新了，先把lazy标记处理了
    int mid=(l+r)>>1;
    if(L<=mid){
        update(ls,l,mid,L,R,val);
    }
    if(R>mid){
        update(rs,mid+1,r,L,R,val);
    }
    pushup(rt);
}
int query(int rt,int l,int r){
    if(l==r){
        return l;
    }
    int res=-1;
    int mid=(l+r)>>1;
    pushdown(rt);
    if(tr[ls].dat==c)
        res=query(ls,l,mid);
    else if(tr[rs].dat==c)
        res=query(rs,mid+1,r);
    return res;
}
 
int main(){
    while(~scanf("%d%d%d",&n,&c,&k)){
        for(int i=1;i<=c;i++){
            pos[i].clear();
            pos[i].push_back(0);
        }
        for(int i=1;i<=n;i++){
            scanf("%d",a+i);
            pos[a[i]].push_back(i);
        }
        build(1,1,n);
        for(int i=1;i<=c;i++){
            pos[i].push_back(n+1);
            update(1,1,n,pos[i][0]+1,pos[i][1]-1,1);
            now[i]=0;
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            int res=0;
            int t=a[i];
            update(1,1,n,pos[t][now[t]]+1,pos[t][now[t]+1]-1,-1);
//            if(now[t]>=k)
//                update(1,1,n,1,pos[t][now[t]-k+1],-1);
            now[t]++;   //更新当前值的个数
            update(1,1,n,pos[t][now[t]]+1,pos[t][now[t]+1]-1,1);
            if(now[t]>=k)
                update(1,1,n,pos[t][now[t]-k]+1,pos[t][now[t]-k+1],1);
 
            res=query(1,1,n);
            if(res!=-1)
                ans=max(ans,i-res+1);
        }
        printf("%d\n",ans);
    }
    return 0;
}