http://www.dxmtb.com/blog/noi2010piano/
题目的大意是：求出在一个长度为n的数列里，权和最大的不重复的k个长度从L到R的子序列。
首先考虑一个问题：当确定一个序列的右端点j时，左端点范围为[j-R+1,j-L+1]，如何求这个序列的最大权和？
我们设从第1个开始到第k个数的和为sum[k]，则对于一个序列A[i,j]，s[i,j]=sum[j]-sum[i-1]，s[i,j]为i到j的和。对于一个确定的j，max{s[i,j]}=s[j]-min{s[j-1]}，i为给定范围内的左端点，其中一个给定区间的最小值我们可以用RMQ的ST算法做到O(nlogn)-O(1)的复杂度，即O(nlogn)的时间预处理，O(1)的时间完成回答。
于是我们可以事先计算以1<=j<=n为右端点的所有序列最大值，即max{s[i,1]},max{s[i,2]},max{s[i,3]}（每个i范围不一定相同）……插入到一个堆，里，第一大的即为堆首元素，我们取出，之后怎么办呢？
假设我们取出的序列为(i,j)，以j为右端点的序列的左端点区间为[l,r]，我们就计算以同样以j为右端点，左端点区间分别为[l,j-1],[j+1,r]的两个节点的序列最大值计算后插入堆中，之后不断进行这一步，就保证了序列(i,j)不会被重复取用。
这样算法复杂度为O(nlogn+klog(n+k))，可以AC。
终于调完了。。。 （^-^）
一下午的奋斗成果（——by rfy）：
type
tree=record
v,ll,lr,r,wz:int64;
end;
var
tp,tp1,tp2:tree;
t:array[1..1000000] of tree;
n,k,l,r,tn,ans:int64;
i,j:longint;
a:array[0..1000000] of int64;
d:array[1..500050,0..30] of int64;
function max(a,b:int64):int64;
begin
if a>b then
exit(a)
else exit(b);
end;
function minwz(l,r:int64):int64;
var k:int64;
begin
if r=0 then
exit(0);
if l=0 then
begin
l:=1;
k:=trunc(ln(abs(r-l+1))/ln(2));
if a[d[l,k]]<a[d[r-1 shl k+1,k]] then
minwz:=d[l,k]
else minwz:=d[r-1 shl k+1,k];
if a[minwz]>0 then
minwz:=0;
exit;
end;
k:=trunc(ln(abs(r-l+1))/ln(2));
if a[d[l,k]]<a[d[r-1 shl k+1,k]] then
exit(d[l,k])
else exit(d[r-1 shl k+1,k]);
end;
procedure swap(x,y:int64);
var sw:int64;
begin
sw:=t[x].v;
t[x].v:=t[y].v;
t[y].v:=sw;
sw:=t[x].wz;
t[x].wz:=t[y].wz;
t[y].wz:=sw;
sw:=t[x].ll;
t[x].ll:=t[y].ll;
t[y].ll:=sw;
sw:=t[x].lr;
t[x].lr:=t[y].lr;
t[y].lr:=sw;
sw:=t[x].r;
t[x].r:=t[y].r;
t[y].r:=sw;
end;
procedure up(x:int64);
begin
if x<>1 then
if t[x].v>t[x div 2].v then
begin
swap(x,x div 2);
up(x div 2);
end;
end;
procedure down(x:int64);
begin
if (x*2>tn)and(x*2+1>tn) then
exit;
if x*2+1>tn then
begin
if t[x].v<t[x*2].v then
begin
swap(x,x*2);
down(x*2);
end;
exit;
end;
if x*2>tn then
begin
if t[x].v<t[x*2+1].v then
begin
swap(x,x*2+1);
down(x*2+1);
end;
exit;
end;
if t[x*2].v>t[x*2+1].v then
begin
if t[x].v<t[x*2].v then
begin
swap(x,x*2);
down(x*2);
end;
exit;
end
else
begin
if t[x].v<t[x*2+1].v then
begin
swap(x,x*2+1);
down(x*2+1);
end;
exit;
end;
end;
procedure insert(x:tree);
begin
inc(tn);
t[tn]:=x;
up(tn);
end;
procedure pop;
begin
t[1]:=t[tn];
dec(tn);
down(1);
end;
begin
readln(n,k,l,r);
for i:=1 to n do
begin
readln(a[i]);
a[i]:=a[i]+a[i-1];
d[i,0]:=i;
end;
//read
for j:=1 to trunc(ln(n)/ln(2)) do
for i:=1 to n-1 shl j+1 do
if a[d[i,j-1]]<a[d[i+1 shl (j-1),j-1]] then
d[i,j]:=d[i,j-1]
else d[i,j]:=d[i+1 shl (j-1),j-1];
//st
for i:=1 to n do
if i-l>=0 then
begin
tp.wz:=minwz(max(0,i-r),i-l);
tp.ll:=max(0,i-r);
tp.lr:=i-l;
tp.r:=i;
tp.v:=a[tp.r]-a[tp.wz];
insert(tp);
end;
//init
while k>0 do
begin
tp:=t[1];
ans:=ans+t[1].v;
dec(k);
pop;
if tp.wz<>tp.ll then
begin
tp1.wz:=minwz(tp.ll,tp.wz-1);
tp1.ll:=tp.ll;
tp1.lr:=tp.wz-1;
tp1.r:=tp.r;
tp1.v:=a[tp1.r]-a[tp1.wz];
insert(tp1);
end;
if tp.wz<>tp.lr then
begin
tp2.wz:=minwz(tp.wz+1,tp.lr);
tp2.ll:=tp.wz+1;
tp2.lr:=tp.lr;
tp2.r:=tp.r;
tp2.v:=a[tp2.r]-a[tp2.wz];
insert(tp2);
end;
end;
write(ans);
end.