NIRVANA

OI Diary

POJ728 Desert King <二分+MST>

Posted on 2017-10-24 Symbols count in article: 893 Reading time ≈ 3 mins.

Problem

Desert King

Description

David the Great has just become the king of a desert country. To win the respect of his people, he decided to build channels all over his country to bring water to every village. Villages which are connected to his capital village will be watered. As the dominate ruler and the symbol of wisdom in the country, he needs to build the channels in a most elegant way.
After days of study, he finally figured his plan out. He wanted the average cost of each mile of the channels to be minimized. In other words, the ratio of the overall cost of the channels to the total length must be minimized. He just needs to build the necessary channels to bring water to all the villages, which means there will be only one way to connect each village to the capital.
His engineers surveyed the country and recorded the position and altitude of each village. All the channels must go straight between two villages and be built horizontally. Since every two villages are at different altitudes, they concluded that each channel between two villages needed a vertical water lifter, which can lift water up or let water flow down. The length of the channel is the horizontal distance between the two villages. The cost of the channel is the height of the lifter. You should notice that each village is at a different altitude, and different channels can’t share a lifter. Channels can intersect safely and no three villages are on the same line.
As King David’s prime scientist and programmer, you are asked to find out the best solution to build the channels.

Input

There are several test cases. Each test case starts with a line containing a number $N (2 \le N \le 1000)$ , which is the number of villages. Each of the following $N$ lines contains three integers, $x$ , $y$ and $z$ $(0\le x, y < 10^4, 0 \le z < 10^7)$ . $(x, y)$ is the position of the village and $z$ is the altitude. The first village is the capital. A test case with $N = 0$ ends the input, and should not be processed.

Output

For each test case, output one line containing a decimal number, which is the minimum ratio of overall cost of the channels to the total length. This number should be rounded three digits after the decimal point.

POJ3228 Gold Transportation < MST >

Posted on 2017-10-24 Symbols count in article: 688 Reading time ≈ 3 mins.

Problem

Gold Transportation

Time Limit: $2000MS$
Memory Limit: $65536K$

Description

Recently, a number of gold mines have been discovered in Zorroming State. To protect this treasure, we must transport this gold to the storehouses as quickly as possible. Suppose that the Zorroming State consists of N towns and there are M bidirectional roads among these towns. The gold mines are only discovered in parts of the towns, while the storehouses are also owned by parts of the towns. The storage of the gold mine and storehouse for each town is finite. The truck drivers in the Zorroming State are famous for their bad temper that they would not like to drive all the time and they need a bar and an inn available in the trip for a good rest. Therefore, your task is to minimize the maximum adjacent distance among all the possible transport routes on the condition that all the gold is safely transported to the storehouses.

Input

The input contains several test cases. For each case, the first line is integer $N$ $(1\le N\le 200)$ . The second line is $N$ integers associated with the storage of the gold mine in every towns .The third line is also $N$ integers associated with the storage of the storehouses in every towns .Next is integer $M$ $(0\le M\le \frac{(n-1)\times n}{2})$ .Then M lines follow. Each line is three integers $x$ , $y$ and $d$ $(1\le x,y\le N, 0<d\le 10^4)$ , means that there is a road between $x$ and $y$ for distance of $d$ . $N=0$ means end of the input.

Output

For each case, output the minimum of the maximum adjacent distance on the condition that all the gold has been transported to the storehouses or “No Solution”.

BZOJ1070【SCOI2007】修车 <费用流>

Posted on 2017-10-17 Symbols count in article: 751 Reading time ≈ 3 mins.

Problem

【SCOI2007】修车

$\mathrm{Time\;Limit:\;1\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

同一时刻有 $N$ 位车主带着他们的爱车来到了汽车维修中心。维修中心共有 $M$ 位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这 $M$ 位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。
说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

Input

第一行有两个 $m,n$ ，表示技术人员数与顾客数。接下来 $n$ 行，每行 $m$ 个整数。第 $i+1$ 行第 $j$ 个数表示第 $j$ 位技术人
员维修第 $i$ 辆车需要用的时间 $T$ 。

Output

最小平均等待时间，答案精确到小数点后 $2$ 位。

BZOJ1972 【SDOI2010】猪国杀 <模拟>

Posted on 2017-10-17 Symbols count in article: 5.8k Reading time ≈ 21 mins.

Problem

【SDOI2010】猪国杀

Time Limit: $1 Sec$
Memory Limit: $64 MB$

题目描述 Description

概述
《猪国杀》是一种多猪牌类回合制游戏，一共有三种角色：主猪，忠猪，反猪。
每局游戏主猪有且只有一只，忠猪和反猪可以有多只，每只猪扮演一种角色。
游戏目的：
·主猪（MP）：自己存活的情况下消灭所有的反猪。
·忠猪（ZP）：不惜一切保护主猪，胜利条件与主猪相同。
·反猪（FP）：杀死主猪。
游戏过程：
·游戏开始时候，每个玩家手里都会有4张牌，且体力上限和初始体力都是4。
·开始游戏时，从主猪开始，按照逆时针方向（数据中就是按照编号从1,2,3…n,1…的顺序）依次行动。
·每个玩家自己的回合可以分为2个阶段：
·摸牌阶段：
·从牌堆顶部摸两张牌，依次放到手牌的最右边。
·出牌阶段：
·你可以使用0张到任意张牌，每次使用牌的时候都使用最靠左的能够使用的牌。
·当然，要满足如下规则：
·1.如果没有猪哥连弩，每个出牌阶段只能使用一次“杀”来攻击。
·2.任何牌被使用后被弃置（武器是装备上）。
·被弃置的牌以后都不能再用，即与游戏无关。
各种牌介绍：
·每张手牌用一个字母表示，字母代表牌的种类。
·基本牌：
『桃(P)』：
·在自己的回合内，如果自己的体力值不等于体力上限，那么使用一个桃可以为自己补充一点体力，否则不能使用桃。
·桃只能对自己使用。
·在自己的回合外，如果自己的血变为0或者更低，那么也可以使用。
『杀(K)』：
·在自己的回合内，对攻击范围内除自己以外的一名角色使用。
·如果没有被『闪』抵消，则造成1点伤害。无论有无武器，杀的攻击范围都是1。
『闪(D)』：
·当你受到杀的攻击时，可以弃置一张闪来抵消杀的效果。
·锦囊牌：
『决斗(F)』：
·出牌阶段，对除自己以外任意一名角色使用，由目标角色先开始，自己和目标角色轮流弃置一张杀，首先没有杀可弃的一方受到1点伤害，另一方视为此伤害的来源。
『南猪入侵(N)』：
·出牌阶段，对除你以外所有角色使用，按逆时针顺序从使用者下家开始依次结算，除非弃置一张杀，否则受到1点伤害。
『万箭齐发(W)』：
·和南猪入侵类似，不过要弃置的不是杀而是闪。
『无懈可击(J)』：
·在目标锦囊生效前抵消其效果。
·每次有一张锦囊即将生效时，从使用这张锦囊的猪开始，按照逆时针顺序，依次得到使用无懈可击的机会。
·效果：
·用于决斗时，决斗无效并弃置。
·用于南猪入侵或万箭齐发时，当结算到某个角色时才能使用，当前角色不需弃置牌并且不会受到伤害（仅对一个角色产生效果）。
·用于无懈可击时，成为目标的无懈可击被无效。
·装备牌：
『猪哥连弩(Z)』：
·武器，攻击范围1，出牌阶段你可以使用任意张杀。
·同一时刻最多只能装一个武器。
·如果先前已经有了一把武器，那么之后再装武器的话，会弃置以前的武器来装现在的武器。
特殊事件及概念解释：
·伤害来源：
·杀、南猪入侵、万箭齐发的伤害来源均是使用该牌的猪。
·决斗的伤害来源如上。
·距离：
·两只猪的距离定义为沿着逆时针方向间隔的猪数＋1。即初始时1和2的距离为1，但是2和1的距离就是n-1。
·注意一个角色的死亡会导致一些猪距离的改变；
·玩家死亡：
·如果该玩家的体力降到0或者更低，并且自己手中没有足够的桃使得自己的体力值回到1，那么就死亡了。
·死亡后所有的牌（装备区，手牌区）被弃置。
·奖励与惩罚：
·反猪死亡时，最后一个伤害来源处（即使是反猪）立即摸三张牌。
·忠猪死亡时，如果最后一个伤害来源是主猪，那么主猪所有装备牌、手牌被弃置。
·注意，一旦达成胜利条件，游戏立刻结束，因此即使会摸3张牌或者还有牌可以用也不用执行了。
几种行为：
·献殷勤：
·使用无懈可击挡下南猪入侵、万箭齐发、决斗。
·使用无懈可击抵消表敌意。
·表敌意：
·对某个角色使用杀、决斗。
·使用无懈可击抵消献殷勤。
·跳忠：
·即通过行动表示自己是忠猪。
·跳忠行动就是对主猪或对某只已经跳忠的猪献殷勤，或者对某只已经跳反的猪表敌意。
·跳反：
·即通过行动表示自己是反猪。
·跳反行动就是对主猪或对某只已经跳忠的猪表敌意，或者对某只已经跳反的猪献殷勤。
·忠猪不会跳反，反猪也不会跳忠。
·不管是忠猪还是反猪，能够跳必然跳。
行动准则：
·共性：
·每个角色如果手里有桃且生命值未满，那么必然吃掉。
·有南猪入侵、万箭齐发、必然使用。
·有装备必然装上。
·受到杀时，有闪必然弃置。
·响应南猪入侵或者万箭齐发时候，有杀/闪必然弃置。
·不会对未表明身份的猪献殷勤（包括自己）。
·特性：
·主猪：
·主猪会认为没有跳身份，且用南猪入侵/万箭齐发对自己造成伤害的猪是类反猪（没伤害到不算，注意类反猪并没有表明身份），如果之后跳了，那么主猪会重新认识这只猪。
·对于每种表敌意的方式，对逆时针方向能够执行到的第一只类反猪或者已跳反猪表；如果没有，那么就不表敌意。
·决斗时会不遗余力弃置杀。
·如果能对已经跳忠的猪或自己献殷勤，那么一定献。
·如果能够对已经跳反的猪表敌意，那么一定表。
·忠猪：
·对于每种表敌意的方式，对逆时针方向能够执行到的第一只已经跳反的猪表，如果没有，那么就不表敌意。
·决斗时，如果对方是主猪，那么不会弃置杀，否则，会不遗余力弃置杀。
·如果有机会对主猪或者已经跳忠的猪献殷勤，那么一定献。
·反猪：
·对于每种表敌意的方式，如果有机会则对主猪表，否则，对逆时针方向能够执行到的第一只已经跳忠的猪表，如果没有，那么就不表敌意。
·决斗时会不遗余力弃置杀。
·如果有机会对已经跳反的猪献殷勤，那么一定献。

现在，我们已经知道每只猪的角色、手牌，还有牌堆初始情况，并且假设每个角色会按照如下的行为准则进行游戏，你需要做的就是告诉小猪 $iPig$ 最后的结果。
限于 $iPig$ 只会用 $P++$ 语言写 $A+B$ ，他请你用 $Pigcal(Pascal)$ 、 $P(C)$ 或 $P++(C++)$ 语言来帮他预测最后的结果。

输入描述 Input Description

输入文件第一行包含两个正整数 $n$ ( $2\le n\le 10$ )和 $m$ ( $m\le 2000$ )，分别代表玩家数和牌堆中牌的数量。数据保证牌的数量够用。
接下来 $n$ 行，每行 $5$ 个字符串，依次表示对第 $i$ 只猪的角色和初始 $4$ 张手牌描述。编号为 $1$ 的肯定是主猪。
再接下来一行，一共 $m$ 个字符串，按照从牌堆顶部到牌堆底部的顺序描述每张牌。
所有的相邻的两个字符串都严格用 $1$ 个空格隔开，行尾没有多余空格。

输出描述 Output Description

输出数据第一行包含一个字符串代表游戏结果。如果是主猪胜利，那么输出 $MP$ ，否则输出 $FP$ 。数据保证游戏总会结束。
接下来 $n$ 行，第 $i$ 行是对第 $i$ 只猪的手牌描述（注意只需要输出手牌），按照手牌从左往右的顺序输出，相邻两张牌用一个空格隔开，行末尾没有多余空格。如果这只猪已阵亡，那么只要输出 $DEAD$ 即可。注意如果要输出手牌而没有手牌的话，那么只需输出一个空行。

BZOJ2466【中山市选2009】树 <高斯消元>

Posted on 2017-10-17 Symbols count in article: 596 Reading time ≈ 2 mins.

Problem

【中山市选2009】树

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

图论中的树为一个无环的无向图。给定一棵树，每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了，那么该节点的灯会从熄灭变为点亮（当按之前是熄灭的），或者从点亮到熄灭（当按之前是点亮的），并且该节点的直接邻居也发生同样的变化。开始的时候，所有的指示灯都是熄灭的。
请编程计算最少要按多少次按钮，才能让所有节点的指示灯变为点亮状态。

Input

输入文件有多组数据。
输入第一行包含一个整数 $n$ ，表示树的节点数目。每个节点的编号从 $1$ 到 $n$ 。
输入接下来的 $n–1$ 行，每一行包含两个整数 $x$ ， $y$ ，表示节点 $x$ 和 $y$ 之间有一条无向边。
当输入 $n$ 为 $0$ 时，表示输入结束。

Output

对于每组数据，输出最少要按多少次按钮，才能让所有节点的指示灯变为点亮状态。每一组数据独占一行。

HDU4757 Tree < LCA+可持久化Trie >

Posted on 2017-10-17 Symbols count in article: 998 Reading time ≈ 4 mins.

Problem

Tree

Description

Zero and One are good friends who always have fun with each other.
This time, they decide to do something on a tree which is a kind of graph that there is only one path from node to node. First, Zero will give One an tree and every node in this tree has a value. Then, Zero will ask One a series of queries. Each query contains three parameters: $x$ , $y$ , $z$ which mean that he want to know the maximum value produced by $z$ $xor$ each value on the path from node $x$ to node $y$ (include node $x$ , node $y$ ). Unfortunately, One has no idea in this question. So he need you to solve it.

Input

There are several test cases and the cases end with $\mathrm{EOF}$ . For each case:
The first line contains two integers $n(1\le n\le 10^5)$ and $m(1\le m\le 10^5)$ , which are the amount of tree’s nodes and queries, respectively.
The second line contains $n$ integers $a[1..n]$ and $a[i]\;(0\le a[i]<2^{16})$ is the value on the $i^{th}$ node.
The next $n–1$ lines contains two integers $u$ $v$ , which means there is an connection between $u$ and $v$ .
The next m lines contains three integers $x$ $y$ $z$ , which are the parameters of Zero’s query.

Output

For each query, output the answer.

BZOJ1001【BJOI2006】狼抓兔子 <网络流>

Posted on 2017-10-16 Symbols count in article: 923 Reading time ≈ 3 mins.

Problem

【BJOI2006】狼抓兔子

$\mathrm{Time\;Limit:\;15\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的，
而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对一个网格的地形：
左上角点为 $(1,1)$ ,右下角点为 $(N,M)$ .有以下三种类型的道路

$(x,y)\Leftrightarrow(x+1,y)$
$(x,y)\Leftrightarrow(x,y+1)$
$(x,y)\Leftrightarrow(x+1,y+1)$

道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的. 左上角和右下角为兔子的两个窝，开始时所有的兔子都聚集在左上角 $(1,1)$ 的窝里，现在它们要跑到右下解 $(N,M)$ 的窝中去，狼王开始伏击些兔子.当然为了保险起见，如果一条道路上最多通过的兔子数为 $K$ ，狼王需要安排同样数量的K只狼，才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦.

Input

第一行为 $N,M$ .表示网格的大小， $N,M$ 均小于等于 $1000$ .
接下来分三部分
第一部分共 $N$ 行，每行 $M-1$ 个数，表示横向道路的权值.
第二部分共 $N-1$ 行，每行 $M$ 个数，表示纵向道路的权值.
第三部分共 $N-1$ 行，每行 $M-1$ 个数，表示斜向道路的权值.
输入文件保证不超过 $\mathrm{10\;MB}$

Output

输出一个整数，表示参与伏击的狼的最小数量.

BZOJ1997 Planer < 2-SAT >

Posted on 2017-10-14 Symbols count in article: 424 Reading time ≈ 2 mins.

Problem

Planer

Description

![](http://www.lydsy.com/JudgeOnline/images/1997_1.jpg)

Input

![](http://www.lydsy.com/JudgeOnline/images/1997_2.jpg)

Output

![](http://www.lydsy.com/JudgeOnline/images/1997_3.jpg)

POJ3207 Ikki's Story IV - Panda's Trick < 2-SAT >

Posted on 2017-10-14 Symbols count in article: 650 Reading time ≈ 2 mins.

Problem

Ikki’s Story IV - Panda’s Trick

Description

liympanda, one of Ikki’s friend, likes playing games with Ikki. Today after minesweeping with Ikki and winning so many times, he is tired of such easy games and wants to play another game with Ikki.
liympanda has a magic circle and he puts it on a plane, there are n points on its boundary in circular border: $0, 1, 2, \cdots , n-1$ . Evil panda claims that he is connecting m pairs of points. To connect two points, liympanda either places the link entirely inside the circle or entirely outside the circle. Now liympanda tells Ikki no two links touch inside/outside the circle, except on the boundary. He wants Ikki to figure out whether this is possible…
Despaired at the minesweeping game just played, Ikki is totally at a loss, so he decides to write a program to help him.

Input

The input contains exactly one test case.
In the test case there will be a line consisting of of two integers: $n$ and $m$ $(n \le 1,000, m \le 500)$ . The following $m$ lines each contain two integers $a_i$ and $b_i$ , which denote the endpoints of the $i^{th}$ wire. Every point will have at most one link.

Output

Output a line, either “panda is telling the truth…” or “the evil panda is lying again”.

【福利】洛谷模板汇总

Posted on 2017-09-29 Symbols count in article: 11k Reading time ≈ 39 mins.

Graph Theory

Disjoint Set

#include <iostream>
#define MAX_N 10000
using namespace std;
int n, m, f, x, y, father[MAX_N+5];
int getfather(int v) {
    if (father[v] == v) {
        return v;
    }
    father[v] = getfather(father[v]);
    return father[v];
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
    for (int i = 0; i < m; i++) {
        cin >> f >> x >> y;
        if (f == 1) {
            int f1 = getfather(x);
            int f2 = getfather(y);
            if (f1 != f2) {
                father[f1] = f2;
            }
        } else {
            int f1 = getfather(x);
            int f2 = getfather(y);
            if (f1 != f2) {
                cout << "N" << endl;
            } else {
                cout << "Y" << endl;
            }
        }
    }
    return 0;
}

Minimum Spanning Tree

Kruskal

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N 5000
#define MAX_M 200000
using namespace std;
struct node {
    int u, v, l;
} edge[MAX_M+5];
int n, m, tot = 0;
int father[MAX_N+5];
bool comp(const node &a, const node &b) {
    return a.l < b.l;
}
int getfather(int v) {
    if (father[v] == v) {
        return v;
    }
    father[v] = getfather(father[v]);
    return father[v];
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> edge[i].u >> edge[i].v >> edge[i].l;
    }
    sort(edge, edge+m, comp);
    for (int i = 1; i <= n; i++)	father[i] = i;
    int flag = n-1;
    for (int i = 0; i < m; i++) {
        int f1 = getfather(edge[i].u);
        int f2 = getfather(edge[i].v);
        if (f1 != f2) {
            father[f1] = f2;
            tot += edge[i].l;
            flag--;
        }
        if (flag == 0)	break;
    }
    if (flag == 0) {
        cout << tot;
    } else {
        cout << "orz";
    }
    return 0;
}

Prim

#include <bits/stdc++.h>
#define MAX_N 5000
#define INF 2147483647
using namespace std;
vector <int> G[MAX_N+5], E[MAX_N+5];
int n, m, dis[MAX_N+5], tot;    bool col[MAX_N+5];
void addedge(int u, int v, int c) {G[u].push_back(v), E[u].push_back(c);}
void Prim() {
    for (int i = 1; i <= n; i++) dis[i] = INF;	dis[1] = 0;
    for (int i = 1, u = -1; i <= n; i++, u = -1) {
        for (int j = 1; j <= n; j++)
            if (!col[j] && (u == -1 || dis[u] > dis[j]))	u = j;
        col[u] = true, tot += dis[u];
        for (int j = 0; j < (int)G[u].size(); j++) {
            int v = G[u][j], c = E[u][j];
            if (!col[v] && dis[v] > c)	dis[v] = c;
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, u, v, c; i < m; i++)
        scanf("%d%d%d", &u, &v, &c), addedge(u, v, c), addedge(v, u, c);
    Prim();	printf("%d", tot);
    return 0;
}

Shortest Path

Dijkstra

#include <bits/stdc++.h>
#define MAX_N 10000
#define INF 2147483647
#define pii pair <int, int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
int n, m, s, dis[MAX_N+5];
vector <int> G[MAX_N+5], E[MAX_N+5];
void addedge(int u, int v, int c) {G[u].push_back(v), E[u].push_back(c);}
void Dijkstra() {
    for (int i = 1; i <= n; i++)	dis[i] = INF;	dis[s] = 0;
    priority_queue <pii> que;	que.push(mp(0, s));
    while (!que.empty()) {
        int u = que.top().sec, d = que.top().fir;
        que.pop();	if (dis[u] != -d)	continue;
        for (int i = 0; i < (int)G[u].size(); i++) {
            int v = G[u][i], c = E[u][i];
            if (dis[u]+c >= dis[v])	continue;
            dis[v] = dis[u]+c, que.push(mp(-dis[v], v));
        }
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 0, u, v, c; i < m; i++)
        scanf("%d%d%d", &u, &v, &c), addedge(u, v, c);
    Dijkstra();
    for (int i = 1; i <= n; i++)	printf("%d ", dis[i]);
    return 0;
}

SPFA

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_M 500000
#define MAX_N 10000
#define INF 2147483647
using namespace std;
struct node {
    int v, len, next;
    node() {
        v = len = next = 0;
    }
} edge[MAX_M+5];
int n, m, s;
int first[MAX_N+5], cnt = 0;
int dis[MAX_N+5];
void insert(int u, int v, int l) {
    cnt++;
    edge[cnt].v = v;
    edge[cnt].len = l;
    edge[cnt].next = first[u];
    first[u] = cnt;
}
void SPFA() {
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
    }
    int que[MAX_N*20+5], mark[MAX_N+5];
    int head = 0, tail = 1;
    memset(mark, 0, sizeof(mark));
    que[1] = s;
    mark[s] = 1;
    dis[s] = 0;
    while (head <= tail) {
        head++;
        for (int tmp = first[que[head]]; tmp; tmp = edge[tmp].next) {
            if (dis[que[head]]+edge[tmp].len < dis[edge[tmp].v]) {
                dis[edge[tmp].v] = dis[que[head]]+edge[tmp].len;
                if (mark[edge[tmp].v] == 0) {
                    mark[edge[tmp].v] = 1;
                    tail++;
                    que[tail] = edge[tmp].v;
                }
            }
        }
        mark[que[head]] = 0;
    }
}
int main() {
    cin >> n >> m >> s;
    memset(first, 0, sizeof(first));
    int u, v, l;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> l;
        insert(u, v, l);
    }
    SPFA();
    for (int i = 1; i <= n; i++) {
        cout << dis[i] << " ";
    }
    return 0;
}

Tarjan

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define MAX_N 100000
using namespace std;
int n, m, c[MAX_N+5], f[MAX_N+5];
int dfn[MAX_N+5], low[MAX_N+5], col[MAX_N+5], val[MAX_N+5], ind, cnt;
vector <int> G[MAX_N+5], E[MAX_N+5];
stack <int> sta;
bool insta[MAX_N+5];
void tarjan(int u) {
    dfn[u] = low[u] = ++ind, sta.push(u), insta[u] = true;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!dfn[v])	tarjan(v), low[u] = min(low[u], low[v]);
        else if (insta[v])	low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        cnt++;
        for (int i = sta.top(); ; i = sta.top()) {
            col[i] = cnt, val[cnt] += c[i], insta[i] = false;
            sta.pop();	if (u == i)	break;
        }
    }
}
int DFS(int u) {
    if (f[u])	return f[u];
    int mx = 0;
    for (int i = 0; i < E[u].size(); i++)	mx = max(mx, DFS(E[u][i]));
    return f[u] = val[u]+mx;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)	scanf("%d", &c[i]);
    while (m--) {
        int u, v;	scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])	tarjan(i);
    for (int u = 1; u <= n; u++) {
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];	if (col[u] == col[v])	continue;
            E[col[u]].push_back(col[v]);
        }
    }
    int ans = 0;
    for (int i = 1; i <= cnt; i++)
        if (!f[i])	ans = max(ans, DFS(i));
    printf("%d", ans);
    return 0;
}

Cut-Vertex

#include <iostream>
#include <cstdio>
#define MAX_N 100000
#define MAX_M 200000
using namespace std;
struct Edge {
    int v, next;
} edge[MAX_M+5];
int first[MAX_N+5], flag[MAX_N+5], num[MAX_N+5], low[MAX_N+5];
int n, m, cnt = 0;
void insert(int u, int v, int pos) {
    edge[pos].next = first[u];
    edge[pos].v = v;
    first[u] = pos;
}
void dfs(int cur, int father) {
    int child = 0;
    num[cur] = low[cur] = ++cnt;
    for (int tmp = first[cur]; tmp; tmp = edge[tmp].next) {
        if (!num[edge[tmp].v]) {
            child++;
            dfs(edge[tmp].v, cur);
            low[cur] = min(low[cur], low[edge[tmp].v]);
            if (low[edge[tmp].v] >= num[cur]) {
                flag[cur] = 1;
            }
        } else if (num[edge[tmp].v] < num[cur] && edge[tmp].v != father) {
            low[cur] = min(low[cur], num[edge[tmp].v]);
        }
    }
    if (father == -1 && child == 1) {
        flag[cur] = 0;
    }
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        insert(u, v, i*2+1);
        insert(v, u, i*2+2);
    }
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        if (!num[i]) {
            dfs(i, -1);
        }
        if (flag[i]) {
            tot++;
        }
    }
    cout << tot << endl;
    for (int i = 1; i <= n; i++) {
        if (flag[i]) {
            cout << i << " ";
        }
    }
    return 0;
}

Lowest Common Ancestor

Doubling

#include <iostream>
#include <cstdio>
#include <vector>
#define MAX_N 500000
using namespace std;
struct Edge {
    int next, to;
} edge[(MAX_N<<1)+5];
int n, m, s, x, y, cnt;
int d[MAX_N+5], p[MAX_N+5][25], first[MAX_N+5];
bool vis[MAX_N+5];
inline int read() {
    int ret = 0;	char ch = getchar();
    while (ch < '0' || ch > '9')	ch = getchar();
    while (ch >= '0' && ch <= '9')	ret = ret*10+ch-'0', ch = getchar();
    return ret;
}
void INSERT(int a, int b) {
    edge[++cnt].next = first[a];
    edge[cnt].to = b;
    first[a] = cnt;
}
void DFS(int u) {
    vis[u] = true;
    for (int i = 1; (1<<i) <= n; i++) {
        if ((1<<i) <= d[u]) {
            p[u][i] = p[p[u][i-1]][i-1];
        }
    }
    for (int i = first[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (!vis[v]) {
            d[v] = d[u]+1;
            p[v][0] = u;
            DFS(v);
        }
    }
}
int LCA(int a, int b) {
    int i, j;
    if (d[a] < d[b])	swap(a, b);
    for (i = 0; (1<<i) <= d[a]; i++) {}
    i--;
    for (j = i; j >= 0; j--) {
        if (d[a]-(1<<j) >= d[b]) {
            a = p[a][j];
        }
    }
    if (a == b) {
        return a;
    }
    for (j = i; j >= 0; j--) {
        if (p[a][j] != p[b][j]) {
            a = p[a][j];
            b = p[b][j];
        }
    }
    return p[a][0];
}
int main() {
    n = read(), m = read(), s = read();
    for (int i = 1; i < n; i++) {
        x = read(), y = read();
        INSERT(x, y);
        INSERT(y, x);
    }
    DFS(s);
    for (int i = 0; i < m; i++) {
        x = read(), y = read();
        cout << LCA(x, y) << endl; 
    }
    return 0;
}

Heavy Path Decomposition

#include <bits/stdc++.h>
#define MAX_N 500000
using namespace std;
vector <int> G[MAX_N+5];
int n, m, r, dep[MAX_N+5], sz[MAX_N+5];
int fa[MAX_N+5], son[MAX_N+5], top[MAX_N+5];
void DFS(int u) {
    sz[u] = 1;
    for (auto v : G[u]) {
        if (v == fa[u])	continue;
        fa[v] = u, dep[v] = dep[u]+1, DFS(v), sz[u] += sz[v];
        if (!son[u] || sz[son[u]] < sz[v])	son[u] = v;
    }
}
void DFS(int u, int tp) {
    top[u] = tp;	if (son[u])	DFS(son[u], tp);
    for (auto v : G[u])	if ((v^fa[u]) && (v^son[u]))	DFS(v, v);
}
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;
}
int main() {
    scanf("%d%d%d", &n, &m, &r);	for (int i = 1, u, v; i < n; i++) scanf("%d%d", &u, &v), G[u].push_back(v), G[v].push_back(u);
    DFS(r), DFS(r, r);	while (m--) {int u, v;	scanf("%d%d", &u, &v);	printf("%d\n", LCA(u, v));}	return 0;
}

Negative Loop

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX_N 200000
#define SIZE 25000000
using namespace std;
int f;    char BUF[SIZE], *buf = BUF;
inline void read(int &x) {
    bool flag = 0;	while (*buf < 48)	if (*buf++ == 45)	flag = 1;
    x = 0;	while (*buf > 32)	x = x*10+*buf++-48;	x = flag ? -x : x;
}
vector <int> G[MAX_N+5], E[MAX_N+5];
int dis[MAX_N+5];
bool insta[MAX_N+5], flag;
void init(int n) {
    flag = false;
    for (int i = 1; i <= n; i++)	G[i].clear(), E[i].clear();
    memset(dis, 0, sizeof(dis)), memset(insta, false, sizeof(insta));
}
void DFS(int u) {
    insta[u] = true;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i], c = E[u][i];
        if (dis[u]+c >= dis[v])	continue;
        if (insta[v] || flag) {flag = true;	break;}
        dis[v] = dis[u]+c, DFS(v);
    }
    insta[u] = false;
}
int main() {
    f = fread(BUF, 1, SIZE, stdin);
    int T;	read(T);
    while (T--) {
        int n, m;	read(n), read(m);	init(n);
        while (m--) {
            int u, v, c;	read(u), read(v), read(c);
            G[u].push_back(v), E[u].push_back(c);
            if (c >= 0)	G[v].push_back(u), E[v].push_back(c);
        }
        for (int i = 1; i <= n; i++) {DFS(i);	if (flag)	break;}
        if (flag)	printf("YE5\n");
        else	printf("N0\n");
    }
    return 0;
}

Network Flow

#include <bits/stdc++.h>
#define MAX_N 10000
#define MAX_M 100000
#define INF 0x7f7f7f7f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, s, t, cnt, d[MAX_N+5], pr[MAX_N+5], cr[MAX_N+5];
struct node {int v, c, nxt;} E[(MAX_M<<1)+5];
void init() {memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c) {E[cnt] = (node){v, c, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, 0);}
bool BFS() {
    queue <int> que;	que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front();	que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (~d[v] || !c) continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t) return flow;	int ret = 0;
    for (int &i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (d[u]+1 != d[v] || !c) continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow) break;
    }
    if (!ret) d[u] = -1;	return ret;
}
void cpy() {for (int i = 1; i <= n; i++) cr[i] = pr[i];}
void rec() {for (int i = 1; i <= n; i++) pr[i] = cr[i];}
int Dinic() {int ret = 0;    cpy();	while (BFS()) ret += DFS(s, INF), rec();	return ret;}
int main() {
    read(n), read(m), read(s), read(t), init();
    for (int i = 1, u, v, c; i <= m; i++)
        read(u), read(v), read(c), addedge(u, v, c);
    return printf("%d\n", Dinic()), 0;
}

Minimum Cost Maximum Flow

#include <bits/stdc++.h>
#define MAX_N 5000
#define MAX_M 50000
#define INF 0x7f7f7f7f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, s, t, cnt, pr[MAX_N+5], cr[MAX_N+5], mxf, mic;
struct node {int v, c, w, nxt;} E[(MAX_M<<1)+5];
void init() {memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c, int w) {E[cnt] = (node){v, c, w, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c, int w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que;	bool inq[MAX_N+5];	int d[MAX_N+5], cr[MAX_N+5];
    memset(inq, false, sizeof inq), memset(d, INF, sizeof d);
    d[s] = 0, que.push(s), inq[s] = true, memset(cr, -1, sizeof cr);
    while (!que.empty()) {
        int u = que.front();	que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c, w = E[i].w;
            if (c && d[u]+w < d[v]) {
                d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (d[t] == INF) return false;	int flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mxf += flow, mic += d[t]*flow;	return true;
}
int main() {
    read(n), read(m), read(s), read(t), init();
    for (int i = 1, u, v, c, w; i <= m; i++)
        read(u), read(v), read(c), read(w), addedge(u, v, c, w);
    while (SPFA()) ;	printf("%d %d\n", mxf, mic);
    return 0;
}

Bipartite Matching

Hungary

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX_N 1000
using namespace std;
int n, m, e, match[MAX_N+5], cnt;
vector <int> G[MAX_N+5];
bool vis[MAX_N+5];
bool DFS(int u) {
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!vis[v]) {
            vis[v] = true;
            if (!match[v] || DFS(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}
int main() {
    cin >> n >> m >> e;
    int a, b;
    for (int i = 0; i < e; i++) {
        cin >> a >> b;
        if (a > n || b > m)	continue;
        G[a].push_back(b);
    }
    for (int i = 1; i <= n; i++) {
        memset(vis, false, sizeof(vis));
        if (DFS(i)) {
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}

Dinic

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAX_N 2000
#define MAX_M 1000000
#define INF 2147483647
using namespace std;
int n, m, s, t, n1, n2;
int pre[MAX_N+5], tmp[MAX_N+5], d[MAX_N+5], cnt;
struct node {int v, c, nxt;} E[MAX_M*2+MAX_N*2+5];
void init() {cnt = 0; s = 0, t = n; memset(pre, -1, sizeof(pre));}
void insert(int u, int v, int c) {E[cnt].v = v, E[cnt].c = c, E[cnt].nxt = pre[u], pre[u] = cnt++;}
bool BFS() {
    memset(d, -1, sizeof(d));
    queue <int> que;
    que.push(s), d[s] = 0;
    while (!que.empty()) {
        int u = que.front();
        for (int i = pre[u]; i != -1; i = E[i].nxt) {
            int v = E[i].v;
            if (E[i].c && d[v] == -1) {
                d[v] = d[u]+1;
                que.push(v);
            }
        }
        que.pop();
    }
    return d[t] != -1;
}
int DFS(int u, int flow) {
    if (u == t)	return flow;
    int ret = 0;
    for (int &i = pre[u]; i != -1; i = E[i].nxt) {
        int v = E[i].v;
        if (E[i].c && d[u]+1 == d[v]) {
            int tmp = DFS(v, min(flow, E[i].c));
            E[i].c -= tmp, E[i^1].c += tmp, flow -= tmp, ret += tmp;
            if (!flow)	break;
        }
    }
    if (!ret)	d[u] = -1;
    return ret;
}
int Dinic() {
    int ret = 0;
    for (int i = 0; i <= n; i++)	tmp[i] = pre[i];
    while (BFS()) {
        ret += DFS(s, INF);
        for (int i = 0; i <= n; i++)	pre[i] = tmp[i];
    }
    return ret;
}
int main() {
    scanf("%d%d%d", &n1, &n2, &m);	n = n1+n2+1;
    init();
    for (int i = 1; i <= n1; i++)	insert(s, i, 1), insert(i, s, 0);
    for (int i = n1+1; i <= n1+n2; i++)	insert(i, t, 1), insert(t, i, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        if (u > n1 || v > n2)	continue;
        insert(u, n1+v, 1), insert(n1+v, u, 0);
    }
    printf("%d", Dinic());
    return 0;
}

Math

Gaussian Elimination

#include <iostream>
#include <cstdio>
#include <vector>
#define MAX_N 100
#define EXP 1e-7
using namespace std;
typedef double fnt;
int n;    vector <fnt> f[MAX_N+5];	fnt ans[MAX_N+5];
bool gauss() {
    for (int i = 1, tmp; i <= n; i++) {
        for (tmp = i; tmp <= n; tmp++)	if (f[tmp][i] <= -EXP || f[tmp][i] >= EXP)	break;
        if (tmp > n)	return false;	swap(f[i], f[tmp]);
        for (int j = 1; j <= n; j++) {
            fnt div = f[j][i]/f[i][i];	if (j == i)	continue;
            for (int k = i; k <= n+1; k++)	f[j][k] -= f[i][k]*div;
        }
    }
    for (int i = 1; i <= n; i++)	ans[i] = f[i][n+1]/f[i][i];
    return true;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        f[i].push_back(0);
        for (int j = 1; j <= n+1; j++) {
            fnt x;	scanf("%lf", &x);
            f[i].push_back(x);
        }
    }
    if (gauss())	for (int i = 1; i <= n; i++)	printf("%.2lf\n", ans[i]);
    else	printf("No Solution");
    return 0;
}

Inverse

#include <iostream>
#include <cstdio>
#define MAX_N 3000000
using namespace std;
typedef long long lnt;
lnt inv[MAX_N+5];
void init(int n, lnt p) {inv[0] = inv[1] = 1;    for (int i = 2; i <= n; i++)	inv[i] = (p-p/i*inv[p%i]%p)%p;}
int main() {
    int n;	lnt p;	scanf("%d%lld", &n, &p);
    init(n, p);
    for (int i = 1; i <= n; i++)	printf("%lld\n", inv[i]);
    return 0;
}

Linear Basis

#include <iostream>
#include <cstdio>
#define MAX_N 50
using namespace std;
typedef long long lnt;
int n;    lnt base[MAX_N+5], pow[MAX_N+5];
int main() {
    scanf("%d", &n);	pow[0] = 1;
    for (int i = 1; i <= MAX_N; i++)	pow[i] = pow[i-1]*2;
    for (int i = 1; i <= n; i++) {
        lnt x;	scanf("%lld", &x);
        for (int j = MAX_N; j >= 0; j--)	if (pow[j]&x) {
            if (base[j])	x ^= base[j];
            else {base[j] = x;	break;}
        }
    }
    lnt ans = 0;
    for (int i = MAX_N; i >= 0; i--)	if ((ans^pow[i]) > ans)	ans ^= base[i];
    printf("%lld", ans);
    return 0;
}

Lucas

#include <iostream>
#include <cstdio>
#define MAX_P 100000
using namespace std;
typedef long long lnt;
lnt f[MAX_P+5] = {1};
void init(lnt p) {for (int i = 1; i <= MAX_P; i++)    f[i] = f[i-1]*i%p;}
lnt FLT(lnt x, lnt p) {
    lnt ret = 1;	x %= p;
    for (int k = p-2; k; k >>= 1)	ret = k%2 ? ret*x%p : ret, x = x*x%p;
    return ret;
}
lnt lucas(lnt n, lnt m, lnt p) {return m ? (n%p >= m%p ? f[n%p]*FLT(f[m%p]*f[n%p-m%p], p)*lucas(n/p, m/p, p)%p : 0) : 1;}
int main() {
    int T;	scanf("%d", &T);
    while (T--) {
        lnt n, m, p;	scanf("%lld%lld%lld", &n, &m, &p);
        init(p), printf("%lld\n", lucas(n+m, min(n, m), p)%p);
    }
    return 0;
}

Matrix Fast Power

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 100
#define MOD 1000000007
using namespace std;
int n;
struct Matrix {
    long long ele[MAX_N][MAX_N];
    inline Matrix operator * (const Matrix &x) const {
        Matrix ret;
        memset(ret.ele, 0, sizeof(ret.ele));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                    ret.ele[i][j] = (ret.ele[i][j]+ele[i][k]*x.ele[k][j])%MOD;
        return ret;
    }
};
Matrix Power(Matrix a, long long k) {
    if (k == 1)    return a;
    Matrix ret = Power(a, k/2);
    if (k%2)    return a*ret*ret;
    return ret*ret;
}
int main() {
    long long k;
    Matrix a;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a.ele[i][j];
    a = Power(a, k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << a.ele[i][j] << " ";
        cout << endl;
    }
    return 0;
}

Prime Sieve

#include <bits/stdc++.h>
#define MAX_N 10000000
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m;    bool NotPri[MAX_N+5];
int pri[MAX_N+5], mu[MAX_N+5], phi[MAX_N+5], cnt;
void init() {
    NotPri[1] = true, mu[1] = phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!NotPri[i]) pri[cnt++] = i, mu[i] = -1, phi[i] = i-1;
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > n) break;	NotPri[i*pri[j]] = true;
            if (i%pri[j]) phi[i*pri[j]] = phi[i]*phi[pri[j]], mu[i*pri[j]] = -mu[i];
            else {phi[i*pri[j]] = phi[i]*pri[j], mu[i*pri[j]] = 0; break;}
        }
    }
}
int main() {
    read(n), read(m), init();
    for (int x; m; m--)
        read(x), puts(NotPri[x] ? "No" : "Yes");
    return 0;
}

Ternary Search

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n;
double s, t;
double a[14];
double calc(double x) {
    double tot = 0, tmp = 1;
    for (int i = 0; i <= n; i++) {
        tot += tmp*a[i];
        tmp *= x;
    }
    return tot;
}
void f(double l, double r) {
    if (abs(r-l) <= 0.000001) {
        printf("%.5f", l);
        return;
    }
    double ml = (2*l+r)/3, mr = (l+2*r)/3;
    if (calc(ml) > calc(mr)) {
        f(l, mr);
    } else {
        f(ml, r);
    }
}
int main() {
    cin >> n >> s >> t;
    for (int i = n; i >= 0; i--) {
        cin >> a[i];
    }
    f(s, t);
    return 0;
}

Fast Fourier Transformation

#include <bits/stdc++.h>
#define MAX_N 1000000
using namespace std;
typedef double dnt;
const dnt Pi = acos(-1);
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
struct Complex {dnt r, i;} a[(MAX_N<<2)+5], b[(MAX_N<<2)+5], c[(MAX_N<<2)+5];
Complex operator + (Complex x, Complex y) {return (Complex){x.r+y.r, x.i+y.i};}
Complex operator - (Complex x, Complex y) {return (Complex){x.r-y.r, x.i-y.i};}
Complex operator * (Complex x, Complex y) {return (Complex){x.r*y.r-x.i*y.i, x.r*y.i+x.i*y.r};}
void Rader(Complex *s, int l) {
    for (int i = 1, j = l/2, k; i < l-1; i++) {
        if (i < j) swap(s[i], s[j]);	k = l/2;
        while (j >= k) j -= k, k >>= 1;	j += k;
    }
}
void FFT(Complex *s, int l, int f) {
    Rader(s, l);	Complex wn, w;
    for (int i = 2; i <= l; i <<= 1) {
        wn = (Complex){cos(2*Pi/i), f*sin(2*Pi/i)};
        for (int j = 0; j < l; j += i) {
            w = (Complex){1, 0};
            for (int k = j; k < j+i/2; k++, w = w*wn) {
                Complex x = s[k], y = w*s[k+i/2];
                s[k] = x+y, s[k+i/2] = x-y;
            }
        }
    }
    if (f == -1) for (int i = 0; i <= l; i++) s[i].r /= l;
}
int main() {
    int n, m;	read(n), read(m);
    for (int i = 0, x; i <= n; i++) read(x), a[i].r = x;
    for (int i = 0, x; i <= m; i++) read(x), b[i].r = x;
    int l;	for (l = 1; l <= n+m; l <<= 1) ;	FFT(a, l, 1), FFT(b, l, 1);
    for (int i = 0; i <= l; i++) c[i] = a[i]*b[i];	FFT(c, l, -1);
    for (int i = 0; i <= n+m; i++) printf("%d ", (int)(c[i].r+0.5));
    return 0;
}

Data Structure

Heap

#include <iostream>
using namespace std;
int n, heap[1000000+5], size = 0;
void insert(int x) {
    size++;
    heap[size] = x;
    int current = size;
    int father = current/2;
    while (father > 0 && heap[father] > heap[current]) {
        swap(heap[father], heap[current]);
        current = father;
        father = current/2;
    }
}
void pop() {
    heap[1] = heap[size];
    size--;
    int current = 1;
    int child = current*2;
    if (child < size && heap[child] > heap[child+1])    child++;
    while (child <= size && heap[current] > heap[child]) {
        swap(heap[current], heap[child]);
        current = child;
        child = 2*current;
        if (child < size && heap[child] > heap[child+1])    child++;
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int f;
        cin >> f;
        if (f == 1) {
            int x;
            cin >> x;
            insert(x);
        } else if (f == 2) {
            cout << heap[1] << endl;
        } else {
            pop();
        }
    }
    return 0;
}

Mergeable Heap

#include <iostream>
#include <cstdio>
#define MAX_N 100000
using namespace std;
struct node {int val, dis, ls, rs;} heap[MAX_N+5];
int n, m, fa[MAX_N+5];
int getf(int x) {return fa[x] == x ? fa[x] : getf(fa[x]);}
int merge(int a, int b) {
    if (!a || !b)	return a^b;
    if (heap[a].val > heap[b].val || (heap[a].val == heap[b].val && a > b))	swap(a, b);
    heap[a].rs = merge(heap[a].rs, b), fa[heap[a].rs] = a;
    if (heap[heap[a].rs].dis > heap[heap[a].ls].dis)	swap(heap[a].ls, heap[a].rs);
    heap[a].dis = heap[a].rs == 0 ? 0 : heap[heap[a].rs].dis+1;	return a;
}
int pop(int a) {
    int l = heap[a].ls, r = heap[a].rs;
    heap[a].ls = heap[a].rs = heap[a].val = 0, fa[l] = l, fa[r] = r;
    return merge(l, r);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)	scanf("%d", &heap[i].val), fa[i] = i;
    while (m--) {
        int opt;	scanf("%d", &opt);
        if (opt == 1) {
            int x, y;	scanf("%d%d", &x, &y), x = getf(x), y = getf(y);
            if (heap[x].val && heap[y].val && x != y)	merge(x, y);
        }
        if (opt == 2) {
            int x;	scanf("%d", &x), x = getf(x);
            if (!heap[x].val)	printf("-1\n");
            else	printf("%d\n", heap[x].val), pop(x);
        }
    }
    return 0;
}

Binary Indexed Tree

Version 1

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 500000
using namespace std;
int n, m;
int tree[MAX_N+5];
int lowbit(int x) {
    return x&(-x);
}
void modify(int pos, int x) {
    while (pos <= n) {
        tree[pos] += x;
        pos += lowbit(pos);
    }
}
long long query(int t) {
    long long tot = 0;
    while (t > 0) {
        tot += tree[t];
        t -= lowbit(t);
    }
    return tot;
}
int main() {
    memset(tree, 0, sizeof(tree));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int tmp;
        cin >> tmp;
        modify(i, tmp);
    }
    for (int i = 0; i < m; i++) {
        int f, a, b;
        cin >> f >> a >> b;
        if (f == 1) {
            modify(a, b);
        } else {
            cout << query(b)-query(a-1) << endl;
        }
    }
    return 0;
}

Version 2

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 500000
using namespace std;
int n, m;
int tree[MAX_N+5];
int lowbit(int x) {
    return x&(-x);
}
void modify(int pos, int x) {
    while (pos <= n) {
        tree[pos] += x;
        pos += lowbit(pos);
    }
}
long long query(int pos) {
    long long tot = 0;
    while (pos > 0) {
        tot += tree[pos];
        pos -= lowbit(pos);
    }
    return tot;
}
int main() {
    memset(tree, 0, sizeof(tree));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        modify(i, x);
        modify(i+1, -x);
    }
    for (int i = 0; i < m; i++) {
        int f;
        cin >> f;
        if (f == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            modify(l, x);
            modify(r+1, -x);
        } else {
            int x;
            cin >> x;
            cout << query(x) << endl;
        }
    }
    return 0;
}

Segment Tree

Version 1

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 100000
using namespace std;
int n, k;
long long tree[MAX_N*4+50], tag[MAX_N*4+50];
void updata(int v) {
    tree[v] = tree[v*2]+tree[v*2+1];
}
void downtag(int v, int s, int t) {
    tag[v*2] += tag[v];
    tag[v*2+1] += tag[v];
    int m = (s+t)/2;
    tree[v*2] += tag[v]*(m-s+1);
    tree[v*2+1] += tag[v]*(t-m);
    tag[v] = 0;
}
void modify(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) {
        tree[v] += x*(t-s+1);
        tag[v] += x;
        return;
    }
    int m = (s+t)/2;
    downtag(v, s, t);
    if (l <= m) {
        modify(v*2, s, m, l, r, x);
    }
    if (r >= m+1) {
        modify(v*2+1, m+1, t, l, r, x);
    }
    updata(v);
}
void build(int v, int s, int t) {
    if (s == t) {
        cin >> tree[v];
        return;
    }
    int m = (s+t)/2;
    build(v*2, s, m);
    build(v*2+1, m+1, t);
    updata(v);
}
long long query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) {
        return tree[v];
    }
    int m = (s+t)/2;
    downtag(v, s, t);
    long long ret = 0;
    if (l <= m) {
        ret += query(v*2, s, m, l, r);
    }
    if (r >= m+1) {
        ret += query(v*2+1, m+1, t, l, r);
    }
    updata(v);
    return ret;
}
int main() {
    cin >> n >> k;
    build(1, 1, n);
    for (int i = 0; i < k; i++) {
        int f, l, r, x;
        cin >> f;
        if (f == 1) {
            cin >> l >> r >> x;
            modify(1, 1, n, l, r, x);
        } else {
            cin >> l >> r;
            cout << query(1, 1, n, l, r) << endl;
        }
    }
    return 0;
}

Version 2

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 100000
#define ll long long
using namespace std;
int n, m;
ll p;
ll tree[MAX_N*4+5], mul[MAX_N*4+5], add[MAX_N*4+5];
void updata(int v) {
    tree[v] = (tree[v*2]+tree[v*2+1])%p;
}
void downtag(int v, int s, int t, int mid) {
    if (mul[v] == 1 && add[v] == 0)	return;
    mul[v*2] = mul[v*2]*mul[v]%p;
    add[v*2] = (add[v*2]*mul[v]%p+add[v])%p;
    tree[v*2] = (tree[v*2]*mul[v]%p+add[v]*(ll)(mid-s+1)%p)%p;
    mul[v*2+1] = mul[v*2+1]*mul[v]%p;
    add[v*2+1] = (add[v*2+1]*mul[v]%p+add[v])%p;
    tree[v*2+1] = (tree[v*2+1]*mul[v]%p+add[v]*(ll)(t-mid)%p)%p;
    mul[v] = 1;
    add[v] = 0;
    return;
}
void create(int v, int s, int t) {
    mul[v] = 1;
    add[v] = 0;
    if (s == t) {
        cin >> tree[v];
        tree[v] %= p;
        return;
    }
    int mid = (s+t)/2;
    create(v*2, s, mid);
    create(v*2+1, mid+1, t);
    updata(v);
}
void modify1(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) {
        add[v] = (add[v]+(ll)x)%p;
        tree[v] = (tree[v]+(ll)x*(ll)(t-s+1)%p)%p;
        return;
    }
    int mid = (s+t)/2;
    downtag(v, s, t, mid);
    if (l <= mid) {
        modify1(v*2, s, mid, l, r, x);
    }
    if (r >= mid+1) {
        modify1(v*2+1, mid+1, t, l, r, x);
    }
    updata(v);
}
void modify2(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) {
        mul[v] = mul[v]*(ll)x%p;
        add[v] = add[v]*(ll)x%p;
        tree[v] = tree[v]*(ll)x%p;
        return; 
    }
    int mid = (s+t)/2;
    downtag(v, s, t, mid);
    if (l <= mid) {
        modify2(v*2, s, mid, l, r, x);
    }
    if (r >= mid+1) {
        modify2(v*2+1, mid+1, t, l, r, x);
    }
    updata(v);
}
ll query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) {
        return tree[v];
    }
    int mid = (s+t)/2;
    ll ret = 0;
    downtag(v, s, t, mid);
    if (l <= mid) {
        ret = (ret+query(v*2, s, mid, l, r))%p;
    }
    if (r >= mid+1) {
        ret = (ret+query(v*2+1, mid+1, t, l, r))%p;
    }
    updata(v);
    return ret;
}
int main() {
    cin >> n >> m >> p;
    create(1, 1, n);
    for (int i = 0; i < m; i++) {
        int f;
        cin >> f;
        if (f == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            modify2(1, 1, n, l, r, x%p);
        } else if (f == 2) {
            int l, r, x;
            cin >> l >> r >> x;
            modify1(1, 1, n, l, r, x%p);
        } else {
            int l, r;
            cin >> l >> r;
            cout << query(1, 1, n, l, r) << endl;
        }
    }
    return 0;
}

Sparse Table

#include <iostream>
#include <cstdio>
#include <cmath>
#define MAX_N 100000
using namespace std;
int n, m, num[MAX_N+5], mx[MAX_N+5][20];
void setTable() {
    for (int i = 1; i <= n; i++)	mx[i][0] = num[i];
    for (int j = 1; (1<<j) <= n; j++)
        for (int i = 1; i+(1<<j)-1 <= n; i++)
            mx[i][j] = max(mx[i][j-1], mx[i+(1<<j-1)][j-1]);
}
int query(int l, int r) {
    int range = (int)(log(r-l+1)/log(2));
    return max(mx[l][range], mx[r-(1<<range)+1][range]);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)	scanf("%d", &num[i]);
    setTable();
    while (m--) {
        int l, r;	scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r));
    }
    return 0;
}

Sustainable Segment Tree

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N 200000
using namespace std;
int n, m, num[MAX_N+5], hash[MAX_N+5], tot, root[MAX_N+5], cnt;
struct pre {int id, val;} p[MAX_N+5];
bool cmp (const pre &a, const pre &b) {return a.val < b.val;}
struct node {int ls, rs, val;} tr[MAX_N*50];
void updata(int v) {tr[v].val = tr[tr[v].ls].val+tr[tr[v].rs].val;}
void build(int v, int s, int t) {
    if (s == t)	return;	int mid = s+t>>1;
    tr[v].ls = ++cnt, tr[v].rs = ++cnt;
    build(tr[v].ls, s, mid), build(tr[v].rs, mid+1, t);
}
void modify(int v, int o, int s, int t, int x) {
    tr[v] = tr[o];	if (s == t) {tr[v].val++;	return;}
    int mid = s+t>>1;
    if (x <= mid)	modify(tr[v].ls = ++cnt, tr[o].ls, s, mid, x);
    else	modify(tr[v].rs = ++cnt, tr[o].rs, mid+1, t, x);
    updata(v);
}
int query(int v1, int v2, int s, int t, int k) {
    if (s == t)	return s;
    int mid = s+t>>1, tmp = tr[tr[v2].ls].val-tr[tr[v1].ls].val;
    if (k <= tmp)	return query(tr[v1].ls, tr[v2].ls, s, mid, k);
    else	return query(tr[v1].rs, tr[v2].rs, mid+1, t, k-tmp);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)	p[i].id = i, scanf("%d", &p[i].val);
    sort(p+1, p+n+1, cmp);
    for (int i = 1; i <= n; i++) {if (p[i].val != p[i-1].val || i == 1)	hash[++tot] = p[i].val;	num[p[i].id] = tot;}
    root[0] = ++cnt, build(root[0], 1, tot);
    for (int i = 1; i <= n; i++)	root[i] = ++cnt, modify(root[i], root[i-1], 1, tot, num[i]);
    while (m--) {
        int l, r, k;	scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", hash[query(root[l-1], root[r], 1, tot, k)]);
    }
    return 0;
}

Treap

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define MAX_N 100000
using namespace std;
struct TNode {
    TNode* s[2];
    int val, k, size;
    TNode() {}
    TNode(int _val, TNode* _s) {val = _val, s[0] = s[1] = _s, k = rand(), size = 1;}
    void updata() {size = s[0]->size+s[1]->size+1;}
} nil, tr[MAX_N+5], *null, *root, *cnt;
typedef TNode* P_TNode;
void init() {
    srand(19260817);
    nil = TNode(0, NULL), null = &nil;
    null->s[0] = null->s[1] = null, null->size = 0;
    cnt = tr, root = null;
}
P_TNode newnode(int val) {
    *cnt = TNode(val, null);
    return cnt++;
}
P_TNode merge(P_TNode a, P_TNode b) {
    if (a == null)    return b;
    if (b == null)    return a;
    if (a->k > b->k) {a->s[1] = merge(a->s[1], b), a->updata(); return a;}
    if (a->k <= b->k) {b->s[0] = merge(a, b->s[0]), b->updata(); return b;}
}
void split(P_TNode v, int val, P_TNode &ls, P_TNode &rs) {
    if (v == null) {ls = rs = null; return;}
    if (val < v->val) {rs = v; split(rs->s[0], val, ls, rs->s[0]);}
    if (val >= v->val) {ls = v;    split(ls->s[1], val, ls->s[1], rs);}
    v->updata();
}
void insert(int val) {
    P_TNode ls, rs;
    split(root, val, ls, rs);
    root = merge(merge(ls, newnode(val)), rs);
}
void remove(int val) {
    P_TNode ls, mids, rs;
    split(root, val-1, ls, rs);
    split(rs, val, mids, rs);
    root = merge(ls, merge(merge(mids->s[0], mids->s[1]), rs));
}
int get_rank(int val) {
    P_TNode ls, rs;
    split(root, val-1, ls, rs);
    int ret = ls->size+1;
    root = merge(ls, rs);
    return ret;
}
int get_kth(P_TNode v, int k) {
    if (k <= v->s[0]->size)    return get_kth(v->s[0], k);
    if (k > v->s[0]->size+1)    return get_kth(v->s[1], k-v->s[0]->size-1);
    return v->val;
}
int get_nearest(P_TNode v, int sn) {
    while (v->s[sn] != null)    v = v->s[sn];
    return v->val;
}
int predecessor(int val) {
    P_TNode ls, rs;
    split(root, val-1, ls, rs);
    int ret = get_nearest(ls, 1);
    root = merge(ls, rs);
    return ret;
}
int successor(int val) {
    P_TNode ls, rs;
    split(root, val, ls, rs);
    int ret = get_nearest(rs, 0);
    root = merge(ls, rs);
    return ret;
}
int main() {
    init();
    int n, opt, x;
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &opt, &x);
        if (opt == 1)    insert(x);
        if (opt == 2)    remove(x);
        if (opt == 3)    printf("%d\n", get_rank(x));
        if (opt == 4)    printf("%d\n", get_kth(root, x));
        if (opt == 5)    printf("%d\n", predecessor(x));
        if (opt == 6)    printf("%d\n", successor(x));
    }
    return 0;
}

Splay

Normal

#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
#define flag (cur->fa->fa!=tar&&cur->fa->fa->s[sn]==cur->fa)
using namespace std;
struct SplayNode {
    SplayNode *s[2], *fa;	int val, w, sz;
    void updata() {sz = w+(s[0]?s[0]->sz:0)+(s[1]?s[1]->sz:0);}
};
struct SplayTree {
    SplayNode* rt;
    SplayNode* newnode(int _val) {
        SplayNode* v = new SplayNode;
        v->s[0] = v->s[1] = v->fa = NULL;
        v->val = _val, v->w = v->sz = 1;
        return v;
    }
    SplayTree() {
        rt = newnode(-INF), rt->s[1] = newnode(INF);
        rt->s[1]->fa = rt, rt->updata();
    }
    void rotate(SplayNode* v, bool sn) {
        SplayNode* f = v->fa;
        f->s[sn^1] = v->s[sn], v->fa = f->fa;
        if (f->s[sn^1]) f->s[sn^1]->fa = f;
        if (v->fa) v->fa->s[f == f->fa->s[1]] = v;
        v->s[sn] = f, f->fa = v, f->updata(), v->updata();
    }
    void splay(SplayNode* cur, SplayNode* tar) {
        while (cur != tar && cur->fa != tar) {
            bool sn = cur->fa->s[1] == cur;
            if flag rotate(cur->fa, sn^1);
            rotate(cur, sn^1);
        }
        if (cur->fa == tar) rotate(cur, cur->fa->s[0] == cur);
        if (tar == rt) rt = cur;
    }
    SplayNode* predecessor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val > cur->val])
            if (cur->val < _val) cpy = cur;
        return cpy;
    }
    SplayNode* successor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val >= cur->val])
            if (cur->val > _val) cpy = cur;
        return cpy;
    }
    void insert(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        if (suc->s[0]) suc->s[0]->w++, suc->s[0]->sz++;
        else suc->s[0] = newnode(_val), suc->s[0]->fa = suc;
        suc->updata(), rt->updata();
    }
    void remove(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        suc->s[0]->w--, suc->s[0]->sz--;
        if (!suc->s[0]->w) suc->s[0] = NULL;
        suc->updata(), rt->updata();
    }
    int get_rank(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        if (suc == NULL) return rt->sz;
        return rt->sz-suc->sz;
    }
    SplayNode* get_kth(SplayNode* v, int k) {
        int lsz = v->s[0] ? v->s[0]->sz : 0;
        if (k <= lsz) return get_kth(v->s[0], k);
        if (k > lsz+v->w) return get_kth(v->s[1], k-lsz-v->w);
        return v;
    }
} BBST;
int main() {
    int n, opt, x;
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &opt, &x);
        if (opt == 1)	BBST.insert(x);
        if (opt == 2)	BBST.remove(x);
        if (opt == 3)	printf("%d\n", BBST.get_rank(x));
        if (opt == 4)	printf("%d\n", BBST.get_kth(BBST.rt, x+1)->val);
        if (opt == 5)	printf("%d\n", BBST.predecessor(x)->val);
        if (opt == 6)	printf("%d\n", BBST.successor(x)->val);
    }
    return 0;
}

Reverse

#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
#define flag (cur->fa->fa!=tar&&cur->fa->fa->s[sn]==cur->fa)
using namespace std;
struct SplayNode {
    SplayNode *s[2], *fa;
    int val, w, sz;	bool rev;
    void updata() {sz = w+(s[0]?s[0]->sz:0)+(s[1]?s[1]->sz:0);}
    void downtag() {
        if (!rev) return;	rev = false, swap(s[0], s[1]);
        if (s[0]) s[0]->rev ^= 1;	if (s[1]) s[1]->rev ^= 1;
    }
};
struct SplayTree {
    SplayNode* rt;
    SplayNode* newnode(int _val) {
        SplayNode* v = new SplayNode;
        v->s[0] = v->s[1] = v->fa = NULL;
        v->val = _val, v->sz = v->w = 1;
        v->rev = false;	return v;
    }
    SplayTree(int n) {
        rt = newnode(-INF), rt->s[1] = newnode(INF);
        rt->s[1]->fa = rt, rt->updata();
        for (int i = 1; i <= n; i++) insert(i);
    }
    void rotate(SplayNode* v, bool sn) {
        SplayNode* f = v->fa;
        f->s[sn^1] = v->s[sn], v->fa = f->fa;
        if (f->s[sn^1]) f->s[sn^1]->fa = f;
        if (v->fa) v->fa->s[f == f->fa->s[1]] = v;
        v->s[sn] = f, f->fa = v, f->updata(), v->updata();
    }
    void splay(SplayNode* cur, SplayNode* tar) {
        while (cur != tar && cur->fa != tar) {
            bool sn = cur->fa->s[1] == cur;
            if flag rotate(cur->fa, sn^1);
            rotate(cur, sn^1);
        }
        if (cur->fa == tar) rotate(cur, cur->fa->s[0] == cur);
        if (tar == rt) rt = cur;
    }
    SplayNode* predecessor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val > cur->val])
            if (cur->val < _val) cpy = cur;
        return cpy;
    }
    SplayNode* successor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val >= cur->val])
            if (cur->val > _val) cpy = cur;
        return cpy;
    }
    void insert(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        if (suc->s[0]) suc->s[0]->w++, suc->s[0]->sz++;
        else suc->s[0] = newnode(_val), suc->s[0]->fa = suc;
        suc->updata(), rt->updata();
    }
    void reverse(int l, int r) {
        SplayNode *nl = get_kth(rt, l), *nr = get_kth(rt, r+2);
        splay(nl, rt), splay(nr, rt->s[1]), nr->s[0]->rev ^= 1;
    }
    SplayNode* get_kth(SplayNode* v, int k) {
        v->downtag();
        int lsz = v->s[0] == NULL ? 0 : v->s[0]->sz;
        if (k <= lsz) return get_kth(v->s[0], k);
        if (k > lsz+v->w) return get_kth(v->s[1], k-lsz-v->w);
        return v;
    }
    void output(SplayNode* v) {
        if (v == NULL) return;	v->downtag(), output(v->s[0]);
        if (v->val != -INF && v->val != INF) printf("%d ", v->val);
        output(v->s[1]);
    }
};
int main() {
    int n, m;	scanf("%d%d", &n, &m);	SplayTree BBST(n);
    for (int i = 1, l, r; i <= m; i++)	scanf("%d%d", &l, &r), BBST.reverse(l, r);
    return BBST.output(BBST.rt), 0;
}

Range Tree

#include <bits/stdc++.h>
#define MAX_N 200000
#define INF 2147483647
#define mid ((s+t)>>1)
#define flag (cur->fa->fa!=tar&&cur->fa->fa->s[sn]==cur->fa)
using namespace std;
int n, m, c[MAX_N+5];
struct SplayNode {
    SplayNode *s[2], *fa;	int val, w, sz;
    void updata() {sz = w+(s[0]?s[0]->sz:0)+(s[1]?s[1]->sz:0);}
};
struct SplayTree {
    SplayNode* rt;
    SplayNode* newnode(int _val) {
        SplayNode* v = new SplayNode;
        v->s[0] = v->s[1] = v->fa = NULL;
        v->val = _val, v->w = v->sz = 1;
        return v;
    }
    SplayTree() {
        rt = newnode(-INF), rt->s[1] = newnode(INF);
        rt->s[1]->fa = rt, rt->updata();
    }
    void rotate(SplayNode* v, bool sn) {
        SplayNode* f = v->fa;
        f->s[sn^1] = v->s[sn], v->fa = f->fa;
        if (f->s[sn^1]) f->s[sn^1]->fa = f;
        if (v->fa) v->fa->s[f == f->fa->s[1]] = v;
        v->s[sn] = f, f->fa = v, f->updata(), v->updata();
    }
    void splay(SplayNode* cur, SplayNode* tar) {
        while (cur != tar && cur->fa != tar) {
            bool sn = cur->fa->s[1] == cur;
            if flag rotate(cur->fa, sn^1);
            rotate(cur, sn^1);
        }
        if (cur->fa == tar) rotate(cur, cur->fa->s[0] == cur);
        if (tar == rt) rt = cur;
    }
    SplayNode* predecessor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val > cur->val])
            if (cur->val < _val) cpy = cur;
        return cpy;
    }
    SplayNode* successor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val >= cur->val])
            if (cur->val > _val) cpy = cur;
        return cpy;
    }
    void insert(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        if (suc->s[0]) suc->s[0]->w++, suc->s[0]->sz++;
        else suc->s[0] = newnode(_val), suc->s[0]->fa = suc;
        suc->updata(), rt->updata();
    }
    void remove(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        suc->s[0]->w--, suc->s[0]->sz--;
        if (!suc->s[0]->w) suc->s[0] = NULL;
        suc->updata(), rt->updata();
    }
    int get_rank(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        if (suc == NULL) return rt->sz-1;
        return rt->sz-suc->sz-1;
    }
} tr[(MAX_N<<2)+5];
void ins(int v, int s, int t, int p, int x) {
    tr[v].insert(x);	if (s == t) return;
    if (p <= mid) ins(v<<1, s, mid, p, x);
    else ins(v<<1|1, mid+1, t, p, x);
}
void modify(int v, int s, int t, int p, int x, int o) {
    tr[v].remove(o), tr[v].insert(x);	if (s == t) return;
    if (p <= mid) modify(v<<1, s, mid, p, x, o);
    else modify(v<<1|1, mid+1, t, p, x, o);
}
int query(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) return tr[v].get_rank(x);	int ret = 0;
    if (l <= mid) ret += query(v<<1, s, mid, l, r, x);
    if (r >= mid+1) ret += query(v<<1|1, mid+1, t, l, r, x);
    return ret;
}
int get_ind(int l, int r, int k) {
    int s = 0, t = INF, ret = -1;
    while (s <= t)
        if (query(1, 1, n, l, r, mid) >= k) t = mid-1;
        else ret = mid, s = mid+1;
    return ret;
}
int get_pre(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) return tr[v].predecessor(x)->val;	int ret = -INF;
    if (l <= mid) ret = max(ret, get_pre(v<<1, s, mid, l, r, x));
    if (r >= mid+1) ret = max(ret, get_pre(v<<1|1, mid+1, t, l, r, x));
    return ret;
}
int get_suc(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) return tr[v].successor(x)->val;	int ret = INF;
    if (l <= mid) ret = min(ret, get_suc(v<<1, s, mid, l, r, x));
    if (r >= mid+1) ret = min(ret, get_suc(v<<1|1, mid+1, t, l, r, x));
    return ret;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", c+i), ins(1, 1, n, i, c[i]);
    while (m--) {
        int opt, l, r, p, k, x;	scanf("%d", &opt);
        if (opt == 1) scanf("%d%d%d", &l, &r, &x), printf("%d\n", query(1, 1, n, l, r, x)+1);
        if (opt == 2) scanf("%d%d%d", &l, &r, &k), printf("%d\n", get_ind(l, r, k));
        if (opt == 3) scanf("%d%d", &p, &x), modify(1, 1, n, p, x, c[p]), c[p] = x;
        if (opt == 4) scanf("%d%d%d", &l, &r, &x), printf("%d\n", get_pre(1, 1, n, l, r, x));
        if (opt == 5) scanf("%d%d%d", &l, &r, &x), printf("%d\n", get_suc(1, 1, n, l, r, x));
    }
}

Heavy Path Decomposition

#include <iostream>
#include <cstdio>
#include <vector>
#define MAX_N 100000
using namespace std;
int n, m, r, p, ind;
vector <int> G[MAX_N+5];
int c[MAX_N+5];
int dep[MAX_N+5], fa[MAX_N+5], size[MAX_N+5], son[MAX_N+5];
int top[MAX_N+5], dfn[MAX_N+5], last[MAX_N+5];
int seg[(MAX_N<<2)+5], tag[(MAX_N<<2)+5];
void DFS1(int u) {
    size[u] = 1;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v == fa[u])	continue;
        dep[v] = dep[u]+1;
        fa[v] = u;
        DFS1(v);
        size[u] += size[v];
        if (!son[u] || size[son[u]] < size[v])	son[u] = v;
    }
}
void DFS2(int u, int tp) {
    top[u] = tp, dfn[u] = ++ind;
    if (son[u])	DFS2(son[u], tp);
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v == fa[u] || v == son[u])	continue;
        DFS2(v, v);
    }
    last[u] = ind;
}
void updata(int v) {seg[v] = (seg[v<<1]+seg[v<<1|1])%p;}
void downtag(int v, int s, int t) {
    if (!tag[v])	return;
    int mid = s+t>>1;
    seg[v<<1] = (seg[v<<1]+tag[v]*(mid-s+1))%p;
    seg[v<<1|1] = (seg[v<<1|1]+tag[v]*(t-mid))%p;
    tag[v<<1] = (tag[v<<1]+tag[v])%p;
    tag[v<<1|1] = (tag[v<<1|1]+tag[v])%p;
    tag[v] = 0;
}
void modify(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) {seg[v] = (seg[v]+x*(t-s+1))%p, tag[v] = (tag[v]+x)%p;	return;}
    downtag(v, s, t);
    int mid = s+t>>1;
    if (l <= mid)	modify(v<<1, s, mid, l, r, x);
    if (r >= mid+1)	modify(v<<1|1, mid+1, t, l, r, x);
    updata(v);
}
int query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r)	return seg[v];
    downtag(v, s, t);
    int mid = s+t>>1, ret = 0;
    if (l <= mid)	ret = (ret+query(v<<1, s, mid, l, r))%p;
    if (r >= mid+1)	ret = (ret+query(v<<1|1, mid+1, t, l, r))%p;
    updata(v);
    return ret;
}
void solve1(int x, int y, int z) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])	swap(x, y);
        modify(1, 1, n, dfn[top[x]], dfn[x], z);
        x = fa[top[x]];
    }
    modify(1, 1, n, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]), z);
}
int solve2(int x, int y) {
    int ret = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])	swap(x, y);
        ret = (ret+query(1, 1, n, dfn[top[x]], dfn[x]))%p;
        x = fa[top[x]];
    }
    ret = (ret+query(1, 1, n, min(dfn[x], dfn[y]), max(dfn[x], dfn[y])))%p;
    return ret;
}
void solve3(int x, int z) {modify(1, 1, n, dfn[x], last[x], z);}
int solve4(int x) {return query(1, 1, n, dfn[x], last[x]);}
int main() {
    scanf("%d%d%d%d", &n, &m, &r, &p);
    for (int i = 1; i <= n; i++)	scanf("%d", &c[i]);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    DFS1(r);
    DFS2(r, r);
    for (int i = 1; i <= n; i++)	modify(1, 1, n, dfn[i], dfn[i], c[i]);
    while (m--) {
        int opt;
        scanf("%d", &opt);
        if (opt == 1) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            solve1(x, y, z);
        }
        if (opt == 2) {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%d\n", solve2(x, y));
        }
        if (opt == 3) {
            int x, z;
            scanf("%d%d", &x, &z);
            solve3(x, z);
        }
        if (opt == 4) {
            int x;
            scanf("%d", &x);
            printf("%d\n", solve4(x));
        }
    }
    return 0;
}

Link-Cut Tree

#include <bits/stdc++.h>
#define MAX_N 300000
#define INF 0x7f7f7f7f
#define flag (!tar(cur->fa->fa)&&cur->fa->fa->s[sn]==cur->fa)
using namespace std;
struct SplayNode {
    SplayNode *s[2], *fa;	int val, sum;	bool rev;
    void updata() {sum = val^(s[0]?s[0]->sum:0)^(s[1]?s[1]->sum:0);}
    void downtag() {
        if (fa && (fa->s[0] == this || fa->s[1] == this)) fa->downtag();
        if (rev && s[0]) swap(s[0]->s[0], s[0]->s[1]), s[0]->rev ^= 1;
        if (rev && s[1]) swap(s[1]->s[0], s[1]->s[1]), s[1]->rev ^= 1;
        rev = false;
    }
} *tr[MAX_N+5];
struct LinkCutTree {
    SplayNode* newnode(int _val) {
        SplayNode* v = new SplayNode;
        v->s[0] = v->s[1] = v->fa = NULL;
        v->val = v->sum = _val, v->rev = 0;
        return v;
    }
    SplayNode* get_rt(SplayNode* v) {for (; v->fa; v = v->fa) ;	return v;}
    bool tar(SplayNode* v) {return (v&&v->fa==NULL)||(v&&v->fa->s[0]!=v&&v->fa->s[1]!=v);}
    LinkCutTree(int n) {for (int i=1,_val;i<=n;i++) scanf("%d", &_val), tr[i]=newnode(_val);}
    void rotate(SplayNode* v, bool sn) {
        SplayNode* f = v->fa;
        f->s[sn^1] = v->s[sn], v->fa = f->fa;
        if (f->s[sn^1]) f->s[sn^1]->fa = f;
        if (v->fa && !tar(f)) v->fa->s[f == f->fa->s[1]] = v;
        v->s[sn] = f, f->fa = v, f->updata(), v->updata();
    }
    void splay(SplayNode* cur) {
        cur->downtag();
        while (!tar(cur) && !tar(cur->fa)) {
            bool sn = cur->fa->s[1] == cur;
            if flag rotate(cur->fa, sn^1);
            rotate(cur, sn^1);
        }
        if (!tar(cur) && tar(cur->fa))
            rotate(cur, cur->fa->s[0] == cur);
        cur->updata();
    }
    void access(SplayNode* cur) {
        for (SplayNode* cpy = NULL; cur; cpy = cur, cur = cur->fa)
            splay(cur), cur->s[1] = cpy, cur->updata();
    }
    void mroot(SplayNode* v) {
        access(v), splay(v);
        swap(v->s[0], v->s[1]), v->rev ^= 1;
    }
    void link(SplayNode* u, SplayNode* v) {
        if (get_rt(u) == get_rt(v)) return;
        mroot(u), u->fa = v;
    }
    void cut(SplayNode* u, SplayNode* v) {
        if (u == v || get_rt(u) != get_rt(v)) return;
        mroot(u), access(v), splay(v);
        if (v->s[0] == u) u->fa = v->s[0] = NULL, v->updata();
    }
    void modify(SplayNode* v, int _val) {
        splay(v), v->val = _val, v->updata();
    }
    int query(SplayNode* u, SplayNode* v) {
        mroot(u), access(v), splay(v);
        return v->sum;
    }
};
int main() {
    int n, m;	scanf("%d%d", &n, &m);
    LinkCutTree LCT(n);
    while (m--) {
        int opt, x, y;	scanf("%d%d%d", &opt, &x, &y);
        if (opt == 0) printf("%d\n", LCT.query(tr[x], tr[y]));
        if (opt == 1) LCT.link(tr[x], tr[y]);
        if (opt == 2) LCT.cut(tr[x], tr[y]);
        if (opt == 3) LCT.modify(tr[x], y);
    }
    return 0;
}

String

Knuth-Morris-Pratt

#include <iostream>
#include <cstdio>
#include <string>
#define MAX_M 1000
using namespace std;
int next[MAX_M];
void CalcNext(string& s) {
    int m = s.length();
    int begin = 1, matched = 0;
    while (begin+matched < m) {
        if (s[begin+matched] == s[matched]) {
            matched++;
            next[begin+matched-1] = matched;
        } else {
            if (matched == 0) {
                begin++;
            } else {
                begin += matched-next[matched-1];
                matched = next[matched-1];
            }
        }
    }
}
void KMP(string& T, string& P) {
    int n = T.length(), m = P.length();
    int begin = 0, matched = 0;
    while (begin <= n-m) {
        if (matched < m && T[begin+matched] == P[matched]) {
            matched++;
            if (matched == m) {
                cout << begin+1 << endl;
            }
        } else {
            if (matched == 0) {
                begin++;
            } else {
                begin += matched-next[matched-1];
                matched = next[matched-1];
            }
        }
    }
}
int main() {
    string s1, s2;
    cin >> s1 >> s2;
    CalcNext(s2);
    KMP(s1, s2);
    for (int i = 0; i < s2.length(); i++) {
        cout << next[i] << " ";
    }
    return 0;
}

Manacher

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_L 11000000
using namespace std;
char s[MAX_L*2+5];
int f[MAX_L*2+5];
int manacher (char* s0) {
    int len = strlen(s0);
    for (int i = 0; i < len; i++)	s[i*2+1] = '#', s[i*2+2] = s0[i];
    s[len = len*2+1] = '#';
    int pos = 0, r = 0, ret = 0;
    for (int i = 1; i <= len; i++) {
        f[i] = (i < r) ? min(f[2*pos-i], r-i) : 1;
        while (i-f[i] >= 1 && i+f[i] <= len && s[i-f[i]] == s[i+f[i]])	f[i]++;
        if (i+f[i] > r)	pos = i, r = i+f[i];
        ret = max(ret, f[i]-1);
    }
    return ret;
}
int main() {
    char s0[MAX_L+5];	scanf("%s", s0);
    printf("%d\n", manacher(s0));
    return 0;
}

Aho-Corasick Automaton

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define DICNUM 26
#define MAX_LETTER 10500
#define MAX_LENGTH 1000000
using namespace std;
char P[155][75], T[MAX_LENGTH+5];
int root = 1, cnt, trie[MAX_LETTER+5][DICNUM], fail[MAX_LETTER+5], end[MAX_LETTER+5], tot[155];
void init() {
    memset(P, 0, sizeof(P)), memset(T, 0, sizeof(T)), memset(tot, 0, sizeof(tot));
    for (int i = 1; i <= cnt; i++)	memset(trie[i], 0, sizeof(trie[i])), fail[i] = end[i] = 0;	cnt = 1;
}
void insert(int id, char s[]) {
    int cur = 1, len = strlen(s);
    for (int i = 0; i < len; cur = trie[cur][s[i++]-'a'])
        if (!trie[cur][s[i]-'a'])	trie[cur][s[i]-'a'] = ++cnt;
    end[cur] = id;
}
void SetFail() {
    queue <int> que;	que.push(root);
    while (!que.empty()) {
        int u = que.front();	que.pop();
        for (int i = 0; i < DICNUM; i++)
            if (trie[u][i])	fail[trie[u][i]] = trie[fail[u]][i], que.push(trie[u][i]);
            else trie[u][i] = trie[fail[u]][i];
    }
}
void query() {
    int cur = root, index, len = strlen(T);
    for (int i = 0; i < len; i++) {
        index = T[i]-'a';
        while (!trie[cur][index])	cur = fail[cur];
        cur = trie[cur][index];
        for (int j = cur; j; j = fail[j])	tot[end[j]]++;
    }
}
int main() {
    int n;
    for (int i = 0; i < DICNUM; i++)	trie[0][i] = root;
    while (scanf("%d", &n) && n) {
        init();
        for (int i = 1; i <= n; i++)	scanf("%s", P[i]), insert(i, P[i]);
        SetFail(), scanf("%s", T), query();
        int ans = 0;
        for (int i = 1; i <= n; i++)	ans = max(ans, tot[i]);
        printf("%d\n", ans);
        for (int i = 1; i <= n; i++)	if (tot[i] == ans)	printf("%s\n", P[i]);
    }
    return 0;
}

Hash Table

#include <iostream>
#include <cstdio>
#include <string>
#define size 15000
using namespace std;
int n, cnt = 0;
string tmp;
string hash[size];
int calc(string& index) {
    int ret = 0;
    for (int i = 0; i < index.length(); i++) {
        ret = (ret*256+index[i]+128)%size;
    }
    return ret;
}
bool search(string& index, int& pos) {
    pos = calc(index);
    while (hash[pos] != "" && hash[pos] != index) {
        pos = (pos+1)%size;
    }
    if (hash[pos] == index) {
        return true;
    } else {
        return false;
    }
}
int insert(string& index) {
    int pos;
    if (search(index, pos)) {
        return 0;
    } else {
        hash[pos] = index;
        return 1;
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        cnt += insert(tmp);
    }
    cout << cnt << endl;
    return 0;
}

Suffix Array

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 1000000
using namespace std;
int n;    char ch[MAX_N+5];
int s[MAX_N+5], sa[MAX_N+5], tx[MAX_N+5], ty[MAX_N+5], cnt[MAX_N+5], rank[MAX_N+5];
int trans(char c) {
    if (c >= '0' && c <= '9')	return c-'0'+1;
    if (c >= 'A' && c <= 'Z')	return c-'A'+11;
    if (c >= 'a' && c <= 'z')	return c-'a'+37;
}
void getSA() {
    int *x = tx, *y = ty;	int DICNUM = 63;
    for (int i = 1; i <= n; i++)	cnt[x[i] = s[i]]++;
    for (int i = 2; i <= DICNUM; i++)	cnt[i] += cnt[i-1];
    for (int i = n; i; i--)	sa[cnt[x[i]]--] = i;
    for (int h = 1; h <= n; h <<= 1) {
        int c = 0;
        for (int i = n-h+1; i <= n; i++)	y[++c] = i;
        for (int i = 1; i <= n; i++)	if (sa[i] > h)	y[++c] = sa[i]-h;
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; i++)	cnt[x[i]]++;
        for (int i = 2; i <= DICNUM; i++)	cnt[i] += cnt[i-1];
        for (int i = n; i; i--)	sa[cnt[x[y[i]]]--] = y[i];
        swap(x, y), c = 0, x[sa[1]] = ++c;
        for (int i = 2; i <= n; i++)	x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+h] == y[sa[i-1]+h]) ? c : ++c;
        DICNUM = c;	if (c == n)	break;
    }
}
int main() {
    scanf("%s", ch);	n = strlen(ch);
    for (int i = 0; i < n; i++)	s[i+1] = trans(ch[i]);
    getSA();
    printf("%d", sa[1]);	for (int i = 2; i <= n; i++)	printf(" %d", sa[i]);
    return 0;
}

Suffix Automaton

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 1000000
using namespace std;
typedef long long lnt;
struct node {int ch[26], par, len;} SAM[MAX_N*2+500];
int sz, root, last, cnt[MAX_N*2+500], dfn[MAX_N*2+500], f[MAX_N*2+500];
int newnode(int _len) {SAM[++sz].len = _len;    return sz;}
void init() {sz = 0, root = last = newnode(0);}
void extend(int c) {
    int p = last, np = newnode(SAM[p].len+1);	last = np, f[np] = 1;
    for (; p && !SAM[p].ch[c]; p = SAM[p].par)	SAM[p].ch[c] = np;
    if (!p)	SAM[np].par = root;
    else {
        int q = SAM[p].ch[c];
        if (SAM[q].len == SAM[p].len+1)	SAM[np].par = q;
        else {
            int nq = newnode(SAM[p].len+1);
            memcpy(SAM[nq].ch, SAM[q].ch, sizeof(SAM[q].ch));
            SAM[nq].par = SAM[q].par, SAM[q].par = SAM[np].par = nq;
            for (; p && SAM[p].ch[c] == q; p = SAM[p].par)	SAM[p].ch[c] = nq;
        }
    }
}
int main() {
    char s[MAX_N+5];	init(), scanf("%s", s);	int l = strlen(s);
    for (int i = 0; i < l; i++)	extend(s[i]-'a');
    for (int i = 1; i <= sz; i++)	cnt[SAM[i].len]++;
    for (int i = 1; i <= l; i++)	cnt[i] += cnt[i-1];
    for (int i = 1; i <= sz; i++)	dfn[cnt[SAM[i].len]--] = i;
    lnt ans = 0;
    for (int i = sz; i >= 1; i--) {
        int p = dfn[i];	f[SAM[p].par] += f[p];
        if (f[p] > 1)	ans = max(ans, (lnt)f[p]*SAM[p].len);
    }
    printf("%lld", ans);
    return 0;
}