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
#include <bits/stdc++.h>
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
#include <bits/stdc++.h>
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)\) 的复杂度。我们来仔细考虑一下：

  1. 左儿子的最大值小于等于 \(x\)。此时左儿子的轮廓被完全覆盖，轮廓值就是 \(x\) 乘上区间长度。再递归右儿子即可。
  2. 左儿子的最小值大于 \(x\)。此时左儿子肯定要递归了。但是右儿子就必须不递归地算出来。怎么办呢？看上去没办法。但是我们发现右儿子的贡献其实是 calc(左儿子最大值)。这个东西是不是很眼熟？就是 push_up 里出现的那个。可以发现，在调用 calc 的时候，自己的“不受影响的轮廓值”应该是准确的，所以右儿子的 calc(左儿子最大值) 就等于自己的轮廓值减去左儿子的轮廓值。这样就充分利用了记录轮廓值的作用。

代码如下：

1
2
3
4
5
6
7
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;
}

但这只是整块的查询。我们如何区间查呢？

线段树的核心思想，就是把区间分成几个整块。我们可以从左到右处理整块。第一个整块就是它自己的轮廓值。而第二个整块是 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
#include <bits/stdc++.h>
using namespace std;

#define FILE_IO
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;
}