bzoj2006: [NOI2010]超级钢琴

题意：给一个序列（n<=500000），要求选定k个不同区间，使得区间长度在L,R之间，并使得k个区间和之和最大，输出这个最大值。

刚拿到题的时候想的是，对于每个点，如果以它开头，那么之后的L-1个一定被选，剩下的R-L个可选，对这一部分进行最大前缀和就好啦！用主席树搞搞，建树的时候维护下就好了。

但有个问题，以这个区间为开头的情况不止一种，这种做法确实能求出以它开头的最大值，那次大值，k大值呢？这也是有可能计入答案的。所以不行。

正解是，对于一个位置，如果我们考虑以它结尾，这个区间等于它的前缀和减去前面一个位置的前缀和，其中位置i满足i离这个位置不小于L不超过R。对于这个位置，我们只需要找这个区间内的区间k大，用这个位置前缀和减掉就好了，然后去求区间k+1大。放入一个堆中取k次就好。

 #include<bits/stdc++.h>

 using namespace std;

 #define N 500005

 #define LL long long

 inline int read(){

     int x=,f=; char a=getchar();

     while(a<'' || a>'') {if(a=='-') f=-; a=getchar();}

     while(a>='' && a<='') x=x*+a-'',a=getchar();

     return x*f;

 }

 LL sum[N];

 struct data{

     int num,k;LL val;

     bool operator < (const data& w)const{

         return val<w.val;

     }

 }t;

 priority_queue<data>q;

 namespace Chairman_Tree{

     int root[N],size;

     struct ct{

         int son[],sz;

     }tr[];

     void insert(int x,int& y,LL l,LL r,LL v){

         y=++size; tr[y].sz=tr[x].sz+;

         if(l==r) return;

         memcpy(tr[y].son,tr[x].son,sizeof(tr[y].son));

         int mid=(l+r)>>;

         if(mid>=v) insert(tr[x].son[],tr[y].son[],l,mid,v);

         else insert(tr[x].son[],tr[y].son[],mid+,r,v);

     }

     LL query(int x,int y,LL l,LL r,int k){

         if(tr[y].sz-tr[x].sz<k) return 1e9;

         if(l==r) return l;

         int mid=(l+r)>>,s=tr[tr[y].son[]].sz-tr[tr[x].son[]].sz;

         if(k<=s) return query(tr[x].son[],tr[y].son[],l,mid,k);

         else return query(tr[x].son[],tr[y].son[],mid+,r,k-s);

     }

 }

 #define CT Chairman_Tree

 #define L -500000005

 #define R 500000005

 int main(){

     int n=read(),k=read(),l=read(),r=read();

     LL ans=; CT::insert(,CT::root[],L,R,);

     for(int i=;i<=n;i++) sum[i]=sum[i-]+read();

     for(int i=;i<=n;i++) CT::insert(CT::root[i-],CT::root[i],L,R,sum[i]);

     for(int i=l;i<=n;i++){

         int ri=i-l,le=i-r-;

         LL tmp;

         if(le<) tmp=CT::query(,CT::root[ri],L,R,);

         else tmp=CT::query(CT::root[le],CT::root[ri],L,R,);

         q.push((data){i,,sum[i]-tmp});

     }

     while(k--){

         t=q.top(); q.pop();

         ans+=t.val;

         int ri=t.num-l,le=t.num-r-; LL tmp;

         if(le<) tmp=CT::query(,CT::root[ri],L,R,t.k+);

         else tmp=CT::query(CT::root[le],CT::root[ri],L,R,t.k+);

         q.push((data){t.num,t.k+,sum[t.num]-tmp});

     }

     cout<<ans;

     return ;

 }

巴特西

bzoj2006: [NOI2010]超级钢琴

最新文章

热门文章