Problem 1016 咒文卷軸 優先隊列+字首和+rmq

題目連結：

題目

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;
}