题目链接：

题目

Problem 1016 咒文卷轴

Time Limit: 3000 mSec

Memory Limit : 131072 KB

问题描述

小Y 是一个魔法师，有一天他获得了一卷神秘而古老的咒文卷轴，其由N个咒文构成，每一个咒文都有一个威力值ai, 现在小Y可以借助该卷轴释放强力的魔法，一个魔法必须由编号连续的一段的、长度大于等于L且小于等于R的咒文构成，该魔法的威力为构成该魔法的每一个咒文的威力的总和，现在小Y想要释放K个不同的魔法，问最大能产生多大的威力值，若两个魔法是相同的，则其咒文编号的集合应该完全相同。

输入

第一行包含四个整数N,K,L,R,分别表示咒文个数，需要释放的魔法个数，以及魔法包含的咒文术的下限与上限。

接下来n行，每行一个数字ai，表示按编号从小到大每个咒文的威力值。

N<=100000

K<=100000

-1000<=ai<=1000,1<=L<=R<=N并且保证一定能释放k种不同的法术。

输出

仅一行，表示K个不同魔法威力值之和的最大值。要换行。

样例

input

4 3 2 3

3

2

-6

8

output

11

题解

考虑一个简单的版本，0 <= ai <= 1000，那么对于i开始的魔法，结尾为[l, r]之间的魔法肯定是递增的，所以只需要用一个优先队列，先把n个位置的值都丢进去，然后每次取出最大的[i, r]，然后在把[i, r - 1]丢回优先队列，直到r < l就不在丢进去，这样贪心能保证一定是从大到小取。

那么对于ai可以为负数的情况，前缀和就不满足递增了，然而对于一段区间[l, r]的和为两个前缀和相减，sum[r] - sum[l - 1]那么在左端点l固定的情况下，sum[r]越大越好，所以对于刚才那个问题等于是要取出优先队列中，区间[l, r]能取到前缀和值最大的位置mid，然后把区间在分成两部分[l, mid - 1], [mid + 1, r]丢回优先队列中，那么要维护一个区间最大值是个rmq问题，可以倍增st表O(nlogn)预处理一下，每次询问就是O(1)的，优先队列中的优先级就是区间最大值大的优先。这样就保证了取到的前k个法术一定是最大的。

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

#define X first

#define Y second

#define mp make_pair

using namespace std;

typedef __int64 LL;

const int maxn=1e5+10;

int arr[maxn];

LL sumv[maxn];

int n,k,l,r;

struct Node{

	int i,l,r,pos;

	Node(int i,int l,int r,int pos):i(i),l(l),r(r),pos(pos){}

	bool operator < (const Node& tmp) const {

		return sumv[pos]-sumv[i-1]<sumv[tmp.pos]-sumv[tmp.i-1];

	}

};

LL dp[maxn][20];

int pos[maxn][20];

void rmq(){

	for(int i=0;i<=n;i++) dp[i][0]=sumv[i],pos[i][0]=i;

	for(int j=1;(1<<j)<=n+1;j++){

		for(int i=0;i+(1<<j)-1<=n;i++){

			if(dp[i][j-1]<dp[i+(1<<(j-1))][j-1]){

				dp[i][j]=dp[i+(1<<(j-1))][j-1];

				pos[i][j]=pos[i+(1<<(j-1))][j-1];

			}

			else{

				dp[i][j]=dp[i][j-1];

				pos[i][j]=pos[i][j-1];

			}

		}

	}

}

int Max(int l,int r){

	if(l>r) return 10086;

	int k=0;

	while((1<<k)<=r-l+1) k++; k--;

	if(dp[l][k]<dp[r-(1<<k)+1][k]){

		return pos[r-(1<<k)+1][k];

	}

	return pos[l][k];

}

int main(){

	while(scanf("%d%d%d%d",&n,&k,&l,&r)==4){

		sumv[0]=0;

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

			scanf("%d",&arr[i]);

			sumv[i]=sumv[i-1]+arr[i];

		}

		rmq();

		LL ans=0;

		priority_queue<Node> pq;

		for(int i=1;i+r-1<=n;i++){

			pq.push(Node(i,i+l-1,i+r-1,Max(i+l-1,i+r-1)));

		}

		for(int i=n+2-r;i+l-1<=n;i++){

			pq.push(Node(i,i+l-1,n,Max(i+l-1,n)));

		}

		while(k--){

			while(pq.top().l>pq.top().r) pq.pop();

			Node nd=pq.top(); pq.pop();

			ans+=sumv[nd.pos]-sumv[nd.i-1];

			pq.push(Node(nd.i,nd.l,nd.pos-1,Max(nd.l,nd.pos-1)));

			pq.push(Node(nd.i,nd.pos+1,nd.r,Max(nd.pos+1,nd.r)));

		}

		printf("%I64d\n",ans);

	}

	return 0;

}