题目大意：给定一个序列。找到k个长度在[l,r]之间的序列。使得和最大

暴力O(n^2logn)，肯定过不去

看到这题的第一眼我OTZ了一下午。。。

后来研究了非常久别人的题解才弄明确怎么回事。。。蒟蒻果然不能理解大神的思路啊0.0

首先维护前缀和，那么以第i个元素结尾的和最大的序列自然就是sum[i]-min{sum[j]}(i-r<=j<=i-l)

然后我们维护一个大根堆，每取走一个以i为结尾的元素，增加sum[i]-2thmin{sum[j]}。再取走这个元素就增加sum[i]-3thmin{sum[j]}，以此类推

维护区间第k小，划分树。不说啥了吧 尼玛本大爷的划分树竟然还写挂了0.0

#include
     
      #include
      
       #include
       
        #include
        
         #define M 500500using namespace std;typedef pair
         
           abcd;typedef long long ll;int n,k,l,r;ll ans;int sum[M],a[M],b[M],c[M],s[22][M],now[M];abcd heap[M];int top;void insert(abcd x){	heap[++top]=x;	int t=top;	while(t>1&&heap[t]>heap[t>>1])		swap(heap[t],heap[t>>1]),t>>=1;}void pop(){	heap[1]=heap[top--];	int t=2;	while(t<=top)	{		if(t
          
           heap[t]) t++; if(heap[t]>heap[t>>1]) swap(heap[t],heap[t>>1]),t<<=1; else break; }}void Build_Tree(int l,int r,int dpt){ int i,mid=l+r>>1; int l1=l,l2=mid+1; int left=mid-l+1; if(l==r) return ; for(i=l;i<=r;i++) left-=a[i]
          
         
        
       
      
     

0:s[dpt][i-1]; } memcpy(a+l,b+l,r-l+1<<2); Build_Tree(l,mid,dpt+1); Build_Tree(mid+1,r,dpt+1); } int Get_Ans(int l,int r,int dpt,int x,int y,int k) { int mid=l+r>>1; int l1=x==l?

0:s[dpt][x-1],l2=s[dpt][y]; if(l==r) return c[mid]; if(k<=l2-l1) return Get_Ans(l,mid,dpt+1,l+l1,l+l2-1,k); else return Get_Ans(mid+1,r,dpt+1,(mid+1)+(x-l-l1),(mid+1)+(y-l+1-l2)-1,k-l2+l1); } int main() { //freopen("piano.in","r",stdin); //freopen("piano.out","w",stdout); int i; cin>>n>>k>>l>>r; for(i=1;i<=n;i++) scanf("%d",&sum[i]),sum[i]+=sum[i-1]; memcpy(a,sum,n+1<<2); memcpy(c,sum,n+1<<2); sort(c,c+n+1); Build_Tree(0,n,0); for(i=l;i<=n;i++) { now[i]=1; int temp=Get_Ans(0,n,0,max(i-r,0),i-l,1); insert( make_pair(sum[i]-temp,i) ); } for(i=1;i<=k;i++) { abcd temp=heap[1];pop(); if( now[temp.second]!=(temp.second-l)-( max(temp.second-r,0) )+1 ) insert( make_pair(sum[temp.second]-Get_Ans(0,n,0,max(temp.second-r,0),temp.second-l,++now[temp.second]),temp.second) ); ans+=temp.first; } cout<<ans<<endl; }