[2006: [NOI2010]超级钢琴][1]
一句话题意:计算出所有区间和中前K大
题解:
显然根据题目要求我们需要在$O(NlogN)$的时间复杂度内解决这个问题。
首先我们枚举左端点L,然后设区间右端点处在[qL,qR]这个区间。我们需要在$O(logN)$的时间复杂度内计算出从左端点到右端点区间和的最大值。如何快速的计算出这个最大值以及最大值所在的位置呢?
预处理出前缀和,这样的话我们上述问题就变成了$max(sum[R])-sum[L-1](R\in [qL,qR])$,显然我们只需要求出$sum[qL]……sum[qR]$中的最大值然后减去$sum[L-1]$
于是根据上述性质使用ST表或者是线段树维护一个二元组$(ans,i)$代表区间$sum[i]$的最大值和取到最大值的位置$i$就可以在$O(logN)$的时间复杂度内解决上述问题。
于是我们对于每个左端点求出对右端点区间内的最大值,并且使用一个五元组记录对应信息$(L,qL,qR,R,ans)$分别代表左端点,右端点取值区间$[qL,qR]$,产生答案的右端点,和对应答案,并且存入优先队列按照ans从大到小排序。我们每次从优先队列中取出一个元素,并且将值加到答案上,然后把这个五元组从R点分裂为两个较小的区间--$(L,qL,R-1,R_{new},ans_{new})$以及$(L,R+1,qR,R_{new},ans_{new})$并且塞入优先队列。显然更具这种方法就可以不重不漏的统计出前K大区间和。
线段树
#include <bits/stdc++.h>
const int MAXN = 2000005;
using namespace std;
int n,k,l,r,qL,qR,ql,qr;
long long sum[MAXN],ans;
pair<long long,int>Max[MAXN],tmp;
struct node{
int L,qL,qR,R;
long long ans;
friend bool operator < (const node &A,const node &B){
return A.ans < B.ans;
}
}A,AL,AR;
priority_queue<node>Q;
inline int read()
{
int x = 0,f = 1;char ch = getchar();
while(ch < '0' || '9' < ch){if(ch == '-') f = -1;ch = getchar();}
while('0' <=ch && ch <='9'){x = x * 10 + ch - '0';ch = getchar();}
return x*f;
}
void update(int o,int L,int R){
if(L == R){
Max[o].first = sum[L];
Max[o].second = L;
return;
}
int M = L + R >> 1;
update(o<<1,L,M);
update(o<<1|1,M+1,R);
Max[o] = max(Max[o<<1],Max[o<<1|1]);
}
void query(int o,int L,int R){
if(ql <= L && R <= qr){
tmp = max(tmp,Max[o]);
return;
}
int M = L + R >> 1;
if(ql <= M) query(o<<1,L,M);
if(M < qr) query(o<<1|1,M+1,R);
}
inline void init()
{
n = read();k = read();qL = read();qR = read();
for(int i = 1;i <= n;i++) scanf("%lld",&sum[i]);
for(int i = 1;i <= n;i++)
sum[i] += sum[i-1];
update(1,1,n);
for(int i = 1;i <= n;i++)
{
A.L = i;
if(i+qL-1 > n) break;
ql = i+qL-1;
qr = min(i+qR-1,n);
tmp.first = -1000000000;tmp.second = 0;
query(1,1,n);
A.qL = ql;A.qR = qr;A.R = tmp.second;A.ans = tmp.first - sum[i-1];
Q.push(A);
}
}
int main()
{
init();
while(k--)
{
A = Q.top();Q.pop();
ans += A.ans;
ql = A.qL;qr = A.R - 1;
if(ql <= qr) {
tmp.first = -1000000000;tmp.second = 0;
query(1,1,n);
AL.L = A.L;AL.qL = ql;AL.qR = qr;AL.R = tmp.second;AL.ans = tmp.first - sum[A.L-1];
Q.push(AL);
}
ql = A.R + 1;qr = A.qR;
if(ql <= qr){
tmp.first = -1000000000;tmp.second = 0;
query(1,1,n);
AR.L = A.L;AR.qL = ql;AR.qR = qr;AR.R = tmp.second;AR.ans = tmp.first - sum[A.L-1];
Q.push(AR);
}
}
printf("%lld\n",ans);
return 0;
}