[NOI2010]超级钢琴

嘟嘟嘟


这题思路和今年省选D1T1特别像（不对，应该是D1T1和这道题特别像）。
反正省选前我是没做，做了考场上那题也不一定能写出来（虽然确实不难）。


这题就是先求一个前缀和，然后维护一个大根堆，里面存一个三元组((val, id, rk))，表示以(id)为右端点，长度在(L, R)之间的(sum[id] - sum[i])的第(rk)大的值是(val)。
把堆中最大的取出来，再把第(rk + 1)放进队列里，这样循环(k)次就是答案。
求第(rk)大的最就是区间第(k)大，最直观的想法是主席树。也可以用st表做：因为每一次只是求排名比当前小1的，那么分治到两个子区间中查询最大值即可。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("") 
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 5e5 + 5;
const int maxt = 2e7 + 5;
inline ll read()
{
	ll ans = 0;
	char ch = getchar(), last = ' ';
	while(!isdigit(ch)) last = ch, ch = getchar();
	while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
	if(last == '-') ans = -ans;
	return ans;
}
inline void write(ll x)
{
	if(x < 0) x = -x, putchar('-');
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}

int n, K, L, R;
ll sum[maxn], T[maxn];
int l[maxn], r[maxn];

struct Tree
{
	int ls, rs, siz;
}t[maxt];
int root[maxn], tcnt = 0;
In void build(int& now, int L, int R, int id)
{
	++t[now = ++tcnt].siz;
	if(L == R) return;
	int mid = (L + R) >> 1;
	if(id <= mid) build(t[now].ls, L, mid, id);
	else build(t[now].rs, mid + 1, R, id);
}
In void insert(int old, int& now, int l, int r, int id)
{
	t[now = ++tcnt] = t[old];
	++t[now].siz;
	if(l == r) return;
	int mid = (l + r) >> 1;
	if(id <= mid) insert(t[old].ls, t[now].ls, l, mid, id);
	else insert(t[old].rs, t[now].rs, mid + 1, r, id);
}
In int query(int old, int now, int l, int r, int id)
{
	if(l == r) return l; 
	int mid = (l + r) >> 1, Sum = t[t[now].ls].siz - t[t[old].ls].siz;
	if(Sum >= id) return query(t[old].ls, t[now].ls, l, mid, id);
	else return query(t[old].rs, t[now].rs, mid + 1, r, id - Sum);
}

struct Node
{
	ll val; int id, rk;
	In bool operator < (const Node& oth)const
	{
		return val < oth.val;
	}
};
priority_queue<Node> q;

int main()
{
	n = read(), K = read(), L = read(), R = read();
	for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + read(), T[i] = sum[i];
	sort(T + 1, T + n + 2);
	int _n = unique(T + 1, T + n + 2) - T - 1;
	build(root[1], 1, _n, lower_bound(T + 1, T + _n + 1, 0) - T);
	for(int i = 1; i <= n; ++i) 
		insert(root[i], root[i + 1], 1, _n, sum[i] = lower_bound(T + 1, T + _n + 1, sum[i]) - T);
	for(int i = 1; i <= n; ++i) l[i] = max(0, i - R), r[i] = i - L + 1;
	for(int i = 1; i <= n; ++i)
	{
		if(l[i] >= r[i]) continue;
		int tp = query(root[l[i]], root[r[i]], 1, _n, 1);
		q.push((Node){T[sum[i]] - T[tp], i, 1});	
	}
	ll ans = 0;
	for(int i = 1; i <= K; ++i)
	{
		Node nod = q.top(); q.pop();
		ans += nod.val;
		if(nod.rk == r[nod.id] - l[nod.id]) continue;
		int tp = query(root[l[nod.id]], root[r[nod.id]], 1, _n, nod.rk + 1);
		q.push((Node){T[sum[nod.id]] - T[tp], nod.id, nod.rk + 1});
	}
	write(ans), enter;
	return 0;
}