题目
给定一个长度为N的序列，选择前k大的子串，问前k大的子串之和。 区间长度在[L,R]之间。
题解
题目给的条件： ①选择的是k个区间。 ②选择前k大的。 ③区间长度有限制。 要求什么： 问前k大的子串之和（区间受限制之后的）。 问题来了：怎么确定这个区间值是第几大？——>对于这种不确定具体排名的序列，我们可以进行二分。 二分出来一个区间值mid，求长度在[L,R]的区间值>=mid的区间个数k’， 比较k’和k进行二分。 假设要打暴力怎么做？ 枚举右端点i,则左端点
j∈[i−R,i−L]
。即求
sum[i]−sum[j]>=mid
的区间个数k’。 那么怎么尽快读取出每一个区间的具体信息呢？ 一定会想到用数据结构存储吧，那么可以使用主席树。每次增加
sum[i]
进主席树里面。 进行差分就可以得到每一个区间的具体信息了。 但是因为j的不同，
sum[i]−sum[j]
也不一样。这棵主席树是权值线段树，怎么在树上找到每个区间的值所在的点？ 这个我做不到。 考虑移项。将不等式变为
sum[i]−mid>=sum[j]
。每次查询在(i-L)-(i-R)这棵树中范围在
∈(−∞,sum[i]−mid)
元素的个数。 这样可以将被查询的范围变成一个定区间。 这样就找出了第k大的区间值。 接下来考虑统计答案。（设第k大的区间值为mid） 问题：①区间排名的无序性。②区间值具体性。 对于①，显然不必考虑。因为之后查询的区间值大于mid的区间个数k’一定≤k。 对于②，枚举i，确定j的范围，查询在(i-L)-(i-R)这棵树中范围在
∈(−∞,sum[i]−mid)
元素的个数即可。
总结
①建树之后考虑什么: ⑴维护; ⑵查询(本题中主要考虑查询的区间); (⑶修改(本道题不用考虑这个)) ②若题目要求考虑多个区间，使用数据结构查询的时候，尽量将要查询的范围变为定区间。 ③区间长度受限制，那么被计入答案的区间值也受到了限制，如何突破这一限制： 一般时间复杂度为O(n log n)。 枚举左/右端点的其中一个，二分另一个端点。
代码
using namespace std;
struct note{
LL sum,ls,rs;
};note
tr[N
*50];
LL i,j,k,l,r,len,n,
m,tot,ans,
x,temp,temp1,cnt;
LL a[M
*M],val[N],sum[N];
LL rt[N];
LL L,R,MID;
LL
read(){
LL res=
0,fh=
1;char ch;
while((ch<
'0'||ch>
'9')&&ch!=
'-')ch=getchar();
if(ch==
'-')fh=-
1,ch=getchar();
while(ch>=
'0'&&ch<=
'9')res=res
*10+ch-
'0',ch=getchar();
return res
*fh;
}
void ins(LL px,LL py,LL l,LL r,LL
x){
tr[px]=
tr[py];
tr[px].sum=
tr[py].sum+
1;
if(l==r)
return;
LL wz=(l+r)/
2;
if(
x<=wz){
tr[px].ls=++tot;ins(
tr[px].ls,
tr[py].ls,l,wz,
x);}
else{
tr[px].rs=++tot;ins(
tr[px].rs,
tr[py].rs,wz+
1,r,
x);}
}
LL find(LL px,LL py,LL l,LL r,LL
x,LL
y){
LL wz=(l+r)/
2;
if(l==
x && r==
y)
return tr[px].sum-
tr[py].sum;
if(l>
y||r<
x)
return 0;
if(
tr[px].sum-
tr[py].sum==
0)
return 0;
if(
y<=wz)find(
tr[px].ls,
tr[py].ls,l,wz,
x,
y);
else
if(
x>wz)find(
tr[px].rs,
tr[py].rs,wz+
1,r,
x,
y);
else
return find(
tr[px].ls,
tr[py].ls,l,wz,
x,wz)+find(
tr[px].rs,
tr[py].rs,wz+
1,r,wz+
1,
y);
}
LL check(LL
x){
LL i,temp,res=
0;
fo(i,l,n){
temp=sum[i]-
x;
res+=find(rt[i-l+
1],rt[max((LL)
0,i-r)],
1,
2*MAXN+
1,
1,temp+MAXN+
1);
if(res>=k)
break;
}
return res;
}
void search(LL px,LL py,LL l,LL r,LL
x,LL
y){
if(l>
y||r<
x)
return;
if(cnt==k)
return;
if(
tr[px].sum-
tr[py].sum==
0)
return;
if(l==r){
cnt+=
tr[px].sum-
tr[py].sum;
ans+=(temp1-(l-MAXN-
1))
*(tr[px].sum-
tr[py].sum);
return;
}
LL wz=(l+r)/
2;
search(
tr[px].rs,
tr[py].rs,wz+
1,r,
x,
y);
if(cnt==k)
return;
search(
tr[px].ls,
tr[py].ls,l,wz,
x,
y);
}
int main(){
freopen(
"fantasy.in",
"r",stdin);
freopen(
"fantasy.out",
"w",stdout);
n=
read();k=
read();l=
read();r=
read();
fo(i,
1,n)val[i]=
read(),sum[i]=sum[i-
1]+val[i];
fo(i,
1,n)ins(rt[i]=++tot,rt[i-
1],
1,
2*MAXN+
1,sum[i-
1]+MAXN+
1);
ins(rt[n+
1]=++tot,rt[n],
1,
2*MAXN+
1,sum[n]+MAXN+
1);
L=-MAXN,R=MAXN;
while(L<R){
if(L==R-
1){
if(check(R)>=k) L=R;
break;
}
MID=(L+R)/
2;
if(check(MID)>=k) L=MID;
else x=MID,R=MID-
1;
}
x=(L+R)/
2;
cnt=
0;ans=
0;
fo(i,l,n){
if(cnt==k)
break;
temp=(sum[i]-
x)-
1;
temp1=sum[i];
search(rt[i-l+
1],rt[max((LL)
0,i-r)],
1,
2*MAXN+
1,
1,temp+MAXN+
1);
}
ans+=(k-cnt)
*x;
printf(
"%lld",ans);
return 0;
}
