Cool Pomelo

Per aspera ad astra. 循此苦旅，以达天际。

发表于 更新于 作者 Pomelorin ， Cool-breeze

欢迎来到 Pomelorin 和 Cool-breeze 的博客！希望我们能相互交流，共同进步～

图标是清爽葡萄柚汽水（确信）。

阅读全文 »

发表于 分类于 ， 作者 Pomelorin

模板——树上算法

LCA，树的一些性质，点分治，树上莫队，DFS 序与欧拉序，笛卡尔树，树上启发式合并，Kruskal 重构树，树链剖分。

LCA

  • \(O(n\log n)\) 预处理，\(O(\log n)\) 求答案。也可以求出欧拉环游序转化为 RMQ 问题，单次求答案变为 \(O(1)\)。
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
void dfs(ll root, ll dad) {
    f[0][root] = dad;
    dep[root] = dep[dad] + 1;
    for (auto son : e[root]) {
        if (son == dad) {
            continue;
        }
        dfs(son, root);
    }
}

ll LCA(ll x, ll y) {
    if (dep[x] < dep[y])
        swap(x, y);
    for (ll i = L; i >= 0; i--) {
        if (dep[f[i][x]] < dep[y])
            continue;
        x = f[i][x];
    }
    if (x == y)
        return x;
    for (ll i = L; i >= 0; i--) {
        if (f[i][x] == f[i][y])
            continue;
        x = f[i][x], y = f[i][y];
    }
    return f[0][x];
}
  • 离线 \(O(n)-O(1)\) Tarjan 求 LCA。
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 5e5 + 39;

ll n, m, s, dad[N], vis[N], ans[N];
vector<ll> e[N];
vector<PII> q[N];

ll find(ll x) {
    while (x != dad[x]) {
        x = dad[x] = dad[dad[x]];
    }
    return x;
}

void dfs(ll root) {
    dad[root] = root;
    vis[root] = 1;
    for (auto son : e[root]) {
        if (!vis[son]) {
            dfs(son);
            dad[son] = root;
        }
    }
    for (auto [son, id] : q[root]) {
        if (vis[son]) {
            ans[id] = find(son);
        }
    }
}

void solve() {
    cin >> n >> m >> s;
    for (ll i = 1, u, v; i <= n - 1; i++) {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (ll i = 1, a, b; i <= m; i++) {
        cin >> a >> b;
        q[a].push_back({b, i});
        q[b].push_back({a, i});
    }
    dfs(s);
    for (ll i = 1; i <= m; i++) {
        cout << ans[i] << endl;
    }
}

树的一些性质

直径

树上任意两节点之间最长的简单路径即为树的「直径」。

  • 一棵树可以有多条直径，他们的长度相等。
  • 可以用树形 DP 的方法在线性时间求出树的直径。

上面的性质在存在负权时依然成立。

  • 可以用两次 DFS 的方法在线性时间求出树的直径。
  • 树上所有直径都必定交于同一点（或同一条边），这个点（或边）被称为树的中心。
  • 合并两棵树，新树直径端点一定属于原来两棵子树直径端点的集合。
  • 对于树上任意一点 \(x\)，离它最远的点一定是直径的某个端点。

中心

在树中，如果节点 \(x\) 作为根节点时，从 \(x\) 出发的最长链最短，那么称 \(x\) 为这棵树的中心。

  • 树的中心不一定唯一，但最多有 2 个，且这两个中心是相邻的。树的中心一定位于树的直径上。
  • 树上所有点到其最远点的路径一定交会于树的中心。
  • 当通过在两棵树间连一条边以合并为一棵树时，连接两棵树的中心可以使新树的直径最小。

重心

三个等价定义：

  1. 在树中删去结点 \(v\) 后，得到的图中每个连通分量的大小均不超过原树结点数的一半。
  2. 在所有删去某个结点后得到的最大连通分量大小中，删去结点 \(v\) 时所得到的值最小。
  3. 树中所有结点到某个结点的距离和中，到结点 \(v\) 的距离和最小。

性质：

  • 树的重心如果不唯一，则恰有两个。这两个重心相邻。而且，删去它们的连边后，树将变为两个大小相同的连通分量。
  • 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
  • 把两棵树通过一条边相连得到一棵新的树，那么新树的重心在连接原来两棵树的重心的路径上。
  • 一棵有根树的重心一定在根结点所在的重链上。
  • 一棵树的重心一定是：根结点的 重子结点对应子树的 重心的 祖先。

点分治

只要路径信息能由“端点到分治中心”的摘要合并得到，并且能在每层快速查询/插入这些摘要，那么点分治就能处理整棵树所有简单路径的信息。算法框架如下：

1
2
3
4
5
solve(当前连通块):
    1. 找到重心 c
    2. 统计所有经过 c 的路径
    3. 删除 c
    4. 对 c 的每个子树递归 solve

注意在重新选择根节点之后一定要重新计算子树的大小。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 1e4 + 10, M = 1e7 + 10;

ll n, m, siz[N], vis[N], ans[N], que[N];
vector<PII> e[N];
bitset<M> b;

void getSiz(ll root, ll dad) {
    siz[root] = 1;
    for (auto [son, w] : e[root]) {
        if (son == dad || vis[son]) {
            continue;
        }
        getSiz(son, root);
        siz[root] += siz[son];
    }
}

ll getCent(ll root, ll dad, ll tal) {
    for (auto [son, w] : e[root]) {
        if (son == dad || vis[son]) {
            continue;
        }
        if (siz[son] > tal / 2) {
            return getCent(son, root, tal);
        }
    }
    return root;
}

void getInfo(ll root, ll dad, ll dis, vector<ll> &ret) {
    if (dis > M - 10) {
        return;
    }
    ret.push_back(dis);
    for (auto [son, w] : e[root]) {
        if (son == dad || vis[son]) {
            continue;
        }
        getInfo(son, root, dis + w, ret);
    }
}

void calcAns(ll root) {
    getSiz(root, root);
    ll cent = getCent(root, root, siz[root]);
    vector<ll> pre;
    pre.push_back(0);
    b[0] = 1;
    for (auto [son, w] : e[cent]) {
        if (vis[son]) {
            continue;
        }
        vector<ll> cur;
        getInfo(son, cent, w, cur);
        for (auto dis : cur) {
            for (ll i = 1; i <= m; i++) {
                if (que[i] >= dis && b[que[i] - dis]) {
                    ans[i] = 1;
                }
            }
        }
        for (auto dis : cur) {
            if (!b[dis]) {
                pre.push_back(dis);
                b[dis] = 1;
            }
        }
    }
    for (auto dis : pre) {
        b[dis] = 0;
    }
    pre.clear();
    vis[cent] = 1;
    for (auto [son, w] : e[cent]) {
        if (vis[son]) {
            continue;
        }
        calcAns(son);
    }
}

void solve() {
    cin >> n >> m;
    for (ll i = 1, u, v, w; i <= n - 1; i++) {
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    for (ll i = 1; i <= m; i++) {
        cin >> que[i];
    }
    calcAns(1);
    for (ll i = 1; i <= m; i++) {
        if (ans[i]) {
            cout << "AYE" << endl;
        } else {
            cout << "NAY" << endl;
        }
    }
}

树上莫队

普通树上莫队

利用下面的欧拉序性质，转化为普通莫队。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 2e5 + 10, L = 18;

// 判断树上一条链有无给定颜色

ll n, m, t[N];
ll st[N], ed[N], dfn[N], timer = 0;
ll col[N], cnt[N], ans[N], vis[N], Unit;
ll f[L + 5][N], dep[N];
vector<ll> e[N];

struct Query {
    ll l, r, id, col, extra;
    bool operator<(const Query &x) const {
        if (l / Unit != x.l / Unit)
            return l < x.l;
        if ((l / Unit) & 1)
            return r < x.r;
        return r > x.r;
    }
} q[N];

void dfs(ll root, ll dad) {
    dfn[++timer] = root;
    st[root] = timer;
    f[0][root] = dad;
    dep[root] = dep[dad] + 1;
    for (auto son : e[root]) {
        if (son == dad) {
            continue;
        }
        dfs(son, root);
    }
    dfn[++timer] = root;
    ed[root] = timer;
}

ll LCA(ll x, ll y) {
    if (dep[x] < dep[y])
        swap(x, y);
    for (ll i = L; i >= 0; i--) {
        if (dep[f[i][x]] < dep[y])
            continue;
        x = f[i][x];
    }
    if (x == y)
        return x;
    for (ll i = L; i >= 0; i--) {
        if (f[i][x] == f[i][y])
            continue;
        x = f[i][x], y = f[i][y];
    }
    return f[0][x];
}

void update(ll pos) {
    if (vis[dfn[pos]] == 0) {
        cnt[col[pos]]++;
    } else {
        cnt[col[pos]]--;
    }
    vis[dfn[pos]] ^= 1;
}

void solve() {
    cin >> n >> m;
    Unit = sqrt(n);
    for (ll i = 1; i <= n; i++) {
        cin >> t[i];
    }
    for (ll i = 1, u, v; i <= n - 1; i++) {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 1);
    for (ll i = 1; i <= L; i++) {
        for (ll j = 1; j <= n; j++) {
            f[i][j] = f[i - 1][f[i - 1][j]];
        }
    }
    for (ll i = 1; i <= n * 2; i++) {
        col[i] = t[dfn[i]];
    }
    for (ll i = 1, l, r, lca; i <= m; i++) {
        cin >> l >> r >> q[i].col;
        if (st[l] > st[r]) {
            swap(l, r);
        }
        lca = LCA(l, r);
        if (lca == l) {
            q[i].l = st[l];
            q[i].r = st[r];
        } else {
            q[i].l = ed[l];
            q[i].r = st[r];
            q[i].extra = st[lca];
        }
        q[i].id = i;
    }
    sort(q + 1, q + 1 + m);
    for (ll i = 1, l = 1, r = 0; i <= m; i++) {
        while (l > q[i].l)
            update(--l);
        while (r < q[i].r)
            update(++r);
        while (l < q[i].l)
            update(l++);
        while (r > q[i].r)
            update(r--);
        if (q[i].extra) {
            update(q[i].extra);
        }
        ans[q[i].id] = (cnt[q[i].col] >= 1);
        if (q[i].extra) {
            update(q[i].extra);
        }
    }
    for (ll i = 1; i <= m; i++) {
        cout << ans[i];
    }
    cout << endl;
}

DFS 序与欧拉序

DFS 序

对树做 DFS，每个节点第一次被访问时，记录下它的编号，得到的序列就是 DFS 序。通常用 dfn[u] 表示节点 u 是第几个被访问的。

  • 一棵子树的所有节点，在 DFS 序中恰好构成一段连续的区间。设 sz[u] 为以 u 为根的子树大小，那么子树 u 对应区间： [dfn[u], dfn[u] + sz[u] - 1]。
  • u 是 v 的祖先，当且仅当：dfn[u] <= dfn[v] <= dfn[u] + sz[u] - 1。

欧拉括号序

对树做 DFS，每次进入一个节点时记录一次，离开这个节点时再记录一次，得到的序列就是欧拉括号序。每个节点会出现两次，整个序列长度是 2n。

设 st[u] 节点 u 第一次出现的位置，ed[u] 节点 u 第二次出现的位置。

  • 子树仍然是一段区间。子树 u 在欧拉序中对应：[st[u], ed[u]]。这个区间里每个节点出现了两次。
  • 路径可以表示成区间。对于树上路径 (u, v)，假设 st[u] <= st[v]，令 p = LCA(u, v)：
    • 如果 p == u，路径对应区间 [st[u], st[v]]。
    • 如果 p != u，路径对应区间 [ed[u], st[v]]，再加上 p。
    • 区间内出现两次的节点，不在路径上；出现一次的节点，在路径上。

欧拉环游序

对树做 DFS，每次经过一个节点时都记录一次，得到的序列就是欧拉环游序。整个序列长度是 2n-1。

对树做 DFS，每次到达一个节点就记录它的编号，同时记录它的深度。这样得到两个序列：euler[] 节点编号序列，长度 2n-1；depth[] 对应节点的深度，长度也是 2n-1。

同时记录每个节点第一次出现在 euler[] 中的位置 first[u]。

对于任意两个节点 u 和 v，假设 first[u] <= first[v]，那么：

u 和 v 的 LCA，就是 euler[first[u] .. first[v]] 这段区间中，深度最小的那个节点。也就是说，LCA 问题变成了 区间最小值查询（RMQ）。

笛卡尔树

笛卡尔树是一种特殊的二叉树，每一个节点由一个键值二元组构成，并且同时满足以下两个性质：

  • 键——二叉搜索树（BST）性质：对于树中的每一个节点，其左子树中的所有节点的值都小于该节点的值；其右子树中的所有节点的值都大于该节点的值。这保证了树在中序遍历时会按照输入序列的顺序访问元素。
  • 值——堆性质：如果我们将笛卡尔树看作是一个最大堆或最小堆，则对于每个节点来说，它的值要么不小于或者不大于其子节点的值。具体采用哪种堆取决于应用场景。

经常用于最值维护、最近公共祖先问题。例如柱状图找面积最大的矩形。Treap 维护的也是笛卡尔树。

1
2
3
4
5
6
7
8
9
10
11
12
13
int cartesian_build(int n) {
    // 建树，满足小根堆性质
    for (int i = 1; i <= n; i++) {
        int k = i - 1;
        while (tree[k].val > tree[i].val)
            k = tree[k].par;
        tree[i].ch[0] = tree[k].ch[1];
        tree[k].ch[1] = i;
        tree[i].par = k;
        tree[tree[i].ch[0]].par = i;
    }
    return tree[0].ch[1];
}

树上启发式合并

例如计算 \(\sum_{d(x)=d(y),1\le x<y\le n}d(y)-d(lca(x,y))\)。

\(O(n\log n)\) 版：

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
vector<ll> e[N];
ll a[N], d[N], cnt[N], big[N], siz[N], ans;
ll dfn[N], L[N], R[N], index;
ll n, m;

ll dfs(ll root, ll dad) {
    ll curb = 0;
    d[root] = d[dad] + 1;
    siz[root]++;
    dfn[++index] = root;
    L[root] = index;
    for (auto son: e[root]) {
        if (son == dad)
            continue;
        siz[root] += dfs(son, root);
        if (siz[son] > curb) {
            curb = siz[son];
            big[root] = son;
        }
    }
    R[root] = index;
    return siz[root];
}

void dsu(ll root, ll dad, ll keep) {
    for (auto son: e[root]) {
        if (son == dad || son == big[root])
            continue;
        dsu(son, root, 0);
    }
    if (big[root])
        dsu(big[root], root, 1);
    for (auto son: e[root]) {
        if (son == dad || son == big[root])
            continue;
        for (ll i = L[son]; i <= R[son]; i++) {
            ans += cnt[d[dfn[i]]] * (d[dfn[i]] - d[root]);
        }
        for (ll i = L[son]; i <= R[son]; i++) {
            cnt[d[dfn[i]]]++;
        }
    }
    cnt[d[root]]++;
    if (keep == 0) {
        for (ll i = L[root]; i <= R[root]; i++) {
            cnt[d[dfn[i]]]--;
        }
    }
}

Kruskal 重构树

原图中两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = Kruskal 重构树上两点之间的 LCA 的权值。

也就是说，到点 x 的简单路径上最大边权的最小值 \(\leq val\) 的所有点 y 均在 Kruskal 重构树上的某一棵子树内，且恰好为该子树的所有叶子节点。

注意重构树新建了节点，初始化范围为 \(n+m\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
sort(h + 1, h + 1 + m, cmp);//按照边权排序
for (ll i = 1; i <= m; i++) {
    ll u = s.find(h[i].u), v = s.find(h[i].v);//并查集
    if (u != v) {
        cnt++;
        s.merge(u, cnt);
        s.merge(v, cnt);
        high[cnt] = h[i].len;//点权为边权
        e[u].push_back(cnt);
        e[cnt].push_back(u);
        e[v].push_back(cnt);
        e[cnt].push_back(v);
    }
}
dfs(cnt, cnt);

树链剖分

把一棵树上的节点重新编号，使得“树上的一条路径”和“一棵子树”都能变成数组上的连续区间。然后就可以用线段树、树状数组等维护区间加、区间求和、区间最大值。

从某个节点开始，一直沿着重儿子往下走，形成一条链，叫重链。每条重链有一个链顶 top。

我们做第二次 DFS 时，优先遍历重儿子，得到的节点编号顺序叫 DFS 序，记为 dfn[u]。

这样会得到两个重要性质：

  1. 同一条重链上的节点，dfn 是连续的。
  2. 任意一棵子树内的节点，dfn 也是连续的。
    • 子树 u 对应区间：[dfn[u], dfn[u] + sz[u] - 1]

所以树上问题就变成了数组区间问题。

只有链可以直接使用倍增，只有子树可以直接使用 dfs 序。

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
136
137
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 10;

ll n, m, r, p;
vector<ll> e[N];
ll a[N]; // 原树点权
ll b[N]; // 按 dfn 排列后的点权
ll fa[N], dep[N], sz[N], son[N];
ll top[N], dfn[N], rnk[N], timer = 0;

// 第一次 DFS：求父节点、深度、子树大小、重儿子
void dfs1(ll u, ll f) {
    fa[u] = f;
    dep[u] = dep[f] + 1;
    sz[u] = 1;
    son[u] = 0;

    for (ll v : e[u]) {
        if (v == f)
            continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) {
            son[u] = v;
        }
    }
}

// 第二次 DFS：分配 dfn，求 top
void dfs2(ll u, ll t) {
    top[u] = t;
    dfn[u] = ++timer;
    rnk[timer] = u;
    // 优先走重儿子
    if (son[u]) {
        dfs2(son[u], t);
    }
    // 再走轻儿子
    for (ll v : e[u]) {
        if (v == fa[u] || v == son[u])
            continue;
        dfs2(v, v);
    }
}

// 线段树：区间加，区间求和，省略（同线段树模板）
struct SGT {} Tree;

// 路径加
void path_add(ll u, ll v, ll k) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]])
            swap(u, v);
        Tree.add(1, 1, n, dfn[top[u]], dfn[u], k);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v])
        swap(u, v);
    Tree.add(1, 1, n, dfn[u], dfn[v], k);
}

// 路径求和
ll path_sum(ll u, ll v) {
    ll res = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]])
            swap(u, v);
        res += Tree.query(1, 1, n, dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v])
        swap(u, v);
    res += Tree.query(1, 1, n, dfn[u], dfn[v]);
    return res;
}

// 子树加
void subtree_add(ll u, ll k) {
    Tree.add(1, 1, n, dfn[u], dfn[u] + sz[u] - 1, k);
}

// 子树求和
ll subtree_sum(ll u) { return Tree.query(1, 1, n, dfn[u], dfn[u] + sz[u] - 1); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m >> r >> p;

    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (ll i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(r, 0);
    dfs2(r, r);

    // 把原树点权放到按 dfn 排列的数组里
    for (ll i = 1; i <= n; i++) {
        b[dfn[i]] = a[i];
    }
    Tree.build(1, 1, n, b);

    while (m--) {
        ll op, u, v;
        ll k;
        cin >> op;

        if (op == 1) {
            // 路径加
            cin >> u >> v >> k;
            path_add(u, v, k);
        } else if (op == 2) {
            // 路径求和
            cin >> u >> v;
            cout << path_sum(u, v) % p << '\n';
        } else if (op == 3) {
            // 子树加
            cin >> u >> k;
            subtree_add(u, k);
        } else if (op == 4) {
            // 子树求和
            cin >> u;
            cout << subtree_sum(u) % p << '\n';
        }
    }

    return 0;
}

方向合并：某些题目信息是不可交换的。在树链剖分跳链时，由于 dfn 顺序和真实路径方向可能相反，必须把某些区间的信息“翻转”后再按正确顺序合并。

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
Info query_path(int u, int v) {
    Info left, right;  // left: u -> LCA 方向
                       // right: LCA -> v 方向
    while (top[u] != top[v]) {
        if (dep[top[u]] >= dep[top[v]]) {
            // u 侧向上跳
            Info cur = seg.query(dfn[top[u]], dfn[u]);
            // cur 的 dfn 方向是 top[u] -> u
            // 真实路径方向是 u -> top[u]，所以翻转
            left = merge(left, rev(cur));
            u = fa[top[u]];
        } else {
            // v 侧向上跳
            Info cur = seg.query(dfn[top[v]], dfn[v]);
            // cur 的 dfn 方向是 top[v] -> v
            // 真实路径方向是 v -> top[v]，所以翻转
            right = merge(rev(cur), right);
            v = fa[top[v]];
        }
    }
    // 现在 u 和 v 在同一条链上
    if (dep[u] < dep[v]) {
        // u 是 LCA，路径 u -> v
        Info cur = seg.query(dfn[u], dfn[v]);
        // dfn 方向就是 u -> v，正好是 LCA -> v 方向
        right = merge(cur, right);
    } else {
        // v 是 LCA，路径 v -> u
        Info cur = seg.query(dfn[v], dfn[u]);
        // dfn 方向是 v -> u，翻转成 u -> v
        left = merge(left, rev(cur));
    }
    return merge(left, right);
}

发表于 更新于 分类于 ， 作者 Pomelorin

模板——数据结构2

线段树，树状数组，动态开点线段树，线段树合并，主席树，树套树，平衡树。

阅读全文 »

发表于 分类于 ， 作者 Pomelorin

B. 梦中星河

给定非负整数 \(x\)，求三个非负整数 \(a,b,c\) 满足 \(a\times b+c=x\)，并使得 \(\max(a,b,c)−\min(a,b,c)\) 尽可能小。输出该最小值。要求约 \(O(\sqrt x)\)。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin

G. 炒股高手

已知 \(n\) 个交易日中股票的股价（所有价格均以自然对数的形式给出）。可以购买非整数份的股票。共有 \(m\) 个时间区间，本金均为 \(e^k\)。求每个时间区间进行买入卖出后得到的总资产。\(n\le 10^5,m\le 10^5\)。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin ， Cool-breeze

D. 与或博弈

博弈规则如下：

  • gsh 和 AI 轮流操作，gsh 先手。
  • 他们操作两个非负整数 \(a\) 和 \(b\)，gsh 的目标是将其变为目标非负整数 \(x\) 和 \(y\)，而 AI 需要阻止 gsh 达成目标。
  • gsh 在自己的回合可以执行以下两种操作之一：
    1. \(a := a \mathbin{\&} v\)（按位与某个非负整数 \(v\)）。
    2. \(b := b \mathbin{|} v\)（按位或某个非负整数 \(v\)）。
  • AI 在自己的回合可以执行以下两种操作之一：
    1. \(a := a \mathbin{|} v\)（按位或某个非负整数 \(v\)）。
    2. \(b := b \mathbin{\&} v\)（按位与某个非负整数 \(v\)）。
  • 允许选择的 \(v\) 满足 \(0 \leq v \lt 2^{60}\)。
  • 双方都足够聪明，并且都会采取最优策略以赢得游戏。
  • 若在 \(10^{100}\) 回合内，存在某一时刻 \(a = x\) 且 \(b = y\)，则 gsh 获胜；否则，AI 获胜。

请你判断 gsh 是否必胜，若必胜，输出 Yes，否则输出 No。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin ， Cool-breeze

F. Inversion Pairs

只含有 01? 三种字符的字符串，可以把 ? 变成 0 或 1，求逆序对最多为多少。

逆序对 贪心 填法一定是左边都填 1，右边都填 0，枚举这个分界点即可。

预处理前缀 1 个数与后缀 0 个数，先假设都填 0，之后从左向右开始填 1。贡献变化为加后面 0 的个数减前面 1 的个数。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin ， Cool-breeze

CSP38 T4 月票发行

CSP38 T4 月票发行

题意：长度为 \(n\)（\(10^9\)）的字符串有 \(m\)（\(10^6\)）个固定为 #，其余能填任意小写字母。问至少有一个 ccf 和一个 cspark 子串，且至少有一个 ccf 出现在 cspark 前的字符串数量。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin

U227762 试卷排序

题目背景

期末考试临近了，yz 和 zzw 收到了来自老师的试卷关爱，但是试卷太多了，足足有 \(10^{6}\) 张，他们已经无法排好试卷了。

所以在 zzy 的建议下，他们把这个问题交给了你。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin ， Cool-breeze

P2472 蜥蜴 - 洛谷

P2472 蜥蜴 - 洛谷

最大流 考虑将问题转化为最多有几只蜥蜴能逃离。

把柱子的点拆成入点出点两部分，它们间的连边的容量就是柱子的高度（能跳出的次数）。

柱子的出点与所有距离 d 以内的柱子的入点和场外点连容量正无穷的边。

源点和有蜥蜴的柱子的入点连容量为 1 的边，场外点和汇点连容量正无穷的边。

阅读全文 »
0%