题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2006

题目分类：堆，杂题

题意：

给出一个长度为n的序列，求出数字和前k大的长度不超过r不小于l的子串的数字和之和。

题解：

发现对于全局维护前k个很困难。

但是可以考虑每次快速求出最大的，再在去掉最大的的情况下求出最大的，以此类推。

所以用一个堆维护。

如果起始位置确定那么最大的就容易求了，所以一开始堆中装以1-n开头的最大的区间共计n个。

每次弹出最大的之后加入可能的替代区间，即开头相同的最大区间，如果原先区间为[l1,r1]，那么就考虑右端点在r1前面和r1后面的两种情况，一定有一种是最大的。

程序：

/*
    PROG:sam
    LANG:C++
*/
#include<iostream> 
#include<fstream> 
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath> 
#include<algorithm> 
#include<queue> 
#include<map> 
#include<vector> 
#include<set> 
#include<list>
#include<utility> 
using namespace std;
long long n,a[600000],s[600000],ans,l,r,m,negainf;
struct segementtree
{
       long long lef[2100000],rig[2100000];
       pair<long long,int>val[2100000];
       inline void build(int x,int le,int ri)
       {
              lef[x]=le;
              rig[x]=ri;
              if  (le==ri)
              {
                  val[x].first=s[le];
                  val[x].second=le;
                  return;
              }
              build(x*2,le,(le+ri)/2);
              build(x*2+1,(le+ri)/2+1,ri);
              val[x]=max(val[x*2],val[x*2+1]);
       }
       inline pair<long long,int> query(int x,int le,int ri)
       {
              //cout<<x<<' '<<le<<' '<<ri<<endl;
              if  (le<=lef[x]&&ri>=rig[x])
              {
                  return val[x];
              }
              pair<long long,int>ss=make_pair(negainf,0);
              if(le<=rig[x*2])ss=max(ss,query(x*2,le,ri));
              if(ri>=lef[x*2+1])ss=max(ss,query(x*2+1,le,ri));
              return ss;
       }
}sgt;
long long v,stt,idx,lv,rv;
pair<long long,int>tmp;
priority_queue<pair<long long,pair<pair<int,int>,pair<int,int> > > >q;
inline void work()
{
       for (int i=1;i<=n;i++)
       {
           if(i+l-1>n)continue;
           tmp=sgt.query(1,i+l-1,min(n,i+r-1));
           q.push(make_pair(tmp.first-s[i-1],make_pair(make_pair(i,tmp.second),make_pair(i+l-1,min(n,i+r-1)))));
       }//puts("----");
       for (int i=1;i<=m;i++)
       {
           //cout<<q.size()<<endl;
           v=q.top().first;
           stt=q.top().second.first.first;
           idx=q.top().second.first.second;
           lv=q.top().second.second.first;
           rv=q.top().second.second.second;
           //cout<<v<<' '<<stt<<' '<<idx<<' '<<lv<<' '<<rv<<endl;
           q.pop();
           ans+=v;
           if  (lv!=idx)
           {
               //puts("---");
           tmp=sgt.query(1,lv,idx-1);
               //puts("---");
           q.push(make_pair(tmp.first-s[stt-1],make_pair(make_pair(stt,tmp.second),make_pair(lv,idx-1))));
               //puts("---");
           }
           if  (rv!=idx)
           {
               //puts("---");
           tmp=sgt.query(1,idx+1,rv);
               //puts("---");
           q.push(make_pair(tmp.first-s[stt-1],make_pair(make_pair(stt,tmp.second),make_pair(idx+1,rv))));
               //puts("---");
           }
       }
}
int main()
{
    scanf("%lld %lld %lld %lld",&n,&m,&l,&r);
    negainf=-((1<<31)-1);
    negainf=(-2)*negainf*negainf;
   // cout<<negainf<<endl;
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        s[i]=s[i-1]+a[i];
    }sgt.build(1,1,n);
    work();
    printf("%lld\n",ans);
    //system("pause");
    return 0;
}