Cool Pomelo

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

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

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

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

阅读全文 »

发表于 分类于 ， 作者 Pomelorin

树上启发式合并。

树上启发式合并

例如计算 \(\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]]]--;
        }
    }
}

发表于 更新于 分类于 ，

简介

线段树，是用来存放给定区间内对应信息的一种数据结构，是一种二叉搜索树。可用来处理数组相应的单点、区间修改操作，也可以进行区间最值、区间和等的查询。

阅读全文 »

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

二叉堆

介绍

二叉堆主要支持的操作有：插入一个数 \(O(\log n)\)、查询最小值 \(O(1)\)、删除最小值 \(O(\log n)\)。

二叉堆是一棵完全二叉树，其每个节点都有一个值，且每个节点的值都大于等于/小于等于其父亲的值。每个节点的值都大于等于其父亲值的堆叫做小根堆（即根最小），否则叫做大根堆。STL 中的 priority_queue 其实就是一个大根堆。

阅读全文 »

发表于 分类于 ， 作者 Pomelorin

模板——图论

Floyd 算法，SPFA 算法（慎用），Dijkstra 算法，强连通分量，Prim 算法，Kruskal 算法，Dinic 最大流，欧拉路。

阅读全文 »

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

模板——杂项

Clion 配置快捷键，KMP，LCA，SG 函数，二进制相关，数位 DP，费马平方和定理，对抗搜索。

阅读全文 »

发表于 分类于 ， 作者 Pomelorin

模板——数据结构

ST 表，Trie 树，线段树，树状数组，并查集，动态开点线段树，主席树，lower_bound 用法，树套树，笛卡尔树，树链剖分。

阅读全文 »

发表于 分类于 ， 作者 Pomelorin

模板——数学类

快速幂，质数线性筛，质因数分解，欧几里得（gcd），扩展欧几里得（exgcd），求欧拉函数 \(\varphi(x)\)，欧拉定理，扩展欧拉定理，中国剩余定理（CRT），在任意模意义下的逆元，同余最短路，组合数，Lucas 定理，卡特兰数，递推求逆元，拉格朗日插值，康托展开，高斯消元，矩阵快速幂。

阅读全文 »
0%