洛谷2048 [NOI2010] 超级钢琴

题目大意

你有一个序列${a_i}$,你要找出$k$个不相同的区间$[l_i,r_i]$,满足$\forall \; i, (r_i-l_i+1) \in [L, R]$,使得这些区间的和最大。

求这个最大值

分析

我们发现这个题有点像$\texttt{P2085 最小函数值}$,我们考虑用一样的方法做

显然,对于这个序列,$i \in [1, n - l + 1]$的$a_i$都可以作为左端点,我们考虑建立一个堆,堆里放置以每个点为左端点的区间

堆里的节点可以记为$\texttt{(L, R, maxp, val, pos)}$
其中$\texttt{L, R}$分别表示当前区间的长度的上下界,$\texttt{pos}$表示该区间的左端点,$\texttt{maxp}$表示以$\texttt{pos}$为左端点且长度$\in \texttt{[L,R]}$的和最大的区间长度,$\texttt{val}$表示$[i, i + maxp - 1]$这个区间的和

初始把所有左端点$i$对应的区间$[i,i+l-1]$到$[i,\min(i+r-1,n)]$的和最大的区间加入堆中

每次我们取出堆中和最大的区间,设这个区间为$\texttt{(L, R, maxp, val, pos)}$

则我们把$\texttt{val}$记录进答案,并往堆里插入$\texttt{(L, maxp-1, maxp’, val’, pos)}$和$\texttt{(maxp+1, R, maxp’’, val’’, pos)}$

这里$\texttt{maxp’,val’,maxp’’,val’’}$分别表示左右半区间的最大和取到的位置和这个最大和

将这个操作执行$k$次,时间复杂度$\texttt{O(n log n)}$

PS. 维护区间的最大值和最大值位置可以用$\texttt{ST}$表维护

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>

#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)

const ll MaxN = 5e5 + 10;

struct node
{
ll maxp, val;
ll l, r, pos;
bool operator<(node x) const { return val < x.val; }
};

ll n, k, l, r;
std::priority_queue<node> q;
ll a[MaxN], lg[MaxN], sum[MaxN], max[MaxN][21], maxp[MaxN][21];

void query(ll l, ll r, ll &val, ll &pos)
{
ll len = lg[r - l + 1];
val = std::max(max[l][len], max[r - (1 << len) + 1][len]);
pos = (max[l][len] > max[r - (1 << len) + 1][len]) ? maxp[l][len] : maxp[r - (1 << len) + 1][len];
}

void prework()
{
lg[0] = -1;
for (ll i = 1; i <= n; i++)
maxp[i][0] = i, max[i][0] = sum[i], lg[i] = lg[i >> 1] + 1;
for (ll j = 1; j <= 20; j++)
for (ll i = 1; i <= n - (1 << j) + 1; i++)
max[i][j] = std::max(max[i][j - 1], max[i + (1 << (j - 1))][j - 1]);
for (ll j = 1; j <= 20; j++)
for (ll i = 1; i <= n - (1 << j) + 1; i++)
maxp[i][j] = ((max[i][j - 1] > max[i + (1 << (j - 1))][j - 1]) ? maxp[i][j - 1] : maxp[i + (1 << (j - 1))][j - 1]);
}

inline ll read()
{
ll x = 0, f = 1;
char ch = getchar();
while (ch > '9' || ch < '0')
{
if (ch == '-') f = 0;
ch = getchar();
}
while (ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f ? x : (-x);
}

int main()
{
n = read(), k = read();
l = read(), r = read();
for (ll i = 1; i <= n; i++)
a[i] = read(), sum[i] = sum[i - 1] + a[i];
prework();
for (ll i = 1; i <= n; i++)
{
ll pos, val;
if (i + l - 1 > n) break;
query(i + l - 1, std::min(i + r - 1, n), val, pos);
val -= sum[i - 1], pos -= i - 1;
q.push((node){pos, val, l, std::min(r, n - i + 1), i});
}
ll ans = 0;
for(ll i = 1; i <= k; i++)
{
node x = q.top();
q.pop(), ans += x.val;
if(x.maxp > x.l)
{
ll pos, val;
query(x.pos + x.l - 1, x.pos + x.maxp - 2, val, pos);
val -= sum[x.pos - 1], pos -= x.pos - 1;
q.push((node){pos, val, x.l, x.maxp - 1, x.pos});
}
if(x.maxp < x.r)
{
ll pos, val;
query(x.pos + x.maxp, x.pos + x.r - 1, val, pos);
val -= sum[x.pos - 1], pos -= x.pos - 1;
q.push((node){pos, val, x.maxp + 1, x.r, x.pos});
}
}
printf("%lld\n", ans);
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×