这个页面主要记录了作者的代码模板，同时也是作者成长的见证。

为了方便使用与迁移，本页面的所有算法均只包含函数，数据结构均使用 $\text{namespace}$ 进行封装。

其中，算法可以直接调用，数据结构请在调用之前添加下面的代码或者在调用时使用NAME :: Things()

using namespace NAME;

My Temple

试机程序

最简单的试机模板，可以用来检测编译器是否可以正常运行。

#include <cstdio>

using namespace std;

int main() {
    printf("Hello World");
    return 0;
}

#include <cstdio>

using namespace std;

int main() {
    int a , b; 
    scanf("%d%d" , &a , &b);
    printf("%d\n" , a + b);
    return 0;
}

数论 & 组合数学

Gcd & Lcm

使用欧几里得算法求最大公约数，时间复杂度 $O(\log a)$

int gcd(int a , int b){
    return !b ? a : gcd(b , a % b);
}

顺便求一下两个数的最小公倍数，公式为 $lcm(a , b) = \frac{a \times b}{gcd(a , b)}$。

int gcd(int a , int b){
    return !b ? a : gcd(b , a % b);
}

int lcm(int a , int b){
    return (a * b) / gcd(a , b);
}

Exgcd

使用扩展欧几里得算法求形如 $ax \equiv b \pmod p$ 的不定方程的一组整数解。

时间复杂度与欧几里得相同，也为 $O(\log a)$

void exgcd(int &x , int &y , int a , int b){
    if(b == 0){
        x = 1 , y = 0;
        return ;
    }
    exgcd(x , y , b , a % b);
    int tx = x; x = y , y = tx - a / b * y;
}

乘法逆元

乘法逆元的做法有两种，分别是费马小定理与线性递推。

其中，费马小定理的采用快速幂实现，时间复杂度为 $O(\log p)$ ，适合处理单个数的逆元。

const int HA = 998244353;

long long Pow(long long a , long long b){
    if(b == 0) return 1;
    if(b == 1) return a % HA;
    long long mid = Pow(a , b >> 1) % HA;
    if(b & 1) return mid * mid % HA * a % HA;
    else return mid * mid % HA;
}

long long get_inv(long long x){
    return Pow(x , HA - 2);
}

而线性递推法可以在 $O(n)$ 的时间内处理从 $1$ 到 $n$ 的所有数的逆元，很适合用来预处理逆元。

long long inv[100005] , n , HA;

inv[1] = 1;
for(int i = 2; i <= n; i ++){
    inv[i] = (HA - HA / i) * inv[HA % i] % HA;
}

还有一个更好记忆的版本

const int HA = 998244353;

long long inv[100005] , n;

long long Pow(long long a , long long b){
    if(b == 0) return 1;
    if(b == 1) return a % HA;
    long long mid = Pow(a , b >> 1) % HA;
    if(b & 1) return mid * mid % HA * a % HA;
    else return mid * mid % HA;
}

inv[n] = Pow(n , HA - 2);

for(int i = n; i >= 1; i --){
    inv[i - 1] = inv[i] * i % HA;
}

素数判定

可以在$O(\sqrt n)$的时间内判定一个数是否为质数。

bool ISPrime(int x){
    for(int i = 2; i * i <= x; i ++){
        if(x % i == 0) return 0;
    }
    return 1;
}

埃氏筛法

可以在 $O(\log \log n)$ 的时间内筛出从 $1$ 到 $n$ 的所有素数。

bool Prime[N];

void IS_Prime(int n){
    for(int i = 2; i <= n; i ++){
        Prime[i] = true;
    }
    for(int i = 2; i * i <= n; i ++){
        if(Prime[i]){
            for(int j = 2 * i; j < n; j += i) Prime[j] = false;
        }
    }
    return ;
}

欧拉筛

可以在严格 $O(n)$ 的时间内筛出从 $1$ 到 $n$ 的所有素数。

int a[N]; 
bool Prime[N];
int num = 0;

void IS_Prime(int n){
    for(int i = 2; i <= n; i ++){
        Prime[i] = true;
    }
    for(int i = 2; i * i <= n; i ++){
        if(Prime[i]){
            a[num ++] = i;
        }
        for(int j = 1; j <= num && i * a[j] < n; j ++){
            Prime[i * a[j]] = false;
            if(!(i % a[j])) break;
        }
    }
    return ;
}

组合数的计算

在 $O(k)$ 的时间内求出从 $n$ 个元素中选出 $k$ 种的方案数。

int C(int n , int k){
    int ans = 1;
    for(int i = 1; i <= k; i ++){
        ans = ans * (n - i + 1) / i;
    }
    return ans;
}

错排公式

在 $O(n)$ 的时间内算出 $n$ 个元素错位排列的方案数

int d[100001] , n , HA;   //d[i] i个元素错位排列的方案数

d[0] = 1 , d[2] = 1;

for(int i = 3; i <= n; i ++){
    d[i] = (i - 1) * (d[i - 1] + d[i - 2]) % HA;
}

组合数表

使用 $\text{Pascal}$ 公式在 $O(n^2)$ 的时间内打出组合数表

#define ll long long
#define N 1001

ll c[N][N];         //c[i][j]表示在i个数中选n个数的组合数
void get_num(int n){
    c[0][0] = 1;
    for(int i = 1; i <= n; i ++){
        c[i][0] = 1;
        for(int j = 1; j <= i; j ++){
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    }
}

Lucas定理

$C_{n}^{m} \bmod p = C_{n / p}^{m / p} \times C_{n \bmod p}^{m \bmod p} \bmod p$

ll Pow(ll a , ll b){
    if(b == 0) return 1;
    if(b == 1) return a;
    ll mid = Pow(a , b >> 1) % HA;
    if(b % 2 == 0){
        return mid * mid % HA;
    }
    else{
        return mid * mid % HA * a % HA;
    }
}

ll fac[M] , inv[M];

void prepare(){
    fac[0] = 1;
    rep(i , 1 , HA){
        fac[i] = fac[i - 1] * i % HA;
    }
}

ll C(ll n , ll m){
    if(n == 0 || m > n) return 0;
    else if(n == m) return 1;
    else{
        return 1ll * fac[n] % HA * Pow(fac[m] , HA - 2) % HA * Pow(fac[n - m] , HA - 2) % HA;
    }
}

ll Lucas(ll n , ll m , ll HA){
    if(!m) return 1;
    else{
        return 1ll * C(n % HA , m % HA) * Lucas(n / HA , m / HA , HA) % HA;
    }
}

数据结构

并查集

用来判断两个元素是否在一个集合中，也可以维护图的联通性。

在采用路径压缩时，查找与合并均为 $O(\log n)$。

使用前不要忘记初始化

int pre[100001];

int find(int root) {
    if(pre[root] == root) return root;
    else return pre[root] = find(pre[root]);
}

int start(int n) {
    for(int i = 1; i <= n; i ++) pre[i] = i;
}

树状数组

用于部分替代线段树的数据结构。

单点查询与单点修改均为 $O(\log n)$

namespace Tree_array{
    int tree[N];

    int lowbit(int x){ 
        return x & (- x); 
    }
    
    void add(int x , int val){
        for(int i = x; i <= n; i += lowbit(i)){
            tree[i] += val;
        }
    }
    int query(int x){
        int ans = 0;
        for(int i = x; i ; i -= lowbit(i)){
            ans += tree[i];
        }
        return ans;
    }
}

另外，树状数组可以用来求逆序对数，时间复杂度也为 $O(\log n)$

#define N 100001

int n , a[N] , b[N];

namespace Tree_array{
    int tree[N];

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

    void add(int x , int val){
        for(int i = x; i <= n; i += lowbit(i)){
            tree[i] += val;
        }
    }
    long long query(int x){
        long long ans = 0;
        for(int i = x; i ; i -= lowbit(i)){
            ans += tree[i];
        }
        return ans;
    }
}

namespace Solve{
    void input(){
        cin >> n;
        for(int i = 1; i <= n; i ++){
            cin >> a[i];
            b[i] = a[i];
        }
        sort(b + 1 , b + 1 + n);
        ll number = unique(b + 1 , b + 1 + n) - b - 1;
        for(int i = 1; i <= number; i ++){
            a[i] = lower_bound(b + 1 , b + 1 + n , a[i]) - b;
        }
    }

    long long main(){
        long long ans;
        input();
        for(int i = 1; i <= n; i ++){
            Tree_array :: add(a[i] , 1);
            ans += i - Tree_array :: query(a[i]);
        }
        return ans;
    }
}

线段树

用来维护一段序列的数据结构，主要利用了分治思想。

缺陷在于要维护的元素必须具有区间可加性。

建树的时间复杂度为 $O(n)$，其他操作均为 $O(\log n)$

//区间加 & 区间查询

namespace Segment_tree{
	#define lson(x) x << 1
	#define rson(x) x << 1 | 1

	ll a[N];

	struct Node{
		int num , add_tag;
	}node[N << 2];

	inline void pushup(int x){
		node[x].num = node[lson(x)].num + node[rson(x)].num;
	}

	inline void pushdown(int x , int l , int r){
		if(!node[x].add_tag) return ;
		int mid = (l + r) >> 1;
		node[lson(x)].add_tag += node[x].add_tag;
		node[lson(x)].num += node[x].add_tag * (mid - l + 1);
		node[rson(x)].add_tag += node[x].add_tag;
		node[rson(x)].num += node[x].add_tag * (r - mid);
		node[x].add_tag = 0;
	}

	void build(int x , int l , int r){
		if(l == r){
			node[x].num = a[l];
			return ;
		}
		int mid = (l + r) >> 1;
		build(lson(x) , l , mid);
		build(rson(x) , mid + 1 , r);
		pushup(x);
	}

	void range_add(int x , int l , int r , int ql , int qr , int add){
		if(ql <= l && r <= qr){
			node[x].add_tag += add;
			node[x].num += add * (r - l + 1);
			return ;
		}
		pushdown(x , l , r);
		int mid = (l + r) >> 1;
		if(ql <= mid){
			range_add(lson(x) , l , mid , ql , qr , add);
		}
		if(mid + 1 <= qr){
			range_add(rson(x) , mid + 1 , r , ql , qr , add);
		}
		pushup(x);
	}
	
	int range_query(int x , int l , int r , int ql , int qr){
		if(ql <= l && r <= qr){
			return node[x].num;
		}
		pushdown(x , l  , r);
		int ans = 0;
		int mid = (l + r) >> 1;
		if(ql <= mid){
			ans += range_query(lson(x) , l , mid , ql , qr);
		}
		if(mid + 1 <= qr){
			ans += range_query(rson(x) , mid + 1 , r , ql , qr);
		}
		return ans;
	}
}

//区间加 & 区间乘 & 区间查询

namespace Segment_tree{
    #define lson(x) x << 1
    #define rson(x) x << 1 | 1

    int a[N] , HA;

    struct Node{
        int num;
        int add_tag , mul_tag;
    }node[N << 2];

    I void pushup(int x){
        node[x].num = node[lson(x)].num + node[rson(x)].num;
        node[x].num %= HA;
    }

    void build(int x , int l , int r){
        node[x].mul_tag = 1;
        if(l == r){
            node[x].num = a[l] % HA;
            return ;
        }
        int mid = (l + r) >> 1;
        build(lson(x) , l , mid);
        build(rson(x) , mid + 1 , r);
        pushup(x);
    }

    void pushdown(int x , int l , int r){
        int mid = (l + r) >> 1;
        if(node[x].mul_tag != 1){
            node[lson(x)].mul_tag *= node[x].mul_tag;
            node[lson(x)].mul_tag %= HA;
            node[lson(x)].add_tag *= node[x].mul_tag;
            node[lson(x)].add_tag %= HA;
            node[lson(x)].num *= node[x].mul_tag;
            node[lson(x)].num %= HA;

            node[rson(x)].mul_tag *= node[x].mul_tag;
            node[rson(x)].mul_tag %= HA;
            node[rson(x)].add_tag *= node[x].mul_tag;
            node[rson(x)].add_tag %= HA;
            node[rson(x)].num *= node[x].mul_tag;
            node[rson(x)].num %= HA;
            node[x].mul_tag = 1;
        }
        if(node[x].add_tag){
            node[lson(x)].add_tag += node[x].add_tag;
            node[lson(x)].add_tag %= HA;
            node[lson(x)].num += node[x].add_tag * (mid - l + 1);
            node[lson(x)].num %= HA;

            node[rson(x)].add_tag += node[x].add_tag;
            node[rson(x)].add_tag %= HA;
            node[rson(x)].num += node[x].add_tag * (r - mid);
            node[rson(x)].num %= HA;
            node[x].add_tag = 0;
        }
        return ;
    }

    void range_add(int x , int l , int r , int ql , int qr , int val){
        if(ql <= l && r <= qr){
            node[x].add_tag += val;
            node[x].add_tag %= HA;
            node[x].num += val * (r - l + 1);
            node[x].num %= HA;
            return ;
        }
        pushdown(x , l , r);
        int mid = (l + r) >> 1;
        if(ql <= mid){
            range_add(lson(x) , l , mid , ql , qr , val);
        }
        if(mid + 1 <= qr){
            range_add(rson(x) , mid + 1 , r , ql , qr , val);
        }
        pushup(x);
    }

    void range_mul(int x , int l , int r , int ql , int qr , int val){
        if(ql <= l && r <= qr){
            node[x].mul_tag *= val;
            node[x].mul_tag %= HA;
            node[x].add_tag *= val;
            node[x].add_tag %= HA;
            node[x].num *= val;
            node[x].num %= HA;
            return ;
        }
        int mid = (l + r) >> 1;
        pushdown(x , l , r);
        if(ql <= mid){
            range_mul(lson(x) , l , mid , ql , qr , val);
        }
        if(mid + 1 <= qr){
            range_mul(rson(x) , mid + 1 , r , ql , qr ,val);
        }
        pushup(x);
    }

    int range_query(int x , int l , int r , int ql , int qr){
        if(ql <= l && r <= qr){
            return node[x].num % HA;
        }
        pushdown(x , l , r);
        int ans = 0;
        int mid = (l + r) >> 1;
        if(ql <= mid){
            ans += range_query(lson(x) , l  ,mid , ql , qr);
            ans %= HA;
        }
        if(mid + 1 <= qr){
            ans += range_query(rson(x) , mid + 1 , r , ql , qr);
            ans %= HA;
        }
        return ans % HA;
    }

}

Trie树

字典树，时间复杂度为 $O(|s|)$

namespace Trie{
    struct Node{
        int son[27] , cnt , size;
    }node[N];

    int tot;

    void insert(string s){
        int len = s.length() , rt = 0;
        for(int i = 0; i < len; i ++){
            int c = s[i] - 'a';
            if(!node[rt].son[c]){
                node[rt].son[c] = ++ tot;
            }
            rt = node[rt].son[c];
            node[rt].size ++;
        }
        node[rt].cnt ++;
    }

    int find(string s){
        int len = s.length() , rt = 0;
        for(int i = 0; i < len; i ++){
            int c = s[i] - 'a';
            if(!node[rt].son[c]){
                return 0;
            }
            rt = node[rt].son[c];
        }
        return node[rt].cnt;
    }

    int get(string s){
        int len = s.length() , rt = 0;
        for(int i = 0; i < len; i ++){
            int c = s[i] - 'a';
            if(!node[rt].son[c]){
                return 0;
            }
            rt = node[rt].son[c];
        }
        return node[rt].size;
    }
}

ODT

即珂朵莉树，原理依托于区间推平操作，无稳定复杂度。但在数据随机的情况下具有良好效果。

namespace ODT{
    int n , m , s;
    int a[N];

    struct Node {
        int l , r;
        mutable int val;
        bool operator < (const Node &b) const {
            return l < b.l;
        }
    };                       

    set<Node> S; 

    void build(int n){
        for(int i = 1; i <= n; i ++){
            S.insert(Node{i , i , a[i]});
        }
    }

    set<Node>::iterator spilt(int pos){
        set<Node>::iterator it = S.lower_bound((Node){pos , pos , -1});
        if(it != S.end() && it -> l == pos){
            return it;
        }
        it --;
        Node ins = *it;
        S.erase(it);
        S.insert((Node){ins.l , pos - 1 , ins.val});
        return S.insert((Node){pos , ins.r , ins.val}).first;
    }

    void assign(int l  , int r , int val){
        set<Node>::iterator R = spilt(r + 1);
        set<Node>::iterator L = spilt(l);
        S.erase(L , R);
        S.insert(Node{l , r , val});
    }

    void range_add(int l , int r , int val){
        set<Node>::iterator R = spilt(r + 1);
        set<Node>::iterator L = spilt(l);
        for(set<Node>::iterator i = L; i != R; i ++){
            i -> val += val;
        }
    }

    int Pow(int a , int n , int HA){
        if(n == 0) return 1;
        if(n == 1) return a % HA;
        int c = Pow(a , n / 2 , HA) % HA;
        if(n % 2 == 0)
            return (c * c) % HA;
        else
            return  (((c * c) % HA) * a) % HA;
    }

    int range_pow(int l , int r , int val , int HA){
        set<Node>::iterator R = spilt(r + 1);
        set<Node>::iterator L = spilt(l);
        int ans = 0;
        for(set<Node>::iterator i = L; i != R; i ++){
            ans += (int)(i -> r - i -> l + 1) * Pow(i -> val , val , HA);
            ans %= HA;
        }
        return ans;
    }

    int range_query(int l , int r , int k){
        #define pairs pair<int , int>

        vector<pairs> V;
        V.clear();
        
        set<Node>::iterator R = spilt(r + 1);
        set<Node>::iterator L = spilt(l);
        for(set<Node>::iterator i = L; i != R; i ++){
            V.push_back(pairs(i -> val , i -> r - i -> l + 1));
        } 
        sort(V.begin() , V.end());
        int sum = 0;
        for(vector<pairs> :: iterator i = V.begin(); i != V.end(); i ++){
            sum += i -> second;
            if(sum >= k){
                return i -> first;
            }
        }
        return -1;

        #undef pairs
    }
}

左偏树

即可并堆，可以快速合并两个优先队列。

插入和弹出的复杂度均为 $O(\log n)$，获取堆顶元素为 $O(1)$，合并为 $O(\log n_1 + \log n_2)$

namespace Left_tree{
    #define lson(x) node[x].l
    #define rson(x) node[x].r

    struct Node{
    	int pre , dis , far;	
    	int l , r;	
    }node[N];

    int find(int root){			
    	if(node[root].pre == root) return root;				
    	else return node[root].pre = find(node[root].pre);		
    	
    }

    int merge(int x , int y){
    	if(!x || !y) return x + y ;
    	if(node[x].dis > node[y].dis) swap(x , y);
    	node[x].r = merge(rson(x) , y);	
    	node[rson(x)].pre = x;				
    	if(node[lson(x)].far < node[rson(x)].far){	
    		swap(lson(x) , rson(x));					
    	}
    	node[x].far = node[rson(x)].far + 1;				
    	return x;
    }

    void pop(int x){
    	int l = lson(x) , r = rson(x);
    	node[x].dis = -1;			
    	node[l].pre = l , node[r].pre = r;
    	node[x].pre = merge(l , r);	
    }
}

Fhq_treap

非旋Treap，不用旋转的平衡树。

具有插入，删除，查询某个数的排名，寻找排名为 $i$ 的数，查询前驱，后继六种操作，时间复杂度均为 $O(\log n)$，是一种很高效的数据结构。

namespace Treap{
    #define lson(x) node[x].l
    #define rson(x) node[x].r

    int cnt , root;
    
    struct Node{
        int dis , size , rd;
        int l , r;
        Node(int dis = 0) : dis(dis) , size(1) , rd(rand()) , l(0) , r(0) {};
    }node[N];

    inline void update(int x){
        node[x].size = (lson(x) ? node[lson(x)].size : 0) + (rson(x) ? node[rson(x)].size : 0) + 1;
    }

    void spilt(int n , int k , int &x , int &y){
        if(!n) x = y = 0;
        else if(node[n].dis >= k){
            spilt(lson(n) , k , x , y);
            lson(n) = y; update(y = n);
        }
        else{
            spilt(rson(n) , k , x , y);
            rson(n) = x; update(x = n);
        }
    }

    int merge(int x , int y){
        if(!x || !y) return x + y;
        if(node[x].rd < node[y].rd){
            rson(x) = merge(rson(x) , y);
            update(x); return x;
        }
        else{
            lson(y) = merge(x , lson(y));
            update(y); return y;
        }
    }

    void insert(int k){
        int x , y;
        spilt(root , k , x , y);
        node[++ cnt] = Node(k);
        root = merge(merge(x , cnt) , y);
    }

    void remove(int k){
        int x , y , z;
        spilt(root , k , x , y);
        spilt(y , k + 1 , y , z);
        y = merge(lson(y) , rson(y));
        root = merge(merge(x , y) , z);
    }

    int rank(int k){
        int x , y , ans;
        spilt(root , k , x , y);
        ans = (x ? node[x].size : 0) + 1;
        root = merge(x , y);
        return ans;
    }

    int search(int x , int r){
        int rank = (lson(x) ? node[lson(x)].size : 0) + 1;
        if(r == rank) return node[x].dis;
        else if(r < rank) return search(lson(x) , r);
        else return search(rson(x) , r - rank);
    }

    inline int lower(int k){
        int x , y , t;
        spilt(root , k , x ,  y);
        t = x;
        while(rson(t)) t = rson(t);
        root = merge(x , y);
        return node[t].dis;
    }

    inline int upper(int k){
        int x , y , t;
        spilt(root , k + 1, x , y);
        t = y;
        while(lson(t)) t = lson(t);
        root = merge(x , y);
        return node[t].dis;
    }

}

图论

Floyd

多源最短路算法，原理为动态规划，时间复杂度为 $O(n^3)$

int n , m;
int f[N][N];

void Floyd(){
    for(int k = 1; k <= n; k ++){
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= n; j ++){
                f[i][j] = min(f[i][j] , f[i][k] + f[k][j]);
            }
        }
    }
}

Dijkstra

稳定的多源最短路算法，朴素版本的时间复杂度为 $O(n^2)$，可以通过堆优化降至 $O(n \log(n + m))$

这里只给出堆优化版本

#define PII pair<int , int>

int dis[100001];
bool vis[100001];

void Dijkstra(int sta){
    priority_queue<PII , vector<PII> , greater<PII> > Q;

    memset(vis , 0 , sizeof(vis)); 
    memset(dis , 0x3f3f3f3f , sizeof(dis));

    dis[sta] = 0;
    Q.push(make_pair(dis[sta] , sta));
    while(!Q.empty()){
        int fro = Q.top().second; Q.pop();
        if(vis[fro]) continue;
        for(int i = head[fro]; i; i = edge[i].last){
            int to = edge[i].to;
            if(dis[to] > dis[fro] + edge[i].dis){
                dis[to] = dis[fro] + edge[i].dis;
                Q.push(make_pair(dis[to] , to));
            }
        }
    }
}

SPFA

不稳定的多源最短路算法，时间复杂度为 $O(k \times m)$, 其中，$k$ 为每个元素的平均入队次数，一般为 $2$，但可以通过数据构造卡至 $n$

极其不建议考场使用，但在判定负环时具有不可代替的作用。

int dis[100001];
bool vis[100001];

void SPFA(int sta){
	queue<int> q;

    memset(dis , 1e9 , sizeof(dis));
    memset(vis , 0 , sizeof(vis));

    dis[sta] = 0; 
    q.push(sta); vis[sta] = 1;
    while(!q.empty()){
        int fro = q.front(); q.pop();
        vis[fro] = false;
        for(int i = hend[fro]; i ; i = edge[i].last){
            int to = edge[i].to;
            if(dis[to] > dis[fro] + edge[i].dis){
            	dis[to] = dis[fro] + edge[i].dis;
                if(!vis[to]){
                    vis[to] = 1; 
                    q.push(edge[i].to);
                }
            }
        }
    }
}

Kruskal

最小生成树算法，时间复杂度为 $O(n \log n)$

int Kruskal(){
    for(int i = 1; i <= n; i ++){
        pre[i] = i;
    }
    int num , ans;
    sort(edge + 1 , edge + 1 + m , cmp);
    for(int i = 1; i <= m; i ++){
        int l = find(edge[i].from); r = find(edge[i].to);
        if(l == r) continue;
        ans += edge[i].dis;
        pre[l] = r; num ++;
        if(num == n - 1) break;
    }
    return ans;
}

Tarjan(割点)

使用 $\text{Tarjan}$ 算法求割点，时间复杂度为 $O(n)$

int dfn[N] , low[N] , cnt;
bool cut[N];

inline void Tarjan(int x , int fa){
    dfn[x] = low[x] = ++ cnt;
    int child = 0;
    for(int i = hend[x]; i ; i = edge[i].last){
        int to = edge[i].to;
        if(!dfn[to]){
            Tarjan(to , fa);
            low[x] = min(low[x] , low[to]);
            if(low[to] > dfn[x] && x != fa) cut[x] = 1;
        }
        if(x == fa) child ++;
        low[x] = min(low[x] , dfn[to]);
    }
    if(child >= 2 && x == fa) cut[x] = true;
}

LCA

倍增求最近公共祖先。

预处理为 $O(n \log n)$，每一次查询为 $O(\log n)$

namespace LCA{
    int fa[N][22];
    int dep[N];

    void search(int x){
        for(int i = head[x]; i ; i = edge[i].last){
            int to = edge[i].to;
            if(to == fa[x][0]) continue;
            fa[to][0] = x;
            dep[to] = dep[x] + 1;
            search(to);
        }
    }

    void build(){
        for(int j = 1; j <= log2(n); j ++){
            for(int i = 1; i <= n; i ++){
                fa[i][j] = fa[fa[i][j - 1]][j - 1];
            }
        }
    }

    int LCA(int x , int y){
        if(dep[x] < dep[y]) swap(x , y);
        while(dep[x] > dep[y]){
            x = fa[x][(int )log2(dep[x] - dep[y])];
        }
        if(x == y) return x;
        for(int i = log2(dep[x]); i >= 0; i --){
            if(dep[x] != dep[y]){
                x = fa[x][i];
                y = fa[y][i];
            }
        }
        return fa[x][0];
    }
}

Others

竞赛模板

作者常用的考场代码模板，采用宏定义的方式定义了一些常见的代码写法，熟练使用可以大幅度提高编码速度。

#include <bits/stdc++.h>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif


    return 0;
}

快速读入

比赛用

比赛常用的快读版本，可以读入所有整数类，且在实现快速读入的同时尽量减少了代码量，便于记忆。

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

工业用

工业代码中常用的快速读入，最大化的减少了读入的时间。

namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf , *its = ibuf;
    char obuf[BUFSIZE],*os = obuf , *ot = obuf + BUFSIZE;

    inline char getch(){
        if(is == its)
            its = (is = ibuf) + fread(ibuf , 1 , BUFSIZE , stdin);
        return (is == its) ? EOF : *is++;
    }

    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg ? - res : res;
    }

    inline void flush(){
        fwrite(obuf , 1 , os - obuf , stdout);
        os = obuf;
    }

    inline void putch(char ch){
        *os ++ = ch;
        if(os == ot)	flush();
    }

    inline void putint(int res){
        static char q[10];
        if(res == 0) putch('0');
        else if(res < 0){ putch('-'); res = -res; }
        int top = 0;
        while(res){
            q[top ++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }

    inline void space(bool x){
        if(!x) putch('\n');
        else putch(' ');
    }
}

inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}

inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}

对拍

此版本为 $\text{Windows}$ 下的对拍原码，使用 $\text{Mac OS}$ 或 $\text{Linux}$ 的读者请自行查找适用于自己系统的对拍代码

考场不对拍，爆零两行泪。

#include <bits/stdc++.h>
#include <windows.h>

using namespace std;

int num , s , t;

int main(){
	while(1){
		system("cls");
		do{
			num ++; system("data.exe");
			s = clock(); system("a.exe");
			t = clock(); system("b.exe");
			if(system("fc try1.out try2.out")) break;
			else{
                printf("AC on text #%d , time is %d\n" , num , t - s);
			}
		}while(true);
        printf("WA on text #%d , time is %d\n" , num , t - s);
		system("fc try1.out try2.out");
        system("pause > nul");
	}
	return 0;
}

模板墙