题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2006
数据传送门:noi_2010_piano
这题很经典!很好!
首先肯定是求前缀和,然后搞n个结构体,第i个表示左端点在i的线段的最值
每次取出最大的结构体进行拓展,需要用函数式线段树来支持区间k大
时间复杂度:O(k*log(值域))
另外这题还有ST表的做法,但还不是很会 qwq
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 500000+9;
const int M = 20000000+9;
const int BAS = 500000010;
const int INF = 1000010000;
int n,k,L,R,arr[N];
struct Query{
int pos,num,val;
bool operator < (const Query & B) const {
return val < B.val;
}
};
priority_queue<Query> que;
namespace Chair_Tree{
#define CT Chair_Tree
int ch[M][2],sum[M],cnt,root[N],ans_tmp;
void insert(int p, int &w, int l, int r, int v) {
w = ++cnt; sum[w] = sum[p] + 1;
memcpy(ch[w],ch[p],sizeof(ch[0]));
if (l < r) {
int mid = l + r + 1 >> 1;
if (v < mid) insert(ch[p][0], ch[w][0], l, mid-1, v);
else insert(ch[p][1], ch[w][1], mid, r, v);
}
}
inline void insert(int p, int w) {
insert(root[p-1], root[p], 1, INF, w);
}
void query(int p, int w, int l, int r, int num) {
if (l == r) ans_tmp = l;
else {
int mid = l + r + 1 >> 1;
if (sum[ch[w][1]] - sum[ch[p][1]] >= num) query(ch[p][1], ch[w][1], mid, r, num);
else query(ch[p][0], ch[w][0], l, mid-1, num - (sum[ch[w][1]] - sum[ch[p][1]]));
}
}
inline int query(int l, int r, int num) {
query(root[l-1],root[r],1,INF,num);
return ans_tmp;
}
};
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
int main(){
n = read(); k = read(); L = read(); R = read();
for (int i=1;i<=n;i++) arr[i] = arr[i-1] + read();
for (int i=1;i<=n;i++) CT::insert(i,arr[i] + BAS);
for (int i=1;i+L-1<=n;i++) {
Query tmp; tmp.pos = i; tmp.num = 1;
tmp.val = CT::query(i+L-1, min(n,i+R-1), 1) - BAS - arr[i - 1];
que.push(tmp);
}
LL vout = 0;
for (int i=1,p;i<=k;i++) {
Query tmp = que.top(); que.pop();
vout += tmp.val;
if (tmp.num < R - L + 1) {
tmp.num++; p = tmp.pos;
if (n - (p+L-1) + 1 < tmp.num) continue;
tmp.val = CT::query(p+L-1, min(n,p+R-1), tmp.num) - arr[p - 1] - BAS;
que.push(tmp);
}
}
printf("%lld\n",vout);
return 0;
}