20231106题解
piano
DP 好题。
首先做字符串哈希。定义 \(f_{i, j}\) 表示在第 \(i\) 个位置结尾涂上 \(j\) 的颜色。枚举这种颜色的每一个标语 \(q\),则 \(\max_{p=1}^{i - l_q - k} \max_c f_{p,c} \to f_{i, j}\)。另外,相同颜色不受 \(k\) 的限制,所以 \(\max_{p=1}^{i} f_{p,j} \to f_{i, j}\)。
我们用 \(g_{i, j}\) 表示 \(\max_{p=1}^{i} f_{p,j}\),\(g_{i, 0}\) 表示 \(\max_c g_{i,c}\)。显然这个前缀最值可以一边 dp 一边维护,而 \(f_{i, j} = \min(g_{i - l_q - k, 0},g_{i, j})\)。
时间复杂度 \(\mathcal{O}(nm)\)。题解说直接 DP 假了,但是我过了,也不知道为啥。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
using namespace std;
template <class T>
void read(T &r) {
r = 0; int ch, f = 0;
while (!isdigit(ch = getchar())) if (ch == 45) f ^= 1;
while (isdigit(ch)) (r *= 10) += ch - 48, ch = getchar();
if (f) r = -r;
}
const int maxn = 1e5 + 5, maxm = 3e1 + 5;
unsigned long long s[maxn], t[maxm], ps[maxn];
int l[maxm], n, m, k, id, p[maxn], w[maxm], c[maxm];
int dp[maxn][maxm], ans, g[maxn][maxm];
vector<int> in_c[maxm];
unsigned long long h(int l, int r) {
return s[r] - s[l - 1] * ps[r - l + 1];
}
bool compare(int id, int tid) {
if (id < l[tid]) return false;
return h(id - l[tid] + 1, id) == t[tid];
}
int main() {
freopen("piano.in", "r", stdin);
freopen("piano.out", "w", stdout);
read(n); read(m); read(k); read(id);
int ch = getchar(); ps[0] = 1;
for (int i = 1; i <= n; i++) {
while (!isalpha(ch)) ch = getchar();
s[i] = s[i - 1] * 131 + ch;
ps[i] = ps[i - 1] * 131;
ch = getchar();
}
for (int i = 1; i <= n; i++) read(p[i]);
cerr << "ok" << endl;
for (int i = 1; i <= m; i++) {
while (!isalpha(ch)) ch = getchar();
while (isalpha(ch)) (t[i] *= 131) += ch, l[i]++, ch = getchar();
read(w[i]); read(c[i]);
in_c[c[i]].emplace_back(i);
}
for (int i = 1; i <= m; i++) {
sort(in_c[i].begin(), in_c[i].end(), [](int a, int b) -> bool { return l[a] > l[b]; });
}
cerr << "ok" << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int tid : in_c[j]) {
if (compare(i, tid)) {
int tmp = 0;
if (i - l[tid] - k > 0) tmp = max(tmp, g[i - l[tid] - k][0]);
tmp = max(tmp, g[i - 1][j]);
tmp = max(tmp, dp[i][j]);
dp[i][j] = tmp + p[i - l[tid] + 1] + w[tid];
ans = max(dp[i][j], ans);
}
}
g[i][j] = max(g[i - 1][j], dp[i][j]);
g[i][0] = max(g[i][0], g[i][j]);
}
}
printf("%d\n", ans);
return 0;
}
restriction
高妙的分治。
考虑删除 \([l,r]\) 中的某个颜色的答案。我们可以将 \([l,mid]\) 中的所有颜色的边加入冰茶姬,然后递归求解 \((mid, r]\) 的解;再撤销这些边,把 \((mid, r]\) 颜色的边加入冰茶姬,递归求解 \([l, mid]\) 的解。
这个做法的复杂度关键是让加边操作可以复用,有一半的询问复用的相同的加边,就降低了复杂度。这样的思想可以通用,DP 中的决策单调性优化也是这个道理。
注意撤销冰茶姬的复杂度:我们可以不用路径压缩,只用启发式合并,这样每次加边最多只会影响边数个点。我们记录有哪些点被修改了,一个一个改回去即可。复杂度 \(\mathcal{O}(m \log k + n \log n)\)。
AC 代码: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
using namespace std;
template <class T>
void read(T &r) {...}
const int maxn = 1e5 + 5;
int n, m, k, ans1, ans2, f[maxn], cnt[maxn];
struct node { int u, v; node() {} node(int u, int v): u(u), v(v) {}};
vector<node> in_c[maxn];
int find(int x) {
return f[x] == x ? x : find(f[x]);
}
void solve(int l, int r) {
if (l == r) {
if (cnt[find(1)] == n) {
if (m - in_c[l].size() == n - 1) ans2++;
ans1++;
}
return;
}
int mid = (l + r) >> 1;
stack<pair<int, int> > history;
for (int i = l; i <= mid; i++) {
for (auto e : in_c[i]) {
int u = find(e.u), v = find(e.v);
if (u != v) {
if (cnt[v] > cnt[u]) swap(u, v);
history.emplace(u, v);
f[v] = u, cnt[u] += cnt[v];
}
}
}
solve(mid + 1, r);
while (!history.empty()) {
auto t = history.top(); history.pop();
f[t.second] = t.second;
cnt[t.first] -= cnt[t.second];
}
for (int i = mid + 1; i <= r; i++) {
for (auto e : in_c[i]) {
int u = find(e.u), v = find(e.v);
if (u != v) {
if (cnt[v] > cnt[u]) swap(u, v);
history.emplace(u, v);
f[v] = u, cnt[u] += cnt[v];
}
}
}
solve(l, mid);
while (!history.empty()) {
auto t = history.top(); history.pop();
f[t.second] = t.second;
cnt[t.first] -= cnt[t.second];
}
}
int main() {
freopen("restriction.in", "r", stdin);
freopen("restriction.out", "w", stdout);
read(n); read(m); read(k);
for (int i = 1; i <= m; i++) {
int u, v, c; read(u); read(v); read(c);
in_c[c].emplace_back(u, v);
}
for (int i = 1; i <= n; i++) f[i] = i, cnt[i] = 1;
solve(0, k - 1);
printf("%d %d\n", ans1, ans2);
return 0;
}
rprfq
单侧递归线段树好题。
如图所示,可以容纳的水体积其实是被水淹没后的“轮廓”(即图中红线部分)减去原本就是山的部分。山的总和可以用线段树快速维护。我们考虑如何计算轮廓大小。
容易发现,轮廓一定由一段单调不降的序列和一段单调不升的序列组成。而且,整个区间的最大值就是这两段序列的分界线。所以我们可以先用线段树维护出最大值的位置 \(mid\),然后分别在 \([l,mid]\) 上求单调不降的和以及 \([mid,r]\) 上单调不升的和。我们就以 \([l, mid]\) 为例。
所谓单调不降的和,就是每个点先变成区间内的前缀最大值,然后再求区间和。我们考虑如何维护整块的“单调不降的和”。也就是 push_up
和 push_down
。
对于 push_down
,很简单,无论某个点是取了自己的值还是取了前面一个更大的点的值,都会加上同一个标记,所以按照区间和的方式维护就好。
对于 push_up
则复杂一点。首先左儿子的贡献肯定能直接拿来用。但是右儿子就不行。因为左儿子的最大值有可能比右儿子开头的一些点更大,这样合并在一起轮廓就变大了。所以我们要再定义一个方法:calc(x)
,表示在左边有一个高度为 \(x\) 的山的影响之下,新的轮廓大小是多少。最终的 push_up
就是左儿子的值加上右儿子的 calc(左儿子最大值)
。
这个 calc
不能暴力算。在过程中,最多只能递归一次,这样才能保证 \(\mathcal{O}(\log^2 n)\) 的复杂度。我们来仔细考虑一下:
- 左儿子的最大值小于等于 \(x\)。此时左儿子的轮廓被完全覆盖,轮廓值就是 \(x\) 乘上区间长度。再递归右儿子即可。
- 左儿子的最小值大于 \(x\)。此时左儿子肯定要递归了。但是右儿子就必须不递归地算出来。怎么办呢?看上去没办法。但是我们发现右儿子的贡献其实是
calc(左儿子最大值)
。这个东西是不是很眼熟?就是push_up
里出现的那个。可以发现,在调用calc
的时候,自己的“不受影响的轮廓值”应该是准确的,所以右儿子的calc(左儿子最大值)
就等于自己的轮廓值减去左儿子的轮廓值。这样就充分利用了记录轮廓值的作用。
代码如下:1
2
3
4
5
6
7long long calcl(pos p, long long x) {
if (p -> val <= x) return x * len(p);
if (p -> l == p -> r) return max(x, p -> lval);
push_down(p);
if (p -> ls -> val <= x) return x * len(p -> ls) + calcl(p -> rs, x);
else return calcl(p -> ls, x) + p -> lval - p -> ls -> lval;
}
但这只是整块的查询。我们如何区间查呢?
线段树的核心思想,就是把区间分成几个整块。我们可以从左到右处理整块。第一个整块就是它自己的轮廓值。而第二个整块是 calc(第一个整块最大值)
,第三个整块是 calc(前两个整块最大值)
……我们只要在查询的时候,先递归左儿子,再递归右儿子,并在过程中维护整块最大值就好了。
不上升的和同理,不过要先递归右儿子,再递归左儿子,因为此时是后缀最大值的和。
由于 calc
只递归一次,总时间复杂度为 \(\mathcal{O}(m \log^2 n)\)。
AC 代码: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
using namespace std;
namespace io {...};
using namespace io;
const long long maxn = 5e5 + 5;
long long a[maxn];
struct node; typedef node* pos;
struct node { int l, r, id; long long sum, val, tag, lval, rval; pos ls, rs; node() {}};
node buf[maxn << 1], *buf_pos = buf, *root = buf;
pos new_node(int l, int r) { pos p = ++buf_pos; p -> l = l, p -> r = r; p -> ls = p -> rs = buf; return p; }
int len(pos p) { return p -> r - p -> l + 1; }
void update_one(pos p, long long x) { p -> tag += x, p -> val += x, p -> sum += x * len(p), p -> lval += x * len(p), p -> rval += x * len(p); }
void push_down(pos p) { if (p -> tag) update_one(p -> ls, p -> tag), update_one(p -> rs, p -> tag), p -> tag = 0; }
long long calcl(pos p, long long x) {
if (p -> val <= x) return x * len(p);
if (p -> l == p -> r) return max(x, p -> lval);
push_down(p);
if (p -> ls -> val <= x) return x * len(p -> ls) + calcl(p -> rs, x);
else return calcl(p -> ls, x) + p -> lval - p -> ls -> lval;
}
long long calcr(pos p, long long x) {
if (p -> val <= x) return x * len(p);
if (p -> l == p -> r) return max(x, p -> val);
push_down(p);
if (p -> rs -> val <= x) return x * len(p -> rs) + calcr(p -> ls, x);
else return calcr(p -> rs, x) + p -> rval - p -> rs -> rval;
}
void push_up(pos p) {
p -> val = max(p -> ls -> val, p -> rs -> val), p -> sum = p -> ls -> sum + p -> rs -> sum;
if (p -> val == p -> ls -> val) p -> id = p -> ls -> id;
else p -> id = p -> rs -> id;
push_down(p);
p -> lval = p -> ls -> lval + calcl(p -> rs, p -> ls -> val);
p -> rval = p -> rs -> rval + calcr(p -> ls, p -> rs -> val);
}
void build(pos p) {
if (p -> l == p -> r) p -> id = p -> l, p -> val = p -> sum = p -> lval = p -> rval = a[p -> l];
else {
int mid = (p -> l + p -> r) >> 1;
p -> ls = new_node(p -> l, mid), build(p -> ls);
p -> rs = new_node(mid + 1, p -> r), build(p -> rs);
push_up(p);
}
}
pair<long long, int> ask_max(pos p, int l, int r) {
if (l <= p -> l && p -> r <= r) return make_pair(p -> val, p -> id);
push_down(p);
if (l > p -> ls -> r) return ask_max(p -> rs, l, r);
else if (r < p -> rs -> l) return ask_max(p -> ls, l, r);
return max(ask_max(p -> ls, l, r), ask_max(p -> rs, l, r));
}
void update(pos p, int l, int r, long long x) {
if (l <= p -> l && p -> r <= r) return update_one(p, x);
push_down(p);
if (l <= p -> ls -> r) update(p -> ls, l, r, x);
if (p -> rs -> l <= r) update(p -> rs, l, r, x);
push_up(p);
}
long long ltmp;
long long askl(pos p, int l, int r) {
if (l <= p -> l && p -> r <= r) {
long long res = calcl(p, ltmp);
ltmp = max(ltmp, p -> val); return res - p -> sum;
}
push_down(p); long long res = 0;
if (l <= p -> ls -> r) res += askl(p -> ls, l, r);
if (p -> rs -> l <= r) res += askl(p -> rs, l, r);
return res;
}
long long rtmp;
long long askr(pos p, int l, int r) {
if (l <= p -> l && p -> r <= r) {
long long res = calcr(p, rtmp);
rtmp = max(rtmp, p -> val); return res - p -> sum;
}
push_down(p); long long res = 0;
if (p -> rs -> l <= r) res += askr(p -> rs, l, r);
if (l <= p -> ls -> r) res += askr(p -> ls, l, r);
return res;
}
int tid, n, m;
long long t, last_ans;
int main() {
freopen("rprfq.in", "r", stdin);
freopen("rprfq.out", "w", stdout);
read(tid); read(n); read(m); read(t);
for (int i = 1; i <= n; i++) read(a[i]);
root = new_node(1, n);
build(root);
while (m--) {
int op; read(op);
if (op == 1) {
long long tl, tr; long long x; read(tl); read(tr); read(x);
int l = tl ^ (t * last_ans); int r = tr ^ (t * last_ans);
update(root, l, r, x);
} else {
long long tl, tr; read(tl); read(tr);
int l = tl ^ (t * last_ans); int r = tr ^ (t * last_ans);
auto r1 = ask_max(root, l, r);
ltmp = 0xcfcfcfcfcfcfcfcf;
long long r2 = askl(root, l, r1.second);
rtmp = 0xcfcfcfcfcfcfcfcf;
long long r3 = askr(root, r1.second, r);
write(last_ans = (r2 + r3));
}
}
return 0;
}