hdu6602 Longest Subarray（线段树）_线段树 出现次数大于等于k

题目链接

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

题目描述

 

输入输出

 

样例

Sample Input

7 4 2

2 1 4 1 4 3 2

Sample Output

4

题意

给定一个数组，数的范围是[1,C]，给定K，让你找一个最长的区间使得区间内任意一个出现的数在该区间内的数量都大于等于K 。

思路

这题难啊，不会做。看别人做的。

数组pos记录每个数字在数组中的位置，比如pos[3][4]表示第4个数字3在输入数组中的位置。

通过一个外层循环，从左到右枚举选中区间的右端点（设为r）。

接下来考虑左端点的选择。 设数组a[]，其中a[i]表示在以i为左端点，以r为右端点的区间中，共有多少个数字“符合要求”，即“出现次数大于等于k次，或者根本不在这个区间”。那么当a[i]==C时，说明[i,r]中所有数字都“符合要求”，是符合题目要求的一个区间。我们需要找到最左边的且a[i]==C的左端点，满足找到的区间最长。

建立一棵线段树维护数组a[]。每枚举一次右端点，更新一次线段树。

设当前右端点为i，该处数字为x，且此处为数字x第p次出现的位置（即i==pos[x][p]）。

首先将a[i]初始化为C-1（因为此时区间只有一个数字x，其他数字均符合要求，因为其他数字不在区间内）。

令区间[pos[x][p-1]+1,i-1]的a[]-1，因为由于i处数字x的出现，该区间需要将数字x考虑在内了，数字x不再满足“出现次数大于等于k次，或者根本不在这个区间”这个条件了，因此减去1.

令区间[pos[x][p-k]+1,pos[x][p-k+1]]的a[]+1，因为由于i处数字x的出现，从区间[pos[x][p-k]+1,pos[x][p-k+1]]选取的左端点到i这个区段内，数字x的出现次数开始大于等于k次了，符合要求了，因此加上1。

线段树维护最大值就行了，查询时返回最大值以及位置，为使最大值位置尽量靠左，优先查找左子树。当最大值等于C时，说明此结果是右端点为r情况下的最优解。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXM=1e5+10;
const int maxn=1e5+10;
int n,c,k,a[MAXM+5],st[(MAXM<<2)+5],pi[maxn+5];
int add[(MAXM<<2)+5];
int maxp[(MAXM<<2)+5];
vector<int>pos[maxn];
int s[maxn];
void build(int o,int l,int r){
    if(l==r){st[o]=a[l];maxp[o]=l;}
    else{
        int m=l+((r-l)>>1);
        build(o<<1,l,m);
        build((o<<1)|1,m+1,r);
        st[o]=max(st[o<<1],st[(o<<1)|1]);
        if(st[o<<1]==st[o]){
            maxp[o]=maxp[o<<1];
        }
        else{
            maxp[o]=maxp[(o<<1)|1];
        }
    }
}
 
void pushup(int o){
    st[o]=max(st[o<<1],st[o<<1|1]);
    if(st[o<<1]==st[o]){
        maxp[o]=maxp[o<<1];
    }
    else{
        maxp[o]=maxp[(o<<1)|1];
    }
}
  
void pushdown(int o,int l,int r){
    if(add[o]){
        add[o<<1]+=add[o];
        add[o<<1|1]+=add[o];
        int m=l+((r-l)>>1);
        st[o<<1]+=add[o];
        st[o<<1|1]+=add[o];
        add[o]=0;
    }
}
 
void update(int o,int l,int r,int ql,int qr,int addv){
    if(ql<=l&&qr>=r){
        add[o]+=addv;
        st[o]+=addv;
        return;
    }   
    pushdown(o,l,r);
    int m=l+((r-l)>>1);
    if(ql<=m)update(o<<1,l,m,ql,qr,addv);
    if(qr>=m+1)update(o<<1|1,m+1,r,ql,qr,addv);
    pushup(o);
}
 
struct node{
    int w;
    int p;
};
node query(int o,int l,int r,int ql,int qr){
    if(ql<=l&&qr>=r){
        node u;
        u.w=st[o];
        u.p=maxp[o];
        return u; 
    }
    pushdown(o,l,r);
    int m=l+((r-l)>>1);
    node ans;ans.w=0;
    if(ql<=m){ 
        node u=query(o<<1,l,m,ql,qr);
        if(u.w>ans.w){
            ans=u;
        }
    }
    if(qr>=m+1){
        node u=query(o<<1|1,m+1,r,ql,qr);
        if(u.w>ans.w){
            ans=u;
        }
    }
    return ans;
}
 
void init(){
    int i;
    for(i=0;i<maxn;i++)pos[i].clear();
    for(i=0;i<maxn;i++)pos[i].push_back(0);
    memset(st,0,sizeof(st));
    memset(add,0,sizeof(add));
    memset(maxp,0,sizeof(maxp));
    memset(a,0,sizeof(a));
    memset(pi,0,sizeof(pi));
}
 
int v(int l){
    node u=query(1,1,n,l,l);
    return u.w;
}
 
int main(){
    init();
    int i,j,l,r,p;
    while(scanf("%d%d%d",&n,&c,&k)!=EOF){
        int ans=0;
        init();
        for(i=1;i<=n;i++){
            scanf("%d",&s[i]);
            pos[s[i]].push_back(i);
            int b=pos[s[i]].size();
            pi[i]=b-1;
        }
        if(k==1){
            printf("%d\n",n);
            continue;
        }
        build(1,1,n);        
        for(i=1;i<=n;i++){        
            int x=s[i];
            p=pi[i];
            update(1,1,n,i,i,c-v(i));
            update(1,1,n,pos[x][p-1]+1,pos[x][p],-1);
            if(p-k>=0){
                update(1,1,n,pos[x][p-k]+1,pos[x][p-k+1],1);
            }
            node u=query(1,1,n,1,n);
            if(u.w>=c){
                ans=max(ans,i-u.p+1);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}