「BZOJ-4504」K个串-主席树

兔子们在玩 $k$ 个串的游戏。首先,它们拿出了一个长度为 $n$ 的数字序列,选出其中的一
个连续子串,然后统计其子串中所有数字之和(注意这里重复出现的数字只被统计一次)。

兔子们想知道,在这个数字序列所有连续的子串中,按照以上方式统计其所有数字之和,第
$k$ 大的和是多少。

链接

BZOJ-4504

题解

问题就是询问 $k$ 大子串和,考虑区间裂解,把以每个位置结尾的初始最优解和左端点可行区间都扔到大根堆里,每次取堆顶并把可行区间分裂成两个,把分裂出的两个左端点可行区间及其最优解扔回堆里。

然后我们需要对每个右端点都建一棵线段树维护左端点取在每个位置时的子串和及其区间最大值,设这个位置的数上次出现的位置是p,那么左端点取在p及左边时子串和不会变化,去在p+1到当前位置这一段时答案会加上这个数,因此把p+1~当前位置这个区间都加上这个数即可,注意到每个右端点对应的线段树是可以从上一个版本的线段树快速更新得到的,使用主席树就好了……

这里有区间修改,因此需要标记永久化或者访问时下传标记+动态开点(下传标记据lcr说会写出心理阴影),标记永久化显然更好写。

代码

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/*
* created by xehoth on 25-02-2017
*/
#include <bits/stdc++.h>
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
if (s == t) {
t = (s = buf) + fread(buf, 1, IN_LEN, stdin);
if (s == t) return -1;
}
return *s++;
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig = false, c = read(); !isdigit(c); c = read()) {
if (c == '-') iosig = true;
if (c == -1) return;
}
for (x = 0; isdigit(c); c = read())
x = (x + (x << 2) << 1) + (c ^ '0');
if (iosig) x = -x;
}
const int MAXN = 100010;
#define long long long
struct Data {
int x, y, l, r;
long sum;
Data(const int x, const int y, const int l, const int r, const long sum) : x(x), y(y), l(l), r(r), sum(sum) {}
inline bool operator<(const Data &x) const {
return sum < x.sum;
}
};
struct Node {
long max, lazy;
Node *lc, *rc;
int id;
} *root[MAXN], pool[MAXN * 40], *cur = pool;
inline void build(const int l, const int r, Node *&rt) {
rt = cur++, rt->id = l;
if (l == r) return;
register int mid = l + r >> 1;
build(l, mid, rt->lc), build(mid + 1, r, rt->rc);
}
inline void copy(Node *a, Node *b) {
a->lc = b->lc, a->rc = b->rc, a->lazy = b->lazy;
}
int s, t, d;
inline void insert(const int l, const int r, Node *&rt, Node *pre) {
rt = cur++, copy(rt, pre);
if (::s <= l && ::t >= r) {
rt->max = pre->max + ::d, rt->lazy += ::d, rt->id = pre->id;
return;
}
register int mid = l + r >> 1;
if (::s <= mid) insert(l, mid, rt->lc, pre->lc);
if (mid < ::t) insert(mid + 1, r, rt->rc, pre->rc);
if (rt->lc->max >= rt->rc->max) {
rt->max = rt->lc->max + rt->lazy, rt->id = rt->lc->id;
} else {
rt->max = rt->rc->max + rt->lazy, rt->id = rt->rc->id;
}
}
typedef std::pair<int, long> Pair;
inline Pair query(const int l, const int r, Node *rt) {
if (::s <= l && ::t >= r) return Pair(rt->id, rt->max);
register int mid = l + r >> 1;
if (::t <= mid) {
Pair tmp = query(l, mid, rt->lc);
tmp.second += rt->lazy;
return tmp;
} else if (::s > mid) {
Pair tmp = query(mid + 1, r, rt->rc);
tmp.second += rt->lazy;
return tmp;
} else {
Pair tmpl = query(l, mid, rt->lc), tmpr = query(mid + 1, r, rt->rc);
tmpl.second += rt->lazy, tmpr.second += rt->lazy;
return tmpl.second >= tmpr.second ? tmpl : tmpr;
}
}
int n, k, a[MAXN];
inline void solve() {
read(n), read(k);
build(1, n, root[0]);
static std::priority_queue<Data> q;
for (register int i = 1; i <= n; i++) {
static std::map<int, int> last;
read(a[i]);
s = last[a[i]] + 1, t = i, d = a[i];
insert(1, n, root[i], root[i - 1]);
s = 1;
Pair tmp = query(1, n, root[i]);
q.push(Data(i, tmp.first, 1, i, tmp.second));
last[a[i]] = i;
}
while (--k) {
Data data = q.top();
q.pop();
if (data.l < data.y) {
s = data.l, t = data.y - 1;
Pair tmp = query(1, n, root[data.x]);
q.push(Data(data.x, tmp.first, data.l, data.y - 1, tmp.second));
}
if (data.r > data.y) {
s = data.y + 1, t = data.r;
Pair tmp = query(1, n, root[data.x]);
q.push(Data(data.x, tmp.first, data.y + 1, data.r, tmp.second));
}
}
std::cout << q.top().sum;
}
int main() {
solve();
return 0;
}
分享到