蒟蒻の模板

rainbow-auto
  2023-10-02 22:01:54 2023-10-02 22:01:54 Created   2025-11-24 22:48:20 2025-11-24 22:48:20 Updated      

蒟蒻 Rainbow-Automaton 的模板

备战

只是目前会的

然而目前啥也不会…

代码注意事项

  • 不要使用using namespace std;

  • min 和 max 都可以直接 std::min std::max 吧

  • 关同步 #define fastread std::ios_sync_with_stdio (false); std::cin.tie (nullptr);

    upd: 更为简洁的写法是 std::cin.tie(nullptr) -> sync_with_stdio(false);

  • 学习 jiangly using i64 = long long

杂项

对拍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline bool pai () {
    // Generate
    system ("gen.exe > test.in");

    // display ();

    // Run
    system ("test_1.exe < test.in > test_1.out");
    system ("test_2.exe < test.in > test_2.out");

    if (system ("fc test_1.out test_2.out")) {
        system ("pause");
        return false;
    }

    return true;
}

毫秒级随机数

通常作为对拍时的随机数生成器

1
2
3
4
5
std::mt19937 rng(std::chrono::steady_clock::now ().time_since_epoch ().count ());

inline int getRand (int l, int r) {
    return std::uniform_int_distribution<int> (l, r) (rng);
}

计时

防止 TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
inline void getTime () {
    system ("gen.exe > test.in");

    auto s = std::chrono::steady_clock::now ();
    system ("test_2.exe < test.in > test_2.out");
    auto t = std::chrono::steady_clock::now ();

    auto duration = std::chrono::duration_cast <std::chrono::microseconds> (t - s); 

    double cost = (double) duration.count () / 1000;

    std::cout << cost << "\n";
}

图论

存图

这种东西真的需要记吗

写一个神秘的封装好的图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<int maxn, int maxm>
struct Graph {
    struct Edge {
        int u, v;
        int pre;
    } es[maxm << 1];

    int last[maxn], cnt;

    Graph () { cnt = 0; memset (last, 0, sizeof (last)); }

    inline void addEdge (int u, int v) {
        es[++cnt] = Edge { u, v, last[u] };
        last[u] = cnt;
    }
};

然而我大部分时侯都不会用到封装好的图…

一般情况下只会直接写 Graph 里面的东西

最短路

Dijkstra

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
struct Node {
    int id;
    int dis;

    friend bool operator < (Node a, Node b) {
        return a.dis > b.dis; // 通过改符号的方向实现小根堆...
    }
};

std::priority_queue<Node> q;
 
int dis[maxn];
bool vis[maxn];
inline void dij (int S) {
    memset (vis, 0, sizeof (vis));
    memset (dis, 0x3f, sizeof (dis)); dis[S] = 0;
    q.push (Node { S, dis[S] });

    while (not q.empty()) {
        int now = q.top ().id; q.pop ();

        if (vis[now]) { continue; }
        vis[now] = true;

        for (int i = last[now]; i; i = es[i].pre) {
            int t = es[i].v;

            if (dis[t] > dis[now] + es[i].w) {
                dis[t] = dis[now] + es[i].w;
                q.push (Node { t, dis[t] });
            }
        }
    }
}

某个广为人所知的最短路算法

判负环

不判负环最好别用

才发现我单源最短路都是用 Dijkstra 过的

甚至找不到一个SPFA的板子

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
std::queue<int> q;
bool inq[maxn];
int times[maxn];

int dis[maxn];
inline bool spfa (int S) {
    q.push (S);
    memset (inq, 0, sizeof (inq)); inq[S] = true;
    memset (times, 0, sizeof (times)); times[S] = 0;
    for (int i = 1; i <= n + 1; i++) { if (i != S) { dis[i] = inf; } }

    while (not q.empty ()) {
        int now = q.front (); q.pop ();
        inq[now] = false;

        for (int i = last[now]; i; i = es[i].pre) {
            int t = es[i].v;

            if (dis[t] > dis[now] + es[i].w) {
                dis[t] = dis[now] + es[i].w;

                if (not inq[t]) {
                    inq[t] = true;
                    times[t] ++; if (times[t] > n + 1) { return false; } // 此处n + 1是因为多了一个超级源

                    q.push (t);
                }
            }
        }
    }

    return true;
}
差分约束

也许是唯一能用上SPFA的地方吧…

可以解出 个形如 的不等式组成的不等式组的一个解

自然也可以判断是否有解

实质就是

到 连一条长度为 的边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline void diff_constraints () { // 差分约束
    std::cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u, v, w; std::cin >> u >> v >> w;

        addEdge (v, u, w);
    }

    // 以n + 1作为超级源点
    for (int i = 1; i <= n; i++) { addEdge (n + 1, i, 0); }

    if (not spfa (n + 1)) { std::cout << "NO\n"; }
    else {
        for (int i = 1; i <= n; i++) { std::cout << dis[i] << " "; }
    }
}

Floyd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int dis[maxn][maxn];

inline void init () {
    memset (dis, 0x3f, sizeof (dis));
    for (int i = 1; i <= n; i++) { dis[i][i] = 0; }
}

inline void floyd () {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dis[i][j] = std::min (dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}

注意先 init() 再加边

倍增Floyd

实际上是矩阵快速幂

把 原来的用 表示前 个点中 到 的最短路

改为用 表示长度为 的 到 的最短路

显然

可以由 转移过来

然后我们发现转移的过程和矩阵乘法特别像

用快速幂求出 就可以得到长为 的路径条数

传递闭包

实际上就是 矩阵上的

只是求最短路改成求连通性了

1
2
3
4
5
6
7
8
9
10
11
std::bitset<maxn> a[maxn];

inline void floydClosure () {
    for (int j = 1; j <= n; j++) {
        for (int i = 1; i <= n; i++) {
            if (a[i][j]) { // i 能到 j
                a[i] |= a[j]; // 用j更新i
            }
        }
    }
}

上面的代码是用 bitset 写的, 与传统 略有不同

但是其基本思想是类似的

生成树

Kruskal

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
struct Edge {
    int u, v, w;

    friend bool operator < (Edge a, Edge b) {
        return a.w < b.w;
    }
};
std::vector<Edge> es;

inline int kruskal () {
    std::sort (es.begin (), es.end ());
    init ();

    int ans = 0;
    int tot = 0;

    for (auto e : es) {
        int u = find (e.u);
        int v = find (e.v);

        if (u == v) { continue; }

        fa[u] = v;
        ans += e.w;

        tot ++;
        if (tot == n - 1) { return ans; }
    }

    return -1;
}

其中 init() 就是并查集的 init()

并查集的写法看数据结构部分吧

欧拉回路

一定要加当前弧优化!

否则复杂度其实是假的

依然记得在mx想出正解但是欧拉回路写挂了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
std::vector<int> g[maxn];

int ind[maxn], otd[maxn];

int st[maxn];
std::vector<int> euler;
void dfs (int now, int eid) {
    for (int i = st[now]; i < g[now].size (); i = st[now]) { // g[now] 中编号一定是单增的
        st[now] = i + 1;

        int t = g[now][i];
        dfs (es[t].v, t);
    }
    euler.push_back (eid);
}

upd: 换一个更人性的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
std::vector <int> g[maxn];
int ind[maxn], otd[maxn];

std::vector <int> euler;

void dfs (int now) {
    db (now);

    while (not g[now].empty ()) {
        int t = g[now].back ();
        g[now].pop_back (); // 自带当前弧优化
        dfs (t);
    }
    euler.push_back (now);
}

upd: 判断

  • 有向图欧拉路径的判断

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    bool check () {
        int dcnt1 = 0;
        int dcnt2 = 0;
        for (int i = 1; i <= tot; i++) {
            if (ind[i] - otd[i] == 0) { continue; }

            if (ind[i] - otd[i] == 1) { dcnt1 ++; continue; }

            if (ind[i] - otd[i] == -1) { dcnt2 ++; start = i; continue; }

            return false;
        }

        if (dcnt1 > 1 or dcnt2 > 1 or dcnt1 + dcnt2 == 1) { return false; }
    }

  • 判断是否存在无向图欧拉回路 : 是否所有点入度等于出度

最后记得判断求出来的长度是否合法

Tarjan 系列

强连通分量

对于一个有向图, 一个强连通分量 是指极大的保证 存在 的路径 和 的路径的点集

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
int low[maxn], dfn[maxn], dpos;
int stk[maxn], spos;
bool ins[maxn];

int belong[maxn], scc_cnt;
std::set<int> scc[maxn];

void tarjan (int now) {
    low[now] = dfn[now] = ++dpos;
    stk[++spos] = now;
    ins[now] = true;

    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not dfn[t]) {
            tarjan (t);
            low[now] = std::min (low[now], low[t]);
        } else if (ins[t]) {
            low[now] = std::min (low[now], dfn[t]);
        }
    }

    if (low[now] == dfn[now]) {
        scc_cnt ++;
        do {
            belong[now] = scc_cnt;
            scc[scc_cnt].insert (now);
            ins[now] = false;

            now = stk[spos--];
        } while (low[now] != dfn[now]);
    }
}
2-SAT

用 到 表示 取

用 到 表示 取 

1
2
3
4
5
6
7
8
9
10
11
for (int i = 1; i <= 2 * n; i++) {
    if (not dfn[i]) { tarjan (i); }
}

if (not check ()) { std::cout << "IMPOSSIBLE" << "\n"; return 0; }

std::cout << "POSSIBLE" << "\n";
for (int i = 1; i <= n; i++) {
    if (scc[i + n] < scc[i]) { std::cout << 1 << " "; }
    else { std::cout << 0 << " "; }
}

割点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int low[maxn], dfn[maxn], dpos;
bool cut[maxn];

void tarjan (int now, int fa) {
    low[now] = dfn[now] = ++dpos;

    int sons = 0;
    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not dfn[t]) {
            tarjan (t, now);
            low[now] = std::min (low[now], low[t]);
            sons ++;
            if (low[t] >= dfn[now]) { cut[now] = true; }
        } else { // 此处可以考虑父亲
            low[now] = std::min (low[now], dfn[t]);
        }            
    }

    if (fa == 0 and sons < 2) { cut[now] = false; } 
}
点双连通分量
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
int low[maxn], dfn[maxn], dpos;
int stk[maxn], spos;

int belong[maxn], vdcc_cnt;
std::vector<int> vdcc[maxn];

void tarjan (int now, int fa) {
    low[now] = dfn[now] = ++dpos;
    stk[++spos] = now;

    int sons = 0;
    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not dfn[t]) {
            tarjan (t, now);
            low[now] = std::min (low[now], low[t]);

            sons ++;

            if (low[t] >= dfn[now]) {
                ++vdcc_cnt;

                int last = 0;
                while (last != t) {
                    int top = stk[spos--];
                    belong[top] = vdcc_cnt;
                    vdcc[vdcc_cnt].push_back (top);         
                    last = top;
                }
                vdcc[vdcc_cnt].push_back (now);
            }    
        } else {
            low[now] = std::min (low[now], dfn[t]);
        }
    }

    if (fa == 0 and sons == 0) { vdcc_cnt ++; vdcc[vdcc_cnt].push_back (now); }
}

桥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int low[maxn], dfn[maxn], dpos;
bool bridge[maxm << 1];

void tarjan (int now, int in_edge) {
    low[now] = dfn[now] = ++dpos;

    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not dfn[t]) {
            tarjan (t, i);
            low[now] = std::min (low[now], low[t]);

            if (low[t] > dfn[now]) { bridge[i] = bridge[i ^ 1] = true; }

        } else if (i != (in_edge ^ 1)) {
            low[now] = std::min (low[now], dfn[t]);
        }
    }
}

inline void init () { cnt = 1; }

因为涉及到快速找反向边, 一定要把 cnt 初始化为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
29
30
31
32
33
34
35
36
37
int low[maxn], dfn[maxn], dpos;
bool bridge[maxm << 1];

void tarjan (int now, int in_edge) {
    low[now] = dfn[now] = ++dpos;

    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not dfn[t]) {
            tarjan (t, i);
            low[now] = std::min (low[now], low[t]);

            if (low[t] > dfn[now]) { bridge[i] = bridge[i ^ 1] = true; }

        } else if (i != (in_edge ^ 1)) {
            low[now] = std::min (low[now], dfn[t]);
        }
    }
}   

int belong[maxn], edcc_cnt;
std::vector<int> edcc[maxn];

void dfs (int now) {
    belong[now] = edcc_cnt;
    edcc[edcc_cnt].push_back (now);
    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;
        if (bridge[i]) { continue; }
        if (belong[t]) { continue; }

        dfs (t);
    }
}

inline void init () { cnt = 1; }

网络流

网络流的加边方式与普通图论问题的加边方式略有不同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Edge {
   int u, v;
   int pre;
   long long flow;
} es[maxm << 1];

int last[maxn], cur[maxn], cnt = 1;
int S, T;

inline void _addEdge (int u, int v, long long cap) {
   es[++cnt] = Edge { u, v, last[u], cap };
   last[u] = cnt;
}

inline void addEdge (int u, int v, long long cap) {
   _addEdge (u, v, cap);
   _addEdge (v, u, 0);
}

Dinic

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
int dep[maxn];

bool bfs () {
    std::queue<int> q; q.push (S);
    memset (dep, 0x3f, sizeof (dep)); dep[S] = 1;

    while (not q.empty ()) {
        int now = q.front (); q.pop ();

        for (int i = last[now]; i; i = es[i].pre) {
            int t = es[i].v;
            if (not es[i].flow) { continue; }
            if (dep[t] != 0x3f3f3f3f) { continue; }

            dep[t] = dep[now] + 1;
            q.push (t);
        }
    }

    return dep[T] != 0x3f3f3f3f;
}

long long dfs (int now, long long now_flow) {
    if (now == T or not now_flow) { return now_flow; }

    long long res = 0;
    for (int &i = cur[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not es[i].flow) { continue; }
        if (dep[t] != dep[now] + 1) { continue; }

        long long t_flow = dfs (t, std::min (now_flow, es[i].flow));

        if (t_flow) {
            es[i].flow -= t_flow;
            es[i ^ 1].flow += t_flow;
            now_flow -= t_flow;
            res += t_flow;

            if (not now_flow) { return res; }
        }
    }

    return res;
}

inline long long Dinic (int _s, int _t) {
    S = _s, T = _t;
    long long res = 0;
    while (bfs ()) {
        memcpy (cur, last, sizeof (last));
        res += dfs (S, 0x3f3f3f3f);
    }
    return res;
}

网络单纯形

把之前写的代码粘过来了

码风可能有点不太一样

而且好像使用 实现会更容易一些…

然而我学网络单纯形的时候并不会lct

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
const long long inf = 1e9;

namespace NetworkSimplex {
    struct Edge {
        int u, v;
        int pre;
        int flow;
        int cost;
    } es[maxm];

    int last[maxn], cnt = 1;

    inline void _addEdge (int u, int v, int cap, int cost) {
        es[++cnt] = Edge { u, v, last[u], cap, cost };
        last[u] = cnt;
    }

    inline void addEdge (int u, int v, int cap, int cost) {
        _addEdge (u, v, cap, cost);
        _addEdge (v, u, 0, -cost);
    }

    int fa[maxn], faEdge[maxn]; // fa[u] : u的父亲 | faEdge[u] : 父亲指向u的边
    int mark[maxn], curTime = 1; // mark[u] : 节点u的时间戳 | curTime : 当前时间

    // 先找出基解 (随便找一棵生成树)
    // 此时mark的作用是标记是否访问过
    void initTree (int now) {
        for (int i = last[now]; i; i = es[i].pre) {
            int t = es[i].v;

            if (not es[i].flow) { continue; }

            if (mark[t]) { continue; }
            mark[t] = 1;

            fa[t] = now;
            faEdge[t] = i;

            initTree (t);
        }
    }

    int piCache[maxn]; // 缓存一下pi优化
    int pi (int now) { // 当前节点到根节点的代价和
        if (mark[now] == curTime) { return piCache[now]; } // 当前节点的时间戳是当前时间 (piCache里的东西没有过时), 直接返回
        mark[now] = curTime; // 当前点经过更新已经是最新的了
        return piCache[now] = es[faEdge[now]].cost + pi(fa[now]); // 当前点的pi是从根节点到父亲的代价 + 父亲到当前点的代价
    }

    inline long long pushFlow (int eid) { // 沿着给定非树边的编号eid形成的环推流
        ++curTime; // 时间戳增加

        // 找根
        int root = es[eid].u;
        while (root) { mark[root] = curTime; root = fa[root]; } // 向上跳并在跳的路径上打标记

        // 找lca
        int lca = es[eid].v;
        while (mark[lca] != curTime) { mark[lca] = curTime; lca = fa[lca]; } // 向上跳, 一直跳到被标记过 (也就是说要跳到在u到根的路径上),, 显然第一个跳到的点是lca

        // 找出基的边 (流量最小的边)

        int minFlow = es[eid].flow; // 能流的流量 (最小的流量)
        int delNode = 0; // 被删去的边的对应点
        int flag = 2; // flag = 2 : 没找到 (当前边就是) | 0 : 在lca到u的路径上 | 1 : 在v到lca的路径上
        std::vector <int> circle; // 存环上的边

        // 从u向上找lca往u方向的流量最小的边
        for (int now = es[eid].u; now != lca; now = fa[now]) {
            int nowEdge = faEdge[now]; // 因为是lca往u方向流所以是u的父亲到u的边
            circle.push_back (nowEdge);

            if (minFlow > es[nowEdge].flow) {
                minFlow = es[nowEdge].flow;
                flag = 0;
                delNode = now;
            }
        }

        // 从v想上找v往lca方向的流量最小的边
        for (int now = es[eid].v; now != lca; now = fa[now]) {
            int nowEdge = faEdge[now] ^ 1; // 因为是v往lca方向流所以是v到父亲的边
            circle.push_back (nowEdge);

            if (minFlow > es[nowEdge].flow) {
                minFlow = es[nowEdge].flow;
                flag = 1;
                delNode = now;
            }
        }

        circle.push_back (eid);

        // 给环上每个边增加流量并统计费用
        long long cost = 0;
        for (auto now : circle) {
            es[now].flow -= minFlow;
            es[now ^ 1].flow += minFlow;
            cost += minFlow * es[now].cost;
        }

        if (flag == 2) { return cost; } // 最小边是当前边, 不许要改变树的结构

        // 改变树的结构 (加入入基边, 删除出基边)
        // 实际上就是翻转树的结构 (此处我们直接暴力翻转)

        // 如果最小边是在lca到u的路径上, 我们实际上要对v->u->delNode的路径进行更新; 
        // 如果最小边是在v到lca的路径上, 我们实际上要对u->v->delNode的路径进行更新
        // 这里有一个trick
        // 我们发现, 在第一种情况里的u->delNode和第二种情况里v->delNode的路径中, 我们原有的faEdge[x]都是从我们要跳到的点, 指向当前点x
        // 如果我们能统一边的方向(从我们要跳到的点指向当前点), 翻转整条链的操作就会变得非常好处理
        // 然后我们又发现
        // 第一种情况里u->v的这条边恰好满足从我们要跳到的点u到我们当前的点v这一条件
        // 第二种情况正好相反
        // 所以第二种情况下, 我们先对我们要加入的这条边u->v翻转一下, 取他的反向边v->u
        // 这样就可以统一处理了

        eid = eid ^ flag; // 所以我们直接异或上flag (如果在lca到u的路径上, flag就等于0, 异或上0等于没有异或)
        int u = es[eid].u;
        int v = es[eid].v;

        int lastNode = v; // 上一个操作的点
        int lastEdge = eid; // 上一个边
        int nextNode = 0; // 下一个点
        for (int now = u; lastNode != delNode; now = nextNode) {
            nextNode = fa[now];
            mark[now] --; // 信息过期, 时间戳--

            lastEdge ^= 1; // 将上一条边翻转
            swap (lastEdge, faEdge[now]);

            fa[now] = lastNode;
            lastNode = now;        
        }

        return cost;
    }

    struct MCMF {
        int minCost, maxFlow;
    };

    inline MCMF simplex (int S, int T) {
        addEdge (T, S, inf, -inf); // 加这条辅助边保证最大流

        initTree (T); // 寻找基解
        mark[T] = ++curTime;
        fa[T] = 0; // 钦定T是根

        long long cost = 0; // 由于一开始加了一条费用为-inf的边, 费用可能很大, 最好开long long
        while (true) {
            bool flag = false;
            for (int i = 2; i <= cnt; i++) {
                if (es[i].flow and es[i].cost + pi(es[i].u) - pi(es[i].v) < 0) { // 寻找可以形成负环的边
                    flag = true;
                    cost += pushFlow (i);
                }
            }

            if (not flag) { break; } // 没有找到可以形成负环推流的边, 停止
        }

        // 最后加上的边反向边 (S -> T) 的flow就是我们的最大流
        // (因为我们这条边加的意义是使得任意S到T的流都可以与它形成负环, 所以每次推流的时候都会把增加的流量加到它上面去)
        int maxFlow = es[cnt].flow; 
        int minCost = int ((long long) es[cnt].flow * inf + cost); // 需要加上 es[cnt].flow * inf 抵消掉一开始那条边的费用  
        return MCMF { minCost, maxFlow };
    }

    inline void clear () {
        memset (mark, 0, sizeof(mark)); curTime = 1;
        memset (piCache, 0, sizeof(piCache));
        memset (last, 0, sizeof(last)); cnt = 1;
    }
}

字符串

啥也不会

前缀函数

1
2
3
4
5
6
7
8
9
10
11
12
inline std::vector<int> get_pi(const std::string &s) {
    std::vector<int> pi(s.length());

    rep (i, 2, (int) s.length() - 1) {
        int j = pi[i - 1];
        while (j and s[j + 1] != s[i]) j = pi[j];
        if (s[j + 1] == s[i]) j++;
        pi[i] = j;
    }

    return pi;
}

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
template <int maxn>
struct ACAM {
    struct Node {
        int ch[26];
        int fail;
    } tr[maxn];

    int rt, tot;

    inline void init() { rt = tot = 1; std::memset(tr, 0, sizeof tr); }

    ACAM() { init(); }

    inline int ins(const std::string &s) {
        int now = rt;
        for (auto c : s) {
            int &t = tr[now].ch[c - 'a'];
            if (not t) t = ++tot;
            now = t;
        }
        return now;
    }

    inline void build() {
        for (auto &t : tr[0].ch) t = rt;
        std::queue<int> q;
        q.push(rt);

        while (not q.empty()) {
            int now = q.front(); q.pop();

            for (int i = 0; i < 26; i++) {
                int &t = tr[now].ch[i];
                int f = tr[tr[now].fail].ch[i];

                if (not t) t = f;
                else {
                    tr[t].fail = f;
                    q.push(t);
                }
            }
        }
    }
};

后缀自动机

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
struct SAM {
    struct Node {
        int ch[26];
        int fa;
        int len;
    } ns[maxn];

    int last, root, tot;

    // 附加信息
    i64 cnt[maxn];

    SAM () { last = root = tot = 1; memset (cnt, 0, sizeof (cnt)); }

    inline void add (int c) {
        int p = last;
        int np = last = ++tot;

        ns[np].len = ns[p].len + 1;
        cnt[np] = 1;

        for (; p and not ns[p].ch[c]; p = ns[p].fa) { ns[p].ch[c] = np; }

        if (not p) { ns[np].fa = root; }
        else {
            int q = ns[p].ch[c];

            if (ns[q].len == ns[p].len + 1) { ns[np].fa = q; }
            else {
                int nq = ++tot;
                ns[nq] = ns[q]; ns[nq].len = ns[p].len + 1;
                ns[q].fa = ns[np].fa = nq;

                for (; p and ns[p].ch[c] == q; p = ns[p].fa) { ns[p].ch[c] = nq; }
            }
        }
    }    

    inline void getParentTree (Graph& tr) {
        for (int i = 2; i <= tot; i++) { tr.addEdge (ns[i].fa, i); }
    }
};

Manacher

1
2
3
4
5
6
7
8
f[1] = 1;
std::pair<int, int> cur = { 1, 1 };

rep (i, 2, n) {
    f[i] = std::min(f[2 * cur.second - i], cur.first - i + 1);
    while (i - f[i] >= 1 and i + f[i] <= n and s[i + f[i]] == s[i - f[i]]) f[i]++;
    cur = std::max(cur, {i + f[i] - 1, i});
}

回文自动机

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
namespace Palindrome_Automaton {
    struct Node {
        int len, cnt;
        int next[26];
        int fail;
    };
    Node pam[maxn];

    int cnt, last;

    inline void init () {
        cnt = 1, last = 0; // 奇根的前一个是偶根
        pam[0].len = 0;
        pam[1].len = -1; // 两边同时加入一个
        pam[0].fail = 1; // 奇根不会有fail 
    }

    // decrypt (x) 只是为了满足模板题里面的强制在线而已
    #define decrypt(x) (s[i] + pam[last].cnt - 97) % 26 + 97

    #define get_fail(x) while (s[i] != s[i - pam[x].len - 1]) { x = pam[x].fail; }

    inline std::vector<int> solve (string s) {
        std::vector<int> res;

        for (int i = 0; i < s.size(); i++) {
            if (i >= 1) { s[i] = decrypt(i); }

            int a = last; get_fail(a);

            if (not pam[a].next[s[i] - 'a']) { // 没有就新建节点
                int b = pam[a].fail; get_fail(b);

                cnt ++;
                pam[cnt].fail = pam[b].next[s[i] - 'a'];
                pam[cnt].cnt = pam[pam[cnt].fail].cnt + 1;
                pam[cnt].len = pam[a].len + 2;
                pam[a].next[s[i] - 'a'] = cnt;
            }

            last = pam[a].next[s[i] - 'a'];

            res.push_back(pam[last].cnt);
        }
        
        return res;
    }
}

数学

预处理约数

才发现先前对每个数分别处理约数的做法这么唐。

考虑贡献即可。

1
2
rep (d, 1, n) 
for (int t = d; t <= n; t += d) ds[t].push_back(d);

预处理质因数

其实是埃氏筛。

1
2
3
4
5
6
7
8

std::vector<int> pfac[maxn];
inline void sieve(int N) {
	rep (i, 2, n) {
		if (not pfac[i].empty()) continue;
		for (int j = i; j <= N; j += i) pfac[j].push_back(i);
	}
}

Miller-Rabin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inline bool test(i64 a, i64 p) {
	if (ksm(a, p - 1, p) != 1) return false;
	i64 x = p - 1;
	while (x % 2 == 0) {
		i64 v = ksm(a, x / 2, p);
		if (v == p - 1) return true;
		if (v != 1) return false;		
		x /= 2;
	}
	return true;
}

inline bool MillerRabin(i64 p) {
	rep (k, 0, 9) if (not test(ps[k], p)) return false;
	return true;
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
i64 ksm (i64 a, i64 b, i64 mod) {
    i64 res = 1;
    i64 base = a;

    while (b) {
        if (b & 1) { (res *= base) %= mod; }
        (base *= base) %= mod;
        b >>= 1;
    }    

    return res;
}

欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
13
i64 phi (i64 n) {
    i64 ans = n;
    for (i64 p = 2; p * p <= n; p++) {
        if (n % p != 0) { continue; }

        ans = ans / p * (p - 1);
        while (n % p == 0) { n /= p; }
    }

    if (n > 1) { ans = ans / n * (n - 1); }

    return ans;
}

逆元

这里使用欧拉函数求逆元

不会写exgcd导致的

你说的对, 但是

所以我们可以直接求逆元

1
2
3
i64 inv (i64 a, i64 b) {
    return Ksm::ksm (a, phi (b) - 1, b);
}

exgcd

1
2
3
4
5
6
i64 exgcd (i64 a, i64 b, i64 &x, i64 &y) {
    if (b == 0) { x = 1, y = 0; return a; }
    i64 d = exgcd (b, a % b, y, x);
    y -= x * (a / b);
    return d;
}

于是, 上面的逆元也可以用exgcd求

因为

所以我们很容易用exgcd求出 

1
2
3
4
inline i64 inv (i64 a, i64 b) {
    i64 x, y; exgcd (a, b, x, y);
    return (x + b) % b;       
}

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
std::bitset<maxn> not_prime;
std::vector<int> primes;

inline void get_primes () {
    not_prime.reset ();
    not_prime[1] = true;

    for (int i = 2; i <= n; i++) {
        if (not not_prime[i]) { primes.push_back (i); }

        for (auto p : primes) {
            if (i * p > n) { break; }
            not_prime[i * p] = true;
            if (i % p == 0) { break; }
        }
    }
}

筛莫比乌斯函数

用线性筛筛出莫比乌斯函数

顺便求出前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline void get_mu () {
    not_prime.reset ();
    int n = maxn - 5;

    mu[1] = 1;
    not_prime[1] = true;

    for (int i = 2; i <= n; i++) {
        if (not not_prime[i]) { primes.push_back (i); mu[i] = -1; }

        for (auto p : primes) {
            if (i * p > n) { break; }
            not_prime[i * p] = true;
            mu[i * p] = -1 * mu[i];

            if (i % p == 0) { mu[i * p] = 0; break; }
        }
    }

    for (int i = 1; i <= n; i++) { sum[i] = sum[i - 1] + mu[i]; }
}

中国剩余定理

只会大数翻倍法

所以这其实是假的中国剩余定理

orz钟神太强了%%%

1
2
3
4
5
6
7
8
9
inline bool merge (i64 &m1, i64 &a1, i64 m2, i64 a2) {
    if (m1 < m2) { std::swap (m1, m2); std::swap (a1, a2); }           

    while (a1 % m2 != a2) { a1 += m1; }

    m1 = lcm (m1, m2);

    return true;
}

真的超级好写啊啊啊

upd: 判无解版本:

1
2
3
4
5
6
7
8
9
10
inline bool merge (i64& m1, i64& a1, i64 m2, i64 a2) {
    if (m1 < m2) { std::swap (m1, m2); std::swap (a1, a2); }
    int tot = 0;
    while (a1 % m2 != a2) { 
        if (++tot > m2 + 1) { return false; } 
        a1 += m1; 
    }
    m1 = lcm (m1, m2);
    return true;
}

扩展中国剩余定理

不用害怕, zhx的大数翻倍法本身就能合并两个同余方程

所以合并部分代码跟上面一样。

蓝的盆。我先前咋这么唐。

其实是平凡的。

骗小朋友的代数 trick 罢了。

1
2
3
4
5
6
7
8
9
using Equation = std::pair<i64, i64>;

Equation mrg(Equation a, Equation b) {
	i64 k0, _; i64 g = exgcd(a.second, b.second, k0, _);
	i64 m = a.second / g * b.second;
	if ((b.first - a.first) % g) return Equation { -1, 0 };
	(k0 *= (b.first - a.first) / g) %= m;
	return Equation { ((a.second * k0 % m + a.first % m) % m + m) % m, m };
}

高维前缀和

1
2
3
4
5
for (int i = 0; i < 22; i++) {
    for (int S = 0; S < (1 << 22); S++) {
        if (S & (1 << i)) { sum[S] = sum[S] + sum[S ^ (1 << i)]; }
    }
}

异或线性基

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Basis {
    u64 b[63];

    inline bool ins(u64 x) {
        per (i, 60, 0) {
            if (x & (1ull << i)) {
                if (not b[i]) return (b[i] = x), true;
                else x ^= b[i];
            }
        }
        return false;
    }

    inline u64 mx(u64 x) {
        per (i, 60, 0) x = std::max(x, x ^ b[i]);
        return x;
    }
} basis;

模意义下线性基

1
2
3
4
5
6
7
8
9
10
11
inline bool ins(Vector a) {
	rep (i, 1, m) {
		if (not a[i]) continue;
		if (not b[i][i]) return b[i] = a, true;

		i64 c = a[i] * inv(b[i][i]) % mod;
		rep (j, i, m) (((a[j] -= c * b[i][j] % mod) %= mod) += mod) %= mod;
	}

	return false;
}

高斯消元

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
f64 a[maxn][maxn];

const f64 eps = 1e-10;
inline int gauss() {
    int rnkA = 0; // 系数矩阵的秩
    rep (i, 1, n) {
        int t = rnkA + 1;
        rep (j, rnkA + 1, n) {
            if (std::fabs(a[j][i]) > std::fabs(a[t][i])) t = j; 
        }

        if (std::fabs(a[t][i]) < eps) continue;
        rnkA++;
        std::swap(a[rnkA], a[t]);

        per (j, n + 1, i) a[rnkA][j] /= a[rnkA][i];

        rep (j, rnkA + 1, n) {
            per (k, n + 1, i) a[j][k] -= a[rnkA][k] * a[j][i];
        }
    }
    if (rnkA == n) {
        per (i, n - 1, 1) rep (j, i + 1, n) a[i][n + 1] -= a[i][j] * a[j][n + 1];
        return -1; // 有唯一解
    } else {
        rep (i, rnkA + 1, n) if (std::fabs(a[i][n + 1]) > eps) return 0; // 无解
        return 1; // 无穷多解
    }
}

多项式

NTT

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
namespace NTT {
	const i64 g = 3, mod = 998244353;

	const int maxb = 21;
	const int maxn = 1 << maxb;
	i64 cache[maxn << 1], *pw = cache + maxn;
	inline void init() {
		i64 v = ksm(g, (mod - 1) / maxn);
		pw[0] = pw[0 - maxn] = 1;
		rep (i, 1, maxn - 1) pw[i] = pw[i - maxn] = pw[i - 1] * v % mod;
	}

	inline void DFT(std::vector<i64> &a, int c) {
		int len = a.size();

		std::vector<i64> org = a;
		rep (i, 0, len - 1) {
			int pos = 0;
			rep (b, 0, maxb - 1) if (i & (1 << b)) pos += (len >> (b + 1));
			a[pos] = org[i];
		}

		for (int h = 2; h <= len; h <<= 1) {
			for (int i = 0; i < len; i += h) {
				for (int j = i; j < i + (h >> 1); j++) {
					i64 u = a[j] % mod;
					i64 v = a[j + (h >> 1)] % mod * pw[(maxn / h) * c * (j - i)] % mod;
					a[j] = (u + v >= mod ? u + v - mod : u + v); 
					a[j + (h >> 1)] = (u - v < 0 ? u - v + mod : u - v);
				}
			}
		}

		if (c == -1) {
			i64 inv_n = inv(len);
			rep (i, 0, len - 1) (a[i] *= inv_n) %= mod;
		}
	}

	inline std::vector<i64> mul(std::vector<i64> a, std::vector<i64> b) {
		int len = 1;
		while (len < a.size() + b.size()) len <<= 1;
		a.resize(len); b.resize(len);

		DFT(a, 1);
		DFT(b, 1);

		std::vector<i64> c(len);
		rep (i, 0, len - 1) c[i] = a[i] * b[i] % mod;
		
		DFT(c, -1);
		return c;
	}
}

Stern–Brocot 树

1
2
3
4
5
6
7
8
9
10
11
void dfs(f64 X, int a, int b, int c, int d) {
	int x = a + c, y = b + d;
	if (x > n or y > m) return;

	decltype(ans) cur = { std::abs(((f64) 1.0 * x / y) - X), { x, y }};	
	nxt = std::min(nxt, cur);
	if (nxt < ans) std::swap(nxt, ans);

	if (X < ((f64) 1.0 * x / y)) dfs(X, a, b, x, y);
	else dfs(X, x, y, c, d);
}

Prufer 序列

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
namespace Decoder {
	int pi[maxn];
	int deg[maxn];
	int fa[maxn];

	inline void solve() {
		rep (i, 1, n - 2) std::cin >> pi[i];
		
		rep (i, 1, n) deg[i] = 1;
		rep (i, 1, n - 2) deg[pi[i]]++;
		pi[n - 1] = n;

		int p = 1;
		rep (i, 1, n - 1) {
			while (deg[p] > 1) p++;
			fa[p] = pi[i];
			while (i < n and (--deg[pi[i]]) == 1 and pi[i] < p) {
				fa[pi[i]] = pi[i + 1]; i++;
			}
			p++;
		}

		i64 res = 0;
		rep (i, 1, n - 1) res ^= 1ll * i * fa[i];
		std::cout << res << "\n";
	}
}

namespace Encoder {
	int fa[maxn];
	int pi[maxn];
	int deg[maxn];

	inline void solve() {
		rep (i, 1, n - 1) std::cin >> fa[i];
		rep (i, 1, n - 1) deg[i] = 1;
		rep (i, 1, n) deg[fa[i]]++;
		
		int p = 1;
		rep (i, 1, n - 2) {
			while (deg[p] > 1) p++;
			pi[i] = fa[p]; 
			while (i < n - 1 and (--deg[pi[i]]) == 1 and pi[i] < p) {
				pi[i + 1] = fa[pi[i]]; i++;
			}
			p++;
		}
		
		i64 res = 0;
		rep (i, 1, n - 2) res ^= (1ll * i * pi[i]);
		std::cout << res << "\n";
	}
}

数据结构

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <int maxn>
struct UnionFindSet {
    int fa[maxn];  

    inline void init () {
        for (int i = 1; i <= n; i++) { fa[i] = i; }
    }

    int find (int x) {
        if (fa[x] == x) { return fa[x]; }
        else { return fa[x] = find (fa[x]); }
    }

    inline void merge (int x, int y) {
        fa[find (y)] = find (x);
    }

    inline bool same (int x, int y) {
        return find (x) == find(y);
    }
};

树状数组

1
2
3
4
5
6
7
8
9
10
11
template <int maxsiz>
struct BIT {
    int tr[maxsiz];

    inline int lowbit (int x) { return x & (-x); }

    inline void add (int pos, int val) { for (int i = pos; i <= n; i += lowbit(i)) { tr[i] += val; } }
    inline int _query (int pos) { int res = 0;for (int i = pos; i; i -= lowbit(i)) { res += tr[i]; } return res; }

    inline int query (int l, int r) { return _query (r) - _query (l - 1); }
};

上面只给出了单点加区间求和的版本

实际上, 树状数组还可以通过神秘的技术实现区间加单点查和 区间加区间求和

甚至可以通过跳 lowbit 实现 区间最值查询

然而实现十分复杂, 失去了树状数组本身简洁的优势

而且复杂度好像也不是很对 (曾被hzhl狠狠质疑)

所以不如写线段树 👇

线段树

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
template <int maxn, typename val_t>
struct SegmentTree {
    struct Node {
        val_t sum;
        val_t tag; bool cov;
    } tr[maxn << 2];

    inline void pushUp (int now) {
        tr[now].sum = tr[now << 1].sum + tr[now << 1 | 1].sum;
    }

    inline void update (int now, int l, int r, val_t val) {
        tr[now].sum += val * (r - l + 1);
        tr[now].tag += val;
        tr[now].cov = true;
    }

    inline void pushDown (int now, int l, int r) {
        if (not tr[now].cov) { return; }
        int mid = (l + r) >> 1;
        update (now << 1, l, mid, tr[now].tag);
        update (now << 1 | 1, mid + 1, r, tr[now].tag);
        tr[now].tag = 0; tr[now].cov = false;
    }

    void build (int now, int l, int r) {
        if (l == r) {
            tr[now] = Node { a[l], 0, false };
            return;
        }

        int mid = (l + r) >> 1;
        build (now << 1, l, mid);
        build (now << 1 | 1, mid + 1, r);

        pushUp (now);
    }

    void modify (int now, int l, int r, int L, int R, val_t val) {
        if (L <= l and r <= R) { update (now, l, r, val); return; } 

        pushDown (now, l, r);
        int mid = (l + r) >> 1;
        if (L <= mid) { modify (now << 1, l, mid, L, R, val); }
        if (R > mid) { modify (now << 1 | 1, mid + 1, r, L, R, val); }
        pushUp (now);   
    }

    val_t query (int now, int l, int r, int L, int R) {
        if (L <= l and r <= R) { return tr[now].sum; }

        pushDown (now, l, r);
        int mid = (l + r) >> 1;
        val_t res = 0;
        if (L <= mid) { res += query (now << 1, l, mid, L, R); }
        if (R > mid) { res += query (now << 1 | 1, mid + 1, r, L, R); }

        return res;
    }
};

使用的时候, 只需要 SegmentTree<maxn, i64> tr 就行

+*标记

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
using tag = std::pair<i64, i64>;
constexpr tag z = { 1, 0 };

int n, q, m;

int a[maxn];

struct Node {
	i64 sum;
	tag t;
} tr[maxn << 2];

inline void compose(tag &cur, tag t) {
	(cur.first *= t.first) %= mod;
	(((cur.second *= t.first) %= mod) += t.second) %= mod;
}

inline void apply(int now, int l, int r, tag t) {
	(tr[now].sum *= t.first) %= mod;
	(tr[now].sum += 1ll * t.second * (r - l + 1) % mod) %= mod;
	compose(tr[now].t, t);
}

inline void pushdown(int now, int l, int r) {
	int mid = (l + r) >> 1;
	apply(now << 1, l, mid, tr[now].t);
	apply(now << 1 | 1, mid + 1, r, tr[now].t);
	tr[now].t = z;
}

inline void pushup(int now) {
	tr[now].sum = (tr[now << 1].sum + tr[now << 1 | 1].sum) % mod;
}

void build(int now, int l, int r) {
	if (l == r) {
		tr[now] = Node { a[l], z };
		return;
	}
	int mid = (l + r) >> 1;
	build(now << 1, l, mid);
	build(now << 1 | 1, mid + 1, r);
	pushup(now);
	tr[now].t = z;
}

void mdf(int now, int l, int r, int L, int R, tag t) {
	if (L <= l and r <= R) return apply(now, l, r, t), void(0);

	pushdown(now, l, r);

	int mid = (l + r) >> 1;
	if (L <= mid) mdf(now << 1, l, mid, L, R, t);
	if (R > mid) mdf(now << 1 | 1, mid + 1, r, L, R, t);
	
	pushup(now);
}

int qry(int now, int l, int r, int L, int R) {
	if (L <= l and r <= R) return tr[now].sum;

	pushdown(now, l, r);

	int mid = (l + r) >> 1;
	if (R <= mid) return qry(now << 1, l, mid, L, R);
	if (L > mid) return qry(now << 1 | 1, mid + 1, r, L, R);

	return (qry(now << 1, l, mid, L, R) + qry(now << 1 | 1, mid + 1, r, L, R)) % mod;
}

权值线段树

其实是动态开点线段树

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
template <int maxn, typename val_t>
struct SegmentTree {
    struct Node {
        int lson, rson;
        val_t sum;
    } tr[(maxn << 4) + 5];

    int root;

    int tot;
    SegmentTree () { tot = 0; }

    inline void pushUp (int now) { tr[now].sum = tr[tr[now].lson].sum + tr[tr[now].rson].sum; }

    void modify (int &now, val_t l, val_t r, val_t pos, val_t val) {
        if (not now) { now = ++tot; }
        if (l == r) { tr[now].sum += val; return; }

        val_t mid = (l + r) >> 1;
        if (pos <= mid) { modify (tr[now].lson, l, mid, pos, val); }
        if (pos > mid) { modify (tr[now].rson, mid + 1, r, pos, val); }

        pushUp (now);
    }

    val_t query (int now, val_t l, val_t r, val_t L, val_t R) {
        if (not now) { return 0; }
        if (L <= l and r <= R) { return tr[now].sum; }

        val_t mid = (l + r) >> 1;
        val_t res = 0;
        if (L <= mid) { res += query (tr[now].lson, l, mid, L, R); }
        if (R > mid) { res += query (tr[now].rson, mid + 1, r, L, R); }
        return res;
     }
};

可持久化线段树

可持久化数组
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
template <int maxn, typename val_t>
struct PresistentArray {
    struct Node {
        int ls, rs;
        val_t val;
    } tr[maxn << 5];

    int tot, root[maxn];
    inline int newNode (Node old = Node { 0, 0, 0 }) { tr[++tot] = old; return tot; }

    void build (int &now, int l, int r) {
        now = newNode ();
        if (l == r) { tr[now].val = a[l]; return; }

        int mid = (l + r) >> 1;
        build (tr[now].ls, l, mid);
        build (tr[now].rs, mid + 1, r);
    }

    void modify (int &now, int old, int l, int r, int pos, val_t val) {
        now = newNode (tr[old]);
        if (l == r) { tr[now].val = val; return; }

        int mid = (l + r) >> 1;
        if (pos <= mid) { modify (tr[now].ls, tr[old].ls, l, mid, pos, val); }
        if (pos > mid) { modify (tr[now].rs, tr[old].rs, mid + 1, r, pos, val); }
    }

    val_t query (int now, int l, int r, int pos) {
        if (not now) { return 0; }
        if (l == r) { return tr[now].val; }

        int mid = (l + r) >> 1;
        if (pos <= mid) { return query (tr[now].ls, l, mid, pos); }
        if (pos > mid) { return query (tr[now].rs, mid + 1, r, pos); }
        return 0;
    }
};

01-trie

普通 01-trie

其实就是普通 01-trie

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
struct Trie {
    i64 tr[maxn << 5][2];
    int tot;
    int siz[maxn << 5];

    void insert (i64 val) {
        int now = 0;
        for (int i = 31; i >= 0; i--) {
            bool x = ((val >> i) & 1);
            if (not tr[now][x]) { tr[now][x] = ++tot; }
            now = tr[now][x];
            siz[now]++;
        }
    }

    void del (i64 val) {
        int now = 0;
        for (int i = 31; i >= 0; i--) {
            bool x = ((val >> i) & 1);
            now = tr[now][x];
            siz[now]--;
        }
    }

    i64 query (i64 val) { // 使得结果尽可能小
        int now = 0;
        i64 ans = 0;

        for (int i = 31; i >= 0; i--) {
            bool x = ((val >> i) & 1);
            if (not siz[tr[now][x]]) { ans |= (1ll << i); now = tr[now][x ^ 1]; }
            else { now = tr[now][x]; }
        }

        return ans;
    }
} trie;

查询 k 大 01-trie

与平衡树 / 值域线段树很像

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
struct Trie {
    int tr[maxn << 5][2], tot, root;

    int siz[maxn << 5];

    Trie () { tot = 0; root = ++tot; }

    inline void insert (i64 val) {
        int now = root; siz[now] ++;
        for (i64 i = 31; i >= 0; i--) {
            bool x = ((val >> i) & 1ll);

            if (not tr[now][x]) { tr[now][x] = ++tot; }
            now = tr[now][x];

            siz[now] ++;
        }
    }

    inline i64 query (i64 val, int rnk) {
        i64 res = 0;

        int now = root;
        for (i64 i = 31; i >= 0; i--) {
            bool x = ((val >> i) & 1ll);

            if (not tr[now][x ^ 1]) { now = tr[now][x]; continue; }

            if (rnk <= siz[tr[now][x ^ 1]]) {
                res |= 1ll << i;
                now = tr[now][x ^ 1];
            } else {
                rnk -= siz[tr[now][x ^ 1]];
                now = tr[now][x];
            }
        }

        return res;
    }
} trie;

可持久化 01-trie

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
struct Trie {
    int tr[maxn << 6][2];
    int tot;
    int siz[maxn << 6];

    int rt[maxn];

    inline void clear () {
        for (int i = 1; i <= tot; i++) { tr[i][0] = tr[i][1] = 0; siz[i] = 0; } 
        tot = 0; 
    }

    inline void insert (int now, int old, int val) {
        for (int i = 31; i >= 0; i--) {
            bool x = ((val >> i) & 1);    

            tr[now][x] = ++tot; tr[now][x ^ 1] = tr[old][x ^ 1];  // clone

            now = tr[now][x]; old = tr[old][x];

            siz[now] = siz[old] + 1;
        }
    }

    inline int query (int now, int old, int val) {
        int ans = 0;
        for (int i = 31; i >= 0; i--) {
            bool x = ((val >> i) & 1);

            if (siz[tr[now][x ^ 1]] - siz[tr[old][x ^ 1]] > 0) {
                ans |= (1 << i);
                now = tr[now][x ^ 1]; old = tr[old][x ^ 1];
            } else {
                now = tr[now][x]; old = tr[old][x];
            }
        }

        return ans;
    }
} trie;

平衡树

FHQ-Treap

普通平衡树
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
template <int maxn, typename val_t>
struct FhqTreap {
    struct Node {
        int ls, rs;
        val_t val;
        unsigned long long key;
        int size;
    } tr[maxn];

    std::mt19937 rnd;

    int tot, root;
    inline int newNode (int val) {
        tr[++tot] = Node { 0, 0, val, rnd (), 1 };
        return tot;
    }

    inline void update (int now) { tr[now].size = tr[tr[now].ls].size + tr[tr[now].rs].size + 1; }

    FhqTreap () { tot = 0; }

    void split (int now, val_t val, int &x, int &y) {
        if (not now) {
            x = 0; y = 0;
        } else if (tr[now].val <= val) {
            x = now; split (tr[now].rs, val, tr[now].rs, y);
            update (x);
        } else {
            y = now; split (tr[now].ls, val, x, tr[now].ls);
            update (y);
        }
    }

    int merge (int x, int y) {
        if (not x or not y) {
            return x | y;
        } else if (tr[x].key < tr[y].key) {
            tr[x].rs = merge (tr[x].rs, y);
            update (x);
            return x;
        } else {
            tr[y].ls = merge (x, tr[y].ls);
            update (y);
            return y;
        }
    }

    inline void insert (val_t val) {
        int x, y; split (root, val, x, y);
        root = merge (merge (x, newNode (val)), y);
    }

    inline void remove (val_t val) {
        int x, y, z;
        split (root, val, x, y);
        split (x, val - 1, x, z);
        z = merge (tr[z].ls, tr[z].rs);
        root = merge (merge (x, z), y);
    }

    inline val_t pre (val_t val) {
        int x, y; split (root, val - 1, x, y);

        int now = x;
        while (tr[now].rs) { now = tr[now].rs; }

        root = merge (x, y);
        return tr[now].val;
    }

    inline val_t nxt (val_t val) {
        int x, y; split (root, val, x, y);

        int now = y;
        while (tr[now].ls) { now = tr[now].ls; }

        root = merge (x, y);
        return tr[now].val;
    }

    inline int get_rank (val_t val) {
        int x, y; split (root, val - 1, x, y);
        int rank = tr[x].size + 1;
        root = merge (x, y);
        return rank;
    }

    inline val_t get_val (int rank) {
        int now = root;
        while (true) {
            if (tr[tr[now].ls].size + 1 == rank) { return tr[now].val; }
            else if (tr[tr[now].ls].size >= rank) { now = tr[now].ls; }
            else { rank -= tr[tr[now].ls].size + 1; now = tr[now].rs; }
        }
        return -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
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
struct Node {
    int val;
    int ls, rs;
    int siz;
    bool tag;

    i64 key;
} tr[maxn];

int root, tot;

std::mt19937 rnd (std::chrono::steady_clock::now ().time_since_epoch ().count ());

inline int newNode (int val) {
    tr[++tot] = Node { val, 0, 0, 1, false, rnd () };
    return tot;
}

inline void pushUp (int now) {
    tr[now].siz = tr[tr[now].ls].siz + tr[tr[now].rs].siz + 1;
}

inline void pushDown (int now) {
    if (tr[now].tag) {
        std::swap (tr[now].ls, tr[now].rs);
        tr[tr[now].ls].tag ^= 1; tr[tr[now].rs].tag ^= 1;
        tr[now].tag = false;
    }
}

void split (int now, int siz, int& x, int& y) {
    if (not now) { x = y = 0; return; }
    pushDown (now);

    if (siz <= tr[tr[now].ls].siz) {
        y = now; split (tr[now].ls, siz, x, tr[now].ls);
        pushUp (now);
    } else {
        x = now; split (tr[now].rs, siz - tr[tr[now].ls].siz - 1, tr[now].rs, y);
        pushUp (now);    
    }
}

int merge (int x, int y) {
    if (not x or not y) { return x | y; }

    if (tr[x].key < tr[y].key) {
        pushDown (x);
        tr[x].rs = merge (tr[x].rs, y);
        pushUp (x);
        return x;
    } else {
        pushDown (y);
        tr[y].ls = merge (x, tr[y].ls);
        pushUp (y);
        return y;
    }
}

inline void rev (int l, int r) {
    int x, y, z;
    split (root, r, x, z);
    split (x, l - 1, x, y);
    tr[y].tag ^= 1;
    root = merge (merge (x, y), z);
}

void output (int now) {
    if (not now) { return; }

    pushDown (now);

    output (tr[now].ls);
    std::cout << tr[now].val << " ";
    output (tr[now].rs);
}
可持久化平衡树

其实跟可持久化线段树本质相同

似乎算导上讲过数据结构可持久化的通用方法

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
struct Node {
    int val;
    int ls, rs;
    int siz;

    unsigned long long key;
} tr[maxn * 50];

std::mt19937 rnd (std::chrono::steady_clock::now ().time_since_epoch ().count ());

int tot, root[maxn];

inline int newNode (Node old) {
    tr[++tot] = old;
    return tot;
}

inline void pushUp (int now) { tr[now].siz = tr[tr[now].ls].siz + tr[tr[now].rs].siz + 1; }

void split (int now, int val, int& x, int& y) {
    if (not now) { x = y = 0; return; }

    if (tr[now].val <= val) {
        int id = newNode (tr[now]);
        x = id; split (tr[id].rs, val, tr[id].rs, y);
        pushUp (id);
    } else {
        int id = newNode (tr[now]);
        y = id; split (tr[id].ls, val, x, tr[id].ls);
        pushUp (id);
    }
}

int merge (int x, int y) {
    if (not x or not y) { return x | y; }

    if (tr[x].key <= tr[y].key) {
        int id = newNode (tr[x]);
        tr[id].rs = merge (tr[id].rs, y);
        pushUp (id);
        return id;
    } else {
        int id = newNode (tr[y]);
        tr[id].ls = merge (x, tr[id].ls);
        pushUp (id);
        return id;
    }
}

inline void insert (int val, int i, int old) {
    root[i] = root[old];
    int x, y; split (root[i], val, x, y);
    root[i] = merge (merge (x, newNode ({ val, 0, 0, 1, rnd () })), y);
}

inline void remove (int val, int i, int old) {
    root[i] = root[old];
    int x, y; split (root[i], val, x, y);
    int z; split (x, val - 1, x, z);
    z = merge (tr[z].ls, tr[z].rs);
    root[i] = merge (merge (x, z), y);
}

inline int getRank (int val, int i, int old) {
    root[i] = root[old];
    int x, y; split (root[i], val - 1, x, y);
    int rank = tr[x].siz + 1;
    root[i] = merge (x, y);
    return rank;
}

inline int getNum (int rank, int i, int old) {
    root[i] = root[old];
    int now = root[i];
    while (now) {
        if (tr[tr[now].ls].siz + 1 == rank) { return tr[now].val; }

        if (rank <= tr[tr[now].ls].siz) { now = tr[now].ls; }
        else { rank -= tr[tr[now].ls].siz + 1; now = tr[now].rs; }
    }
}

inline int pre (int val, int i, int old) {
    root[i] = root[old];
    int x, y; split (root[i], val - 1, x, y);

    int now = x;
    while (tr[now].rs) { now = tr[now].rs; }
    root[i] = merge (x, y);
    return now ? tr[now].val : -2147483647;
}

inline int nxt (int val, int i, int old) {
    root[i] = root[old];
    int x, y; split (root[i], val, x, y);

    int now = y;
    while (tr[now].ls) { now = tr[now].ls; }
    root[i] = merge (x, y);
    return now ? tr[now].val : 2147483647;
}

树套树

树状数组套线段树

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
struct FenwickTree {
    struct SegmentTree {
        struct Node {
            int ls, rs;
            int sum;
        } tr[maxn << 9];

        std::vector<int> Add;
        std::vector<int> Sub;

        int root[maxn], tot;

        void modify (int& now, int l, int r, int pos, int val) {
            if (not now) { now = ++tot; }
            tr[now].sum += val;

            if (l == r) { return; }    

            int mid = (l + r) >> 1;

            if (pos <= mid) { modify (tr[now].ls, l, mid, pos, val); }
            if (pos > mid) { modify (tr[now].rs, mid + 1, r, pos, val); }
        }

        int query (int l, int r, int k) {
            if (l == r) { return l; }

            int sum = 0; 
            for (auto x : Add) { sum += tr[tr[x].ls].sum; }
            for (auto x : Sub) { sum -= tr[tr[x].ls].sum; }

            for (auto& x : Add) { x = (k <= sum) ? tr[x].ls : tr[x].rs; }
            for (auto& x : Sub) { x = (k <= sum) ? tr[x].ls : tr[x].rs; }

            int mid = (l + r) >> 1;

            return (k <= sum) ? query (l, mid, k) : query (mid + 1, r, k - sum);
        }
    } seg;

    inline int lowbit (int x) { return x & (-x); }

    inline void ins (int pos, int val) {
        for (int i = pos; i <= n; i += lowbit (i)) { seg.modify (seg.root[i], 0, 1e9, val, 1); }    
    }

    inline void del (int pos, int val) {
        for (int i = pos; i <= n; i += lowbit (i)) { seg.modify (seg.root[i], 0, 1e9, val, -1); }
    }

    inline int query (int l, int r, int k) {
        seg.Add.clear (); for (int i = r; i; i -= lowbit (i)) { seg.Add.push_back (seg.root[i]); }
        seg.Sub.clear (); for (int i = l - 1; i; i -= lowbit (i)) { seg.Sub.push_back (seg.root[i]); }

        return seg.query (0, 1e9, k);
    }
} tr;

笛卡尔树

神秘科技

1
2
3
4
5
6
7
8
9
10
11
inline int build () {
    std::stack <int> rChain; // 右链
    rep (now, 1, n) {
        int last = 0;
        while (not rChain.empty () and w[rChain.top ()] > w[now]) { last = rChain.top (); rChain.pop (); }
        tr[rChain.empty () ? 0 : rChain.top ()].rs = now;
        tr[now].ls = last;
        rChain.push (now);
    }
    return tr[0].rs;
}

树

树链剖分

核心部分代码不长

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
int fa[maxn], siz[maxn], son[maxn], dep[maxn];
void build_tree (int now) {
    siz[now] = 1;
    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;
        if (t == fa[now]) { continue; }
        fa[t] = now;
        dep[t] = dep[now] + 1;
        build_tree (t);
        siz[now] += siz[t];
        if (siz[t] > siz[son[now]]) { son[now] = t; }
    }
}

int top[maxn], dfn[maxn], dpos, rnk[maxn];
// int bottom[maxn];
void tree_decomp (int now, int topnow) {
    dfn[now] = ++dpos;
    rnk[dfn[now]] = now;
    top[now] = topnow;
    // bottom[now] = dfn[now];

    if (not son[now]) { return; }
    tree_decomp (son[now], topnow);
    // bottom[now] = std::max (bottom[now], bottom[son[now]]);

    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;
        if (t == fa[now]) { continue; }
        if (t == son[now]) { continue; }

        tree_decomp (t, t);
        // bottom[now] = std::max (bottom[now], bottom[t]);
    }
}

子树内的信息

一般会像上面注释里面一样维护一个 bottom[u] 表示以 为根的子树中最大的

然后就可以

1
2
3
inline i64 subtreeQuery (int x) {
    return tr.query (1, 1, n, dfn[x], bottom[x]);
}

修改同理

路径上的信息

直接跳链即可

1
2
3
4
5
6
7
8
9
10
11
12
13
inline void chainModify (int x, int y, i64 val) {
    while (top[x] != top[y]) {
        if (dep[top[x]] > dep[top[y]]) {
            tr.modify (1, 1, n, dfn[top[x]], dfn[x], val);
            x = fa[top[x]];
        } else {
            tr.modify (1, 1, n, dfn[top[y]], dfn[y], val);
            y = fa[top[y]];
        }
    }
    if (dfn[x] > dfn[y]) { std::swap (x, y); }
    tr.modify (1, 1, n, dfn[x], dfn[y], val);
}

查询同理

lca

同样是直接跳链

1
2
3
4
5
6
7
8
9
10
inline int lca (int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] > dep[top[v]]) {
            u = fa[top[u]];
        } else {
            v = fa[top[v]];
        }
    }
    return dep[u] < dep[v] ? u : v;
}
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
struct Node {
    int sum, val;
    int ch[2];
    int fa;
    bool tag;
} tr[maxn];

inline bool chk (int now) { return now == tr[tr[now].fa].ch[1]; }
inline bool notRoot (int now) { return now == tr[tr[now].fa].ch[0] or now == tr[tr[now].fa].ch[1]; }

inline void pushUp (int now) { tr[now].sum = tr[tr[now].ch[0]].sum xor tr[tr[now].ch[1]].sum xor tr[now].val; }

inline void rev (int now) { std::swap (tr[now].ch[0], tr[now].ch[1]); tr[now].tag ^= 1; }
inline void pushDown (int now) {
    if (not tr[now].tag) { return; }
    if (tr[now].ch[0]) { rev (tr[now].ch[0]); }
    if (tr[now].ch[1]) { rev (tr[now].ch[1]); }
    tr[now].tag = false;
}

void pushAll (int now) {
    if (notRoot (now)) { pushAll (tr[now].fa); }
    pushDown (now);
}

inline void connect (int fa, int x, int p) { tr[fa].ch[p] = x; tr[x].fa = fa; }

inline void rotate (int x) {
    int f = tr[x].fa, ff = tr[f].fa, p = chk (x), pp = chk (f); 
    pushDown (f); pushDown (x);
    if (notRoot (f)) { connect (ff, x, pp); }
    else { tr[x].fa = ff; }
    connect (f, tr[x].ch[p ^ 1], p); connect (x, f, p ^ 1);
    pushUp (f); pushUp (x);
}

inline void splay (int x) {
    pushAll (x);
    for (; notRoot (x); rotate (x)) {
        if (notRoot (tr[x].fa)) { rotate (chk (tr[x].fa) == chk (x) ? tr[x].fa : x); }
    }
    pushUp (x);    
}

inline void access (int x) {
    int pre = 0;
    while (x) {
        splay (x); tr[x].ch[1] = pre; pushUp (x);
        x = tr[pre = x].fa;
    }
}

inline void makeRoot (int x) { access (x); splay (x); rev (x); }
inline void split (int x, int y) { makeRoot (x); access (y); splay (y); }

inline int findRoot (int x) {
    access (x); splay (x); 
    pushDown (x); while (tr[x].ch[0]) { x = tr[x].ch[0]; pushDown (x); }
    splay (x); return x;
}

inline void link (int x, int y) { 
    makeRoot (x); 
    if (x == findRoot (y)) { return; } 
    tr[x].fa = y;
}

inline void cut (int x, int y) { 
    split (x, y); 
    if (tr[y].ch[0] != x or tr[x].ch[0] != tr[x].ch[1]) { return; }
    tr[y].ch[0] = tr[x].fa = 0; 
    pushUp (y);
}

点分治

淀粉质

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
inline void addEdge (int u, int v, int w) {
    es[++cnt] = Edge { u, v, last[u], w };
    last[u] = cnt;
}

int sum;
std::bitset<maxn> removed;

int root;
int maxpart[maxn];
int siz[maxn];

void getRoot (int now, int fa) {
    siz[now] = 1; 
    maxpart[now] = 0;
    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;
        if (t == fa) { continue; }
        if (removed[t])    { continue; }

        getRoot (t, now);
        siz[now] += siz[t];
        maxpart[now] = std::max (maxpart[now], siz[t]);
    }
    maxpart[now] = std::max (maxpart[now], sum - siz[now]);
    if (maxpart[now] < maxpart[root]) { root = now; }
}

int disStack[maxn], dpos;
int removeStack[maxn], rpos;

int dis[maxn];
void getDis (int now, int fa) {
    disStack[++dpos] = dis[now];
    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;
        if (t == fa) { continue; }
        if (removed[t]) { continue; }

        dis[t] = dis[now] + es[i].w;
        getDis (t, now);
    }
}

const int maxv = 100000005;
std::bitset<maxv> exist;

void solve (int now) {
    exist[0] = true;

    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;
        if (removed[t]) { continue; }

        dis[t] = es[i].w;
        getDis (t, now);

        for (int j = 1; j <= dpos; j++) {
            for (auto &q : qs) {
                if (q.k - disStack[j] >= 0) { q.ans |= exist[q.k - disStack[j]]; }
            }
        }

        while (dpos) {
            int top = disStack[dpos--];
            exist[top] = true;
            removeStack[++rpos] = top;
        }
    }

    while (rpos) {
        int top = removeStack[rpos--];
        exist[top] = false;
    }
}

inline void divide (int now) {
    removed[now] = true;
    solve (now);

    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;
        if (removed[t]) { continue; }

        sum = siz[t];
        maxpart[root] = 0x3f3f3f3f;
        getRoot (t, now);
        getRoot (root, now); // 实际上在getSiz

        divide (root);
    }
}
  • Title: 蒟蒻の模板
  • Author: rainbow-auto
  • Created at : 2023-10-02 22:01:54
  • Updated at : 2025-11-24 22:48:20
  • Link: https://rainbow-auto.github.io/2023/10/02/蒟蒻の模板/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
蒟蒻の模板
  1. 蒟蒻 Rainbow-Automaton 的模板
    1. 代码注意事项
    2. 杂项
      1. 对拍
      2. 毫秒级随机数
      3. 计时
    3. 图论
      1. 存图
      2. 最短路
      3. 生成树
      4. 欧拉回路
      5. Tarjan 系列
      6. 网络流
    4. 字符串
      1. 前缀函数
      2. AC 自动机
      3. 后缀自动机
      4. Manacher
      5. 回文自动机
    5. 数学
      1. 预处理约数
      2. 预处理质因数
      3. Miller-Rabin
      4. 快速幂
      5. 欧拉函数
      6. 逆元
      7. exgcd
      8. 线性筛
      9. 中国剩余定理
      10. 高维前缀和
      11. 异或线性基
      12. 模意义下线性基
      13. 高斯消元
      14. 多项式
      15. Stern–Brocot 树
      16. Prufer 序列
    6. 数据结构
      1. 并查集
      2. 树状数组
      3. 线段树
      4. 01-trie
      5. 平衡树
      6. 树套树
      7. 笛卡尔树
    7. 树
      1. 树链剖分
      2. Link-Cut Tree
      3. 点分治