Description：

给一个数列，选 $k$ 个长度在 $[L,R]$ 的区间最大化区间和的和。

$1\le n \le 500000$

Solution：

与 K个串 类似的做法，用一个大根堆维护五元组 $(v,l,r,p,x)$ 表示区间左端点在 $v$ ，可以取值的范围在 $[l,r]$ ，在这个区间内区间和最大的位置在 $p$ ，区间和为 $x$ ，找区间最大值可以用 $ST$ 表，每次取出堆顶后将区间分裂为 $(v,l,p-1,r,p',x')$ 和 $(v,p+1,r,p'',x'')$ ，这样找 $k$ 次就是最终答案了。

$ST$ 表只用存位置就好了，查值直接去数组里查。 $ST$ 表一定要开二倍！！！

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cstring>

using namespace std;

int n,k,L,R;

#define MAXN 500010

typedef long long ll; 

ll val[MAXN];

ll sum[MAXN];

int g[MAXN << 1][20];

void makeST()

{

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

	for(int i = 1;i <= n;++i)g[i][0] = i;

	for(int k = 1;k <= 19;++k)

	{

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

		{

			if(sum[g[i][k - 1]] < sum[g[i + (1 << (k - 1))][k - 1]])

			{

				g[i][k] = g[i + (1 << (k - 1))][k - 1];

			}

			else

			{

				g[i][k] = g[i][k - 1];

			}

		}

	}

	return;

}

ll query_max(int l,int r)

{

	int len = log2(r - l + 1);

	return max(sum[g[l][len]],sum[g[r - (1 << len) + 1][len]]);

}

int query_pos(int l,int r)

{

	int len = log2(r - l + 1);

	if(sum[g[l][len]] > sum[g[r - (1 << len) + 1][len]])return g[l][len];

	else return g[r - (1 << len) + 1][len];

}

struct state

{

	int v,l,r,p;

	ll x;

};

struct cmp

{

	bool operator ()(state a,state b)

	{

		return a.x < b.x;

	}

};

priority_queue<state,vector<state>,cmp> q;

void insert(int v,int l,int r,int p,ll x)

{//cout << v << " " << l << " " << r << " " << p << " " << x << endl;

	q.push((state){v,l,r,p,x});

	return;

}

int main()

{

	scanf("%d%d%d%d",&n,&k,&L,&R);

	for(int i = 1;i <= n;++i)scanf("%lld",&val[i]);

	makeST();

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

	{

		int l = i + L - 1,r;

		if(i + R - 1 <= n)r = i + R - 1;

		else r = n;

		insert(i,l,r,query_pos(l,r),query_max(l,r) - sum[i - 1]);

	}

	ll ans = 0;

	for(int i = 1;i <= k;++i)

	{

		state k = q.top();q.pop();

		ans += k.x;//cout << k.x << endl;

		if(k.p != k.l)

		{

			insert(k.v,k.l,k.p - 1,query_pos(k.l,k.p - 1),query_max(k.l,k.p - 1) - sum[k.v - 1]);

		}

		if(k.p != k.r)

		{

			insert(k.v,k.p + 1,k.r,query_pos(k.p + 1,k.r),query_max(k.p + 1,k.r) - sum[k.v - 1]);

		}

	}

	cout << ans << endl;

	return 0;

}