[COJ0989]WZJ的数据结构（负十一）
试题描述
给出以下定义：
1.若子序列[L,R]的极差（最大值-最小值）<=M，则子序列[L,R]为一个均匀序列。
2.均匀序列[L,R]的权值为Sum(L,R)即序列的元素和。
现在给你一个长度为N的整数序列A，请你求出权值前K大的均匀序列，输出K行为它们的权值。
输入
第一行为两个整数N,M,K。
第二行为N个整数Ai。
输出
输出K行，第i行为第i大的均匀序列的权值。
输入示例
输出示例
数据规模及约定
1<=N,K<=100000
0<=|Ai|,M<=10^9
保证原序列至少有K个均匀序列
题解
如果确定了一个区间的左端点 x，那么显然对于均匀序列 [x, y]，y 一定在区间 [L, R] 内。于是我们记状态 (x, l, r, v) 表示左端点为 x，右端点在 [l, r] 内，且最大的均匀序列权值为 v，那么我们可以预处理出对于所有的 i，(i, i, r, v) 这个状态，把它扔进堆里，然后每从堆顶取一个元素 (x, l, r, v)，我们可以用 RMQ 找到最优的右端点 p（即 S[p] - S[x-1] = v，S 为前缀和），使得 p 在 [l, r] 中，那么就输出这个 v，然后把 (x, l, p - 1, v') 和 (x, p + 1, r, v'') 放入堆中（其中 v' 和 v'' 都可以由求区间内最大前缀和得到），进行 k 次即可。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std; const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
} #define maxn 100010
#define maxlog 21
#define LL long long
int n, m, k;
LL S[maxn], A[maxn]; LL mx2[maxlog][maxn];
int mx[maxlog][maxn], mn[maxlog][maxn], Log[maxn], mxp[maxlog][maxn];
void rmq_init() {
Log[1] = 0;
for(int i = 2; i <= n; i++) Log[i] = Log[i>>1] + 1;
for(int i = 1; i <= n; i++) mx[0][i] = mn[0][i] = A[i];
for(int j = 1; j < maxlog; j++)
for(int i = 1; i + (1 << j) - 1 <= n; i++)
mx[j][i] = max(mx[j-1][i], mx[j-1][i+(1<<j-1)]),
mn[j][i] = min(mn[j-1][i], mn[j-1][i+(1<<j-1)]);
return ;
}
void rmq_init2() {
for(int i = 1; i <= n; i++) mx2[0][i] = S[i], mxp[0][i] = i;
for(int j = 1; j < maxlog; j++)
for(int i = 1; i + (1 << j) - 1 <= n; i++)
if(mx2[j-1][i] > mx2[j-1][i+(1<<j-1)]) mx2[j][i] = mx2[j-1][i], mxp[j][i] = mxp[j-1][i];
else mx2[j][i] = mx2[j-1][i+(1<<j-1)], mxp[j][i] = mxp[j][i] = mxp[j-1][i+(1<<j-1)];
return ;
}
int qmx(int l, int r, int tp) {
int t = Log[r-l+1], len = (1 << t);
if(tp == 1)
return max(mx[t][l], mx[t][r-len+1]);
return mx2[t][l] > mx2[t][r-len+1] ? mxp[t][l] : mxp[t][r-len+1];
}
int qmn(int l, int r) {
int t = Log[r-l+1], len = (1 << t);
return min(mn[t][l], mn[t][r-len+1]);
} struct Node {
int x, l, r; LL v;
bool operator < (const Node& t) const { return v < t.v; }
} ;
priority_queue <Node> Q; int R[maxn];
int main() {
n = read(); m = read(); k = read();
for(int i = 1; i <= n; i++) A[i] = read(), S[i] = S[i-1] + A[i]; rmq_init(); rmq_init2();
int nl = 1, nr = 0;
for(int i = 1; i <= n; i++) {
nr++;
while(qmx(nl, nr, 1) - qmn(nl, nr) > m) nl++;
R[nl] = nr;
// printf("%d %d %d %lld\n", nl, nr, qmx(nl, nr, 2), S[qmx(nl, nr, 2)] - S[nl-1]);
// Q.push((Node){ nl, nl, nr, S[qmx(nl, nr, 2)] - S[nl-1] });
}
for(int i = 1; i <= n; i++) if(!R[i]) R[i] = R[i-1];
for(nl = 1; nl <= n; nl++) {
LL tmp = S[qmx(nl, R[nl], 2)] - S[nl-1];
Q.push((Node){ nl, nl, R[nl], tmp });
// printf("%d %d %lld\n", nl, R[nl], tmp);
}
while(k--) {
Node u = Q.top(); Q.pop();
printf("%lld\n", u.v);
int p = qmx(u.l, u.r, 2);
if(u.l < p) Q.push((Node){ u.x, u.l, p - 1, S[qmx(u.l, p - 1, 2)] - S[u.x-1] });
if(p < u.r) Q.push((Node){ u.x, p + 1, u.r, S[qmx(p + 1, u.r, 2)] - S[u.x-1] });
} return 0;
}