关于我想了好久才想出这题咋做这档事 - 7

发表于 更新于 分类于
CF1527E, CF1149C, HDU5634, HDU6315, POJ2155 题解

#Prob. 1 CF1527E Partition Game

Time Limit: 3s | Memory Limit: 256MB

#题意简述

给你一个长度为 \(n\) 序列，定义其中一个连续子序列 \(t\) 的代价为： \[ cost(t)=\sum_{x\in set(t)}last(x)−first(x) \] 其中 \(set(t)\) 表示该子序列的元素集合，\(last(x)\) 表示 \(x\) 在该子序列中最后一次出现的位置，\(first(x)\) 表示 \(x\) 在该子序列中第一次出现的位置。

也就是说一个连续子序列的贡献为对于其中每种元素最后一次出现的位置与第一次出现的位置的下标差的和。现在你要把原序列划分成 \(k\) 个连续子序列，求最小代价和。

其中 \(1\leq n\leq35000,1\leq k\leq min(n,100),1\leq a_i \leq n\).

#大体思路

设 \(f_{i,j}\) 为把前 \(i\) 个数分为 \(j\) 段的最小代价，通过枚举枚举最后一段的长度，有转移方程： \[ f_{i,j}=\min_{1\leq k\leq i}\{f_{k-1,j-1}+cost(k,i)\}, \] 其中 \(cost(i,j)\) 表示将所有 \(a_k(k\in[i,j])\) 划分为一段的代价，来考虑如何计算 \(cost(i,j)\)，对于 \(a_j\)，假设 \(\exists k\in[i,j-1]\)，使得 \(a_k=a_j\)，那么应当有 \[ cost(i,j)=cost(i,j-1)+j-last_{a_j}, \] 其中 \(last_{a_j}\) 表示在 \([i,j-1]\) 中 \(a_j\) 最后一次出现的位置，否则就应当有 \(cost(i,j)=cost(i,j-1)\)，这里我们将原本整个的贡献拆分为了许多段。

直接暴力的时间复杂度为 \(O(kn^2)\)（\(cost\) 可以 \(n^2\) 预处理）。

考虑进行优化，我们拿出常用的方法：比较 \(f_{i,j}\) 和 \(f_{i+1,j}\) 的式子的区别： \[ \begin{aligned} f_{i,j}&=\min_{1\leq k\leq i}\{f_{k-1,j-1}+cost(k, i)\},\\ f_{i+1,j}&=\min_{1\leq k\leq i+1}\{f_{k-1,j-1}+cost(k,i+1)\}.\\ \end{aligned} \] 注意到上面两个式子仅有求 \(\min\) 范围和 \(cost\) 略有不同，于是考虑用一个数列维护\(j\) 相同时的候选序列，发现当且仅当 \(k\leq last_{a_{i+1}}\) 时 \(cost\) 才会改变，且一定是增加了 \(i+1-last_{a_{i+1}}\)，且 \(a_i\) 的改变对于 \(a_{i+1}\) 依旧有效，于是我们自前向后进行更新，对于求 \(\min\) 的范围，我们只需要在求 \(f_{i,j}\) 之前将 \(f_{i-1,j-1}\) 插入到 \(i\) 号位置即可。

于是我们只需要单点修改、区间修改以及区间取 \(\min\) 三个操作，直接 \(k\) 棵线段树即可。时间复杂度 \(O(kn\log n)\).

#Code

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
const int M = 105;
const int N = 4e4 + 5;
const int INF = 0x3fffffff;

template <typename T>
inline T Min(const T a, const T b) {
    return a < b ? a : b;
}

struct Node {int ls, rs, tag, minn;} p[N * M << 1];

int n, m, cnt, rt[N], a[N], lst[N], f[N][M], ans = INF;

inline void update(int k, int x) {
    p[k].minn += x, p[k].tag += x;
}

inline void pushup(int k) {
    p[k].minn = Min(p[p[k].ls].minn, p[p[k].rs].minn);
}

inline void pushdown(int k) {
    update(p[k].ls, p[k].tag);
    update(p[k].rs, p[k].tag);
    p[k].tag = 0;
}

inline void build(int &k, int l, int r) {
    if (!k) k = ++ cnt;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(p[k].ls, l, mid);
    build(p[k].rs, mid + 1, r);
}

void modify(int k, int l, int r, int x, int y, int c) {
    if (x <= l && r <= y) {update(k, c); return;}
    int mid = l + r >> 1; pushdown(k);
    if (x <= mid) modify(p[k].ls, l, mid, x, y, c);
    if (mid < y) modify(p[k].rs, mid + 1, r, x , y, c);
    pushup(k);
}

int query(int k, int l, int r, int x, int y) {
    if (x <= l && r <= y) return p[k].minn;
    int mid = l + r >> 1, ans = INF; pushdown(k);
    if (x <= mid) ans = Min(ans, query(p[k].ls, l, mid, x, y));
    if (mid < y) ans = Min(ans, query(p[k].rs, mid + 1, r, x, y));
    return ans;
}

int main() {
    scanf("%d%d", &n, &m); mset(f, 0x3f);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
    for (int i = 1; i <= m; ++ i) build(rt[i], 1, n);
    f[0][0] = 0;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= Min(i, m); ++ j) {
            modify(rt[j], 1, n, i, i, f[i - 1][j - 1]);
            if (lst[a[i]]) modify(rt[j], 1, n, 1, lst[a[i]], i - lst[a[i]]);
            f[i][j] = query(rt[j], 1, n, 1, i);
        }
        lst[a[i]] = i;
    }
    printf("%d", f[n][m]);
    return 0;
}

#Prob. 2 CF1149C Tree Generator™

Time Limit: 2s | Memory Limit: 256MB

#题意简述

定义一棵树的括号序列为从任意一点开始，每进入一个节点，就加入一个 (，每从一个节点退出，就加入一个 )，最终形成的序列。

给你一棵 \(n(n\leq10^5)\) 个节点的树的括号序列，输出它的直径。

有 \(m(m\leq10^5)\) 次询问，每次询问表示交换两个括号，输出交换两个括号后的直径（保证每次操作后都为一棵树）

#大体思路

不难（并不）发现一棵树的一条链在去掉中间所有匹配括号后一定形如下面的括号序列： \[ \begin{aligned} )))))\dots)))((((\dots((\\ )))))\dots)))))))))))))\\ (((((\dots((((((((((((( \end{aligned} \] 于是我们考虑如何去找这样一条最长的去匹配括号序列，我们考虑将字符串的表示转化为数字的表示，不妨用 \(1\) 表示 \((\)，用 \(-1\) 表示 \()\)，我们可以把交换操作看作两次修改操作，显然无法离线，于是需要考虑通过可以快速合并的信息来得到最终的答案，这里我们考虑用线段树进行维护。

我们称 ) 与 ( 相交的地方是中间点，那么第二种情况可以看作中间点是最右端，第三种情况则是中间点在最左端。然后合并时考虑中间点在哪些位置，需要哪些值进行维护，解释起来有些麻烦，建议结合代码并画图理解。

#Code

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
const int N = 1000010;
const int INF = 0x3fffffff;

template <typename T>
inline T Max(const T a, const T b) {return a > b ? a : b;}

template <typename T>
inline T Min(const T a, const T b) {return a < b ? a : b;}

struct Node {int ls, rs, s, lmx, rmn, lv, rv, lrv, v;} p[N];

int n, m, cnt, rt;
char S[N];

inline void pushup(int k) {
    p[k].s = p[p[k].ls].s + p[p[k].rs].s;
    p[k].lmx = Max(p[p[k].ls].lmx, p[p[k].rs].lmx + p[p[k].ls].s);
    p[k].rmn = Min(p[p[k].rs].rmn, p[p[k].ls].rmn + p[p[k].rs].s);
    p[k].lv = Max(Max(p[p[k].ls].lv, p[p[k].rs].lv - p[p[k].ls].s),
                  p[p[k].ls].lrv + p[p[k].rs].lmx);
    p[k].rv = Max(Max(p[p[k].rs].rv, p[p[k].ls].rv + p[p[k].rs].s),
                  p[p[k].rs].lrv - p[p[k].ls].rmn);
    p[k].lrv = Max(p[p[k].ls].lrv + p[p[k].rs].s, p[p[k].rs].lrv - p[p[k].ls].s);
    p[k].v = Max(Max(p[p[k].ls].v, p[p[k].rs].lv - p[p[k].ls].rmn), 
                 Max(p[p[k].rs].v, p[p[k].ls].rv + p[p[k].rs].lmx));
}

void build(int &k, int l, int r) {
    if (!k) k = ++ cnt;
    if (l == r) {
        p[k].s = (S[l] == '(' ? 1 : -1);
        p[k].lmx = Max(p[k].s, 0); p[k].rmn = Min(p[k].s, 0);
        p[k].lrv = p[k].lv = p[k].rv = p[k].v = 1;
        return;
    }
    int mid = l + r >> 1;
    build(p[k].ls, l, mid); build(p[k].rs, mid + 1, r);
    pushup(k);
}

void modify(int k, int l, int r, int x, int c) {
    if (l == r) {
        p[k].s = c, p[k].lmx = Max(p[k].s, 0);
        p[k].rmn = Min(p[k].s, 0); return;
    }
    int mid = l + r >> 1;
    if (x <= mid) modify(p[k].ls, l, mid, x, c);
    else modify(p[k].rs, mid + 1, r, x, c);
    pushup(k);
}

int main() {
    scanf("%d%d%s", &n, &m, S + 1);
    (n -= 1) <<= 1; build (rt, 1, n);
    printf("%d\n", p[rt].v);
    while (m --) {
        int a, b; scanf("%d%d", &a, &b);
        if (S[a] != S[b]) {
            swap(S[a], S[b]);
            modify(rt, 1, n, a, (S[a] == '(' ? 1 : -1));
            modify(rt, 1, n, b, (S[b] == '(' ? 1 : -1));
        }
        printf("%d\n", p[rt].v);
    }
    return 0;
}

#Prob. 3 HDU5634 Rikka with Phi

Time Limit: 8s | Memory Limit: 128MB

#Prob.4 HDU6315 Naive Operations

Time Limit: 3s | Memory Limit: 512MB

#Prob. 5 POJ2155 Matrix

Time Limit: 3s | Memory Limit: 64MB

#题意简述

给定一个 \(n\cdot n(n\leq1000)\) 的最初全为 \(0\) 的矩阵，\(q(q\leq50000)\) 次操作，操作分为两种：

  • 将左上角为 \((x_1,y_1)\)，右下角为 \((x_2,y_2)\) 中的所有值取反；
  • 询问 \((x,y)\) 位置的值；

#大体思路

将取反操作看作区间加一，那么就是每次询问一个位置值的奇偶性，于是就变为了二维树状数组的板子题。

#Code

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
#define mset(l, x) memset(l, x, sizeof(l))

const int N = 1010;
const int INF = 0x3fffffff;

int t, bit[N][N], n, q;

void add(int x, int y, int c) {
    int ty = y;
    while (x <= n) {
        y = ty;
        while (y <= n) bit[x][y] += c, y += y & -y;
        x += x & -x;
    }
}

inline void modify(int xa, int ya, int xb, int yb, int c) {
    add(xa, ya, c); add(xb + 1, yb + 1, c);
    add(xa, yb + 1, -c); add(xb + 1, ya, -c);
}

int query(int x, int y) {
    int res = 0, ty = y;
    while (x) {
        y = ty;
        while (y) res += bit[x][y], y -= y & -y;
        x -= x & -x;
    }
    return res;
}

int main() {
    scanf("%d", &t);
    while (t --) {
        mset(bit, 0); scanf("%d%d", &n, &q);
        while (q --) {
            char op; int xa, ya, xb, yb;
            cin >> op;
            if (op == 'C') {
                scanf("%d%d%d%d", &xa, &ya, &xb, &yb);
                modify(xa, ya, xb, yb, 1);
            } else {
                scanf("%d%d", &xa, &ya);
                printf("%d\n", query(xa, ya) & 1);
            }
        }
        printf("\n");
    }
    return 0;
}

其实本来还有一道题的 POJ3728 The merchant，也是一道树上倍增/树剖水题，但是写本文时突然发现自己当时 WA 了，但是对拍都没拍出错来，而今日身体状况实在不佳，不想 DEBUG 了，那就只能先咕咕咕了[流汗黄豆.jpg]

2021.11.02