题解区怎么没有和我做法一样的。
先考虑 。我们发现就是区间最大字段和问题。我们直接从左往右扫一遍即可。
我们发现这个做法本质上是对每个右端点找到最优的左端点计算代价更新答案，实际上是一个扫描线的过程。
我们考虑扫描线的同时尝试维护这个答案。
我们可以考虑用一个堆来维护前 大的元素。
我们发现，由于一个大区间是小区间加入若干个元素得到，因此大区间的前 大肯定对应偏序小区间的前 大。
如果一个区间的前 大偏序另一个区间并且这个区间的答案大于另一个区间时，我们发现另一个区间在之后任何时刻都不会更加优秀了。
因为此时你无论向两个区间里同时加入什么数，大区间增加的值不会小于小区间增加的值，并且加入后这个性质得以保留。
严格证明可以考虑对加入个数归纳。
那么，由于更左侧的左端点对应的前 大一定偏序右侧的前 大，因此只有答案大于前一个左端点时，这个区间才值得保留。
我们又发现，如果两个区间前 大集合相同，那么我们保留更大的那个即可。此外由于左侧一定偏序右侧，此时前 大的和也相同。
因此，我们维护一个下标递增（前 大递减 ）和递增的数组即可。
此时取出数组的最后一个元素就是当前的最优解。
我们考虑如何维护这样一个数组。
我们考虑暴力维护，从后往前扫描这个数组。如果一个堆里的最小元素比加入的这个元素大，那么就不管。显然后续的所有元素都不可能被更新。
然后对于堆里最小值小于加入元素的数组，我们直接加入，并往后尝试弹出值比自己小的元素，并且检查下一个元素的堆中元素和是否和自己相同，如果相同并且右侧更大，那么就弹出自己。
看上去这个做法错完了啊！
但是我们仔细考虑，这个东西似乎不是跑得很满。
我们仔细分析一下，进行一下势能分析。
考虑任意时刻数组中的元素 。假设前 大集合是 。考虑前一个元素前 大集合是 。
考虑将 从大到小排序找到第一个不同元素的位置。定义 的势能是这个元素之后的元素个数。特别的，数组的第一个元素势能定义为 。
一个数组的势能是所有元素的势能之和。
下面要来证明，上面的更新操作不会超过 次。
首先是弹出操作。
假设数组中相邻两个元素 都被更新（ 在 前），插入 。考察新插入的元素在 堆中的排名 。
对于值相等的元素，我们任意钦定一个顺序即可，我们这里采用下标作为第二关键字。下文的相等要求值和下标同时相等。
分两种情况考虑。
- 。此时会使 的势能减少 。 因为 的堆可以看成是 的堆加入一些元素得到的。如果任意一个元素被插入在 之前，那么 在 的排名就会增加，就不可能排名相同了。因此 的排名显然小于第一个不同位置的排名。另一方面，插入之后显然第一个不同位置的排名会增加 。
- 。此时 中排名显然比 中排名大。排名至少减少 ，这种情况最多出现 次。另一方面，这种情况显然会出现在第一个不同元素之后，因此对势能没有影响。
在一个元素的势能到达 时，意味着这个元素和上一个元素的堆完全相同。这个元素或者前一个元素将被移除。
当一个元素被移除时，后面元素的势能显然不会大于移除元素的势能加上原来的势能。
往堆中加入元素会增加最多 的势能。因此 的更新最多出现 次。第二种更新则是每次加入最多 次，总共 次。
复杂度是 。值得一提的是本题 ，因此这个做法的计算量是 左右。是可以接受的。
然后我们发现需要删除任意位置元素和尾部加入，链表即可。
实际上跑得飞快，没卡常甚至是次优解。
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
| #include <iostream>
#include <list>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
namespace solve {
struct item {
ll psum;
ll pqsum;
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
bool push(ll x) {
if (pq.empty() || x <= pq.top()) {
return false;
}
auto y = pq.top();
pq.pop();
pqsum -= y;
pqsum += x;
pq.push(x);
return true;
}
ll val() const { return -psum - pqsum; }
};
void solve() {
uint n, k;
std::cin >> n >> k;
std::vector<ll> v(n);
for (size_t i = 0; i < n; i++) {
std::cin >> v[i];
}
std::vector<ll> sum(n + 1);
for (size_t i = 0; i < n; i++) {
sum[i + 1] = sum[i] + v[i];
}
std::vector<item> val(n);
for (size_t i = 0; i + k < n; i++) {
val[i].psum = sum[i];
for (size_t j = i; j < i + k; j++) {
val[i].pqsum += v[j];
val[i].pq.push(v[j]);
}
val[i].push(v[i + k]);
}
ll ans = 0;
if (k == 0) {
ans = -0x3f3f3f3f3f3f3f3f;
}
std::list<item> stk;
for (size_t i = 0; i < n; i++) {
{
bool last = true;
for (auto it = stk.end(); it != stk.begin() && last;) {
auto nxt = it;
--it;
last = it->push(v[i]);
while (nxt != stk.end() && nxt->val() <= it->val()) {
nxt = stk.erase(nxt);
}
if (nxt != stk.end() && nxt->pqsum == it->pqsum) {
it = stk.erase(it);
}
}
}
if (i >= k) {
auto cur = i - k;
if (stk.empty() || val[cur].val() > stk.back().val()) {
while (!stk.empty() && stk.back().pqsum == val[cur].pqsum) {
stk.pop_back();
}
stk.push_back(val[cur]);
}
}
if (!stk.empty()) ans = std::max(ans, sum[i + 1] + stk.back().val());
}
std::cout << ans << "\n";
}
}
int main() {
solve::solve();
std::cout << std::flush;
}
|