模板

Part 0

头文件

#include<bits/stdc++.h>
using namespace std;
int main(){
    return 0;
}

快读版

#include<bits/stdc++.h>
using namespace std;
int read(){int ans = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ans *= 10;ans += ch - '0';ch = getchar();}return ans * f;}
void write(int x){if(x < 0){putchar('-');write(-x);return;}else if(x < 10){putchar(x + '0');}else if(x >= 10){write(x / 10);putchar(x % 10 + '0');}}
int main(){
	return 0;
}

快读

void read(int &ans){
	ans = 0;
	int f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9'){
		ans *= 10;
		ans += ch - '0';
		ch = getchar();
	}
}

void write(int x){
	if(x < 0){
		putchar('-');
		write(-x);
		return;
	}
	else if(x < 10){
		putchar(x + '0');
	}
	else if(x >= 10){
		write(x / 10);
		putchar(x % 10 + '0');
	}
}

Part 1 图论

建图

const int N = 1e5 + 10;
#define Son for(int i = G.hd[u], v = G.e[i].to, w = G.e[i].w; i; i = G.e[i].nt, v = G.e[i].to, w = G.e[i].w)
#define PII pair<int, int>
struct edge{
    int nt, to, w;
};
struct Graph{
    int hd[N], cnt;
    edge e[N * 2];
    Graph(){
        memset(hd, 0, sizeof(hd));
        cnt = 0;
    }
    void add(int x, int y){
        e[++cnt].nt = hd[x];
        hd[x] = cnt;
        e[cnt].to = y;
    }
    void add(int x, int y, int z){
        e[++cnt].nt = hd[x];
        hd[x] = cnt;
        e[cnt].to = y;
        e[cnt].w = z;
    }
}G;

const int N = 1e5 + 10;
#define Son for(int i = G.hd[u], v = G.e[i].to, w = G.e[i].w; i; i = G.e[i].nt, v = G.e[i].to, w = G.e[i].w)
#define PII pair<int, int>
struct edge{int nt, to, w;};
struct Graph{
    int hd[N], cnt;edge e[N * 2];
    Graph(){memset(hd, 0, sizeof(hd));cnt = 0;}
    void add(int x, int y){e[++cnt].nt = hd[x];hd[x] = cnt;e[cnt].to = y;}
    void add(int x, int y, int z){e[++cnt].nt = hd[x];hd[x] = cnt;e[cnt].to = y;e[cnt].w = z;}
}G;

倍增LCA

int f[N][32], dep[N];
void dfs(int u, int fa){
    Son{
        if(v == fa) continue;
        f[v][0] = u;
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}

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

int main(){
    for(int i = 1; i <= 30; i++){
        for(int j = 1; j <= n; j++){
            f[j][i] = f[f[j][i - 1]][i - 1];
        }
    }
    return 0;
}

树链剖分

int son[N], siz[N], top[N], dep[N];
int f[N];
int dfn[N], L[N], R[N], cntl;
void dfs1(int u, int F){
	siz[u] = 1;
	Son{
		if(v == F) continue;
		dep[v] = dep[u] + 1;
		f[v] = u;
		dfs1(v, u);
		if(siz[v] > siz[son[u]] || son[u] == 0) son[u] = v;
		siz[u] += siz[v];
	}
}
void dfs2(int u, int F, int tp){
	dfn[++cntl] = u;
	L[u] = cntl;
	top[u] = tp;
	if(son[u]) dfs2(son[u], u, tp);
	Son{
		if(v == F || v == son[u]) continue;
		dfs2(v, u, v);
	}
	R[u] = cntl;
}
int ask(int x, int y){

	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]]) swap(x, y);

		x = f[top[x]], top[x] = top[x];
	}
	if(dep[x] > dep[y]) swap(x, y);

}

Part 3 数论

快速幂

int ksm(int a, int b, int p){
	int ans = 1;
	a %= p;
	while(b){
		if(b & 1){
			(ans *= a) %= p;
		}
		(a *= a) %= p;
		b >>= 1;
	}
	return ans % p;
}

高精度运算

struct gjd{
    int n, a[N];
    gjd(){
        n = 0;
        for(int i = 0; i < N; i++){
            a[i] = 0;
        }
    }
    
};
gjd operator+(gjd a, gjd b){
    gjd c;
    c.n = max(a.n, b.n);
    for(long long i = 1; i <= c.n; i++){
        c.a[i] += a.a[i] + b.a[i];
        if(c.a[i] >= 10){
            c.a[i + 1]++;
        }
        c.a[i] %= 10;
    }
    if(c.a[c.n + 1] != 0){
        c.n++;
    }
    return c;
}
gjd operator*(gjd a, int b){
    gjd c;
    c.n = a.n;
    for(int i = 1; i <= c.n; i++){
        c.a[i] = a.a[i] * b;
    }
    for(int i = 1; i <= c.n; i++){
        c.a[i + 1] += c.a[i] / 10;
        c.a[i] %= 10;
    }
    while(c.a[c.n + 1] != 0){
        c.n++;
        c.a[c.n + 1] += c.a[c.n] / 10;
        c.a[c.n] %= 10;
    }
    return c;
}
gjd readgjd(){
    gjd c;
    char s[N];
    scanf("%s", s + 1);
    c.n = strlen(s + 1);
    for(long long i = 1; i <= c.n; i++){
        c.a[c.n - i + 1] = s[i] ^ 48;
    }
    return c;
}
void print(gjd c){
    for(long long i = c.n; i >= 1; i--){
        printf("%d", c.a[i]);
    }
}

Part 4 数据结构

树状数组

struct BIT{
    int sum[N];
    BIT(){
        memset(sum, 0, sizeof(sum));
    }
    int lobit(int x){
        return x & -x;
    }
    void add(int x, int y){
        while(x <= n){
            sum[x] += y;
            x += lobit(x);
        }
    }
    int ask(int x){
        int ans = 0;
        while(x >= 1){
            ans += sum[x];
            x -= lobit(x);
        }
        return ans;
    }
}a;

线段树（区间加，区间和）

struct STree{
    int sum[N * 4], la[N * 4];
    void put_down(int l, int r, int rt){
        int Lson = rt << 1, Rson = (rt << 1) + 1, Mid = (l + r) >> 1;
        sum[Lson] += la[rt] * (Mid - l + 1);
        la[Lson] += la[rt];
        sum[Rson] += la[rt] * (r - Mid);
        la[Rson] += la[rt];
        la[rt] = 0;
    }
    void build(int l, int r, int rt){
        if(l == r){
            scanf("%lld", &sum[rt]);
            return;
        }
        int Lson = rt << 1, Rson = (rt << 1) + 1, Mid = (l + r) >> 1;
        build(l, Mid, Lson), build(Mid + 1, r, Rson);
        sum[rt] = sum[Lson] + sum[Rson];
    }
    void add(int l, int r, int rt, int x, int y, int z){
        if(l > y || r < x) return;
        if(l >= x && r <= y){
            sum[rt] += z * (r - l + 1);
            la[rt] += z;
            return;
        }
        int Lson = rt << 1, Rson = (rt << 1) + 1, Mid = (l + r) >> 1;
        put_down(l, r, rt);
        add(l, Mid, Lson, x, y, z), add(Mid + 1, r, Rson, x, y, z);
        sum[rt] = sum[Lson] + sum[Rson];
    }
    int ask(int l, int r, int rt, int x, int y){
        if(l > y || r < x) return 0;
        if(l >= x && r <= y){
            return sum[rt];
        }
        int Lson = rt << 1, Rson = (rt << 1) + 1, Mid = (l + r) >> 1;
        put_down(l, r, rt);
        return ask(l, Mid, Lson, x, y) + ask(Mid + 1, r, Rson, x, y);
    }
}a;

线段树（区间加，区间覆盖，区间和，区间最大值）

struct STree{
    int sum[N * 4], la[N * 4], smax[N * 4], cola[N * 4], bj[N * 4];
    void put_down(int l, int r, int rt){
        int Lson = rt << 1, Rson = (rt << 1) + 1, Mid = (l + r) >> 1;
        if(bj[rt]){
            sum[Lson] = cola[rt] * (Mid - l + 1);
            smax[Lson] = cola[rt];
            bj[Lson] = 1, cola[Lson] = cola[rt];
            la[Lson] = 0;
            sum[Rson] = cola[rt] * (r - Mid); 
            smax[Rson] = cola[rt];
            bj[Rson] = 1, cola[Rson] = cola[rt];
            la[Rson] = 0;
            cola[rt] = 0;
            bj[rt] = 0;
        }
        sum[Lson] += la[rt] * (Mid - l + 1);
        smax[Lson] += la[rt];
        la[Lson] += la[rt];
        sum[Rson] += la[rt] * (r - Mid);
        smax[Rson] += la[rt];
        la[Rson] += la[rt];
        la[rt] = 0;
    }
    void build(int l, int r, int rt){
        bj[rt] = 0;
        if(l == r){
            scanf("%lld", &sum[rt]);
            smax[rt] = sum[rt];
            la[rt] = 0;
            cola[rt] = 0;
            return;
        }
        int Lson = rt << 1, Rson = (rt << 1) + 1, Mid = (l + r) >> 1;
        build(l, Mid, Lson), build(Mid + 1, r, Rson);
        sum[rt] = sum[Lson] + sum[Rson];
        smax[rt] = max(smax[Lson], smax[Rson]);
    }
    void add(int l, int r, int rt, int x, int y, int z){
        if(l >= x && r <= y){
            sum[rt] += z * (r - l + 1);
            smax[rt] += z;
            la[rt] += z;
            return;
        }
        int Lson = rt << 1, Rson = (rt << 1) + 1, Mid = (l + r) >> 1;
        put_down(l, r, rt);
        if(x <= Mid) add(l, Mid, Lson, x, y, z);
        if(y > Mid) add(Mid + 1, r, Rson, x, y, z);
        sum[rt] = sum[Lson] + sum[Rson];
        smax[rt] = max(smax[Lson], smax[Rson]);
    }
    int ask(int l, int r, int rt, int x, int y){
        if(l >= x && r <= y){
            return sum[rt];
        }
        int Lson = rt << 1, Rson = (rt << 1) + 1, Mid = (l + r) >> 1;
        put_down(l, r, rt);
        int ans = 0;
        if(x <= Mid) ans += ask(l, Mid, Lson, x, y);
        if(y > Mid) ans += ask(Mid + 1, r, Rson, x, y);
        return ans;
    }
    int Max(int l, int r, int rt, int x, int y){
        if(l >= x && r <= y){
            return smax[rt];
        }
        int Lson = rt << 1, Rson = (rt << 1) + 1, Mid = (l + r) >> 1;
        put_down(l, r, rt);
        int ans = -1e18;
        if(x <= Mid) ans = max(ans, Max(l, Mid, Lson, x, y));
        if(y > Mid) ans = max(ans, Max(Mid + 1, r, Rson, x, y));
        return ans;
    }
    void cover(int l, int r, int rt, int x, int y, int z){
        if(l >= x && r <= y){
            sum[rt] = z * (r - l + 1);
            cola[rt] = z;
            smax[rt] = z;
            bj[rt] = 1;
            la[rt] = 0;
            return;
        }
        put_down(l, r, rt);
        int Lson = rt << 1, Rson = (rt << 1) + 1, Mid = (l + r) >> 1;
        if(x <= Mid) cover(l, Mid, Lson, x, y, z);
        if(y > Mid) cover(Mid + 1, r, Rson, x, y, z);
        sum[rt] = sum[Lson] + sum[Rson];
        smax[rt] = max(smax[Lson], smax[Rson]);
    }
}a;

权值线段树

[普通平衡树](https://www.luogu.com.cn/problem/P3369

struct STree{
    int sum[N * 30], Ls[N * 30], Rs[N * 30], cnt = 1;
    void update(int l, int r, int rt){
        sum[rt] = sum[Ls[rt]] + sum[Rs[rt]];
    }
    void add(int l, int r, int &rt, int x, int y){
        if(!rt) rt = ++cnt;
        if(l == r){
            sum[rt] += y;
            return;
        }
        int Mid = (l + r) >> 1;
        if(x <= Mid) add(l, Mid, Ls[rt], x, y);
        else add(Mid + 1, r, Rs[rt], x, y);
        update(l, r, rt);
    }
    int ask(int l, int r, int rt, int x, int y){
        if(x <= l && r <= y){
            return sum[rt];
        }
        int ans = 0;
        int Mid = (l + r) >> 1;
        if(x <= Mid) ans += ask(l, Mid, Ls[rt], x, y);
        if(y > Mid) ans += ask(Mid + 1, r, Rs[rt], x, y);
        return ans;
    }
    int FoMax(int l, int r, int rt){
        if(l == r) return l;
        int Mid = (l + r) >> 1;
        if(sum[Rs[rt]]) return FoMax(Mid + 1, r, Rs[rt]);
        else return FoMax(l, Mid, Ls[rt]);
    }
    int FoMin(int l, int r, int rt){
        if(l == r) return l;
        int Mid = (l + r) >> 1;
        if(sum[Ls[rt]]) return FoMin(l, Mid, Ls[rt]);
        else return FoMin(Mid + 1, r, Rs[rt]);
    }
    int Max(int l, int r, int rt, int x){
        int Mid = (l + r) >> 1;
        if(r < x){
            if(sum[rt]){
                return FoMax(l, r, rt);
            }
            else{
                return 0;
            }
        }
        if(x > Mid + 1 && sum[Rs[rt]]){
            int ans = Max(Mid + 1, r, Rs[rt], x);
            if(ans) return ans;
        }
        return Max(l, Mid, Ls[rt], x);
    }
    int Min(int l, int r, int rt, int x){
        int Mid = (l + r) >> 1;
        if(l > x){
            if(sum[rt]){
                return FoMin(l, r, rt);
            }
            else{
                return 0;
            }
        }
        if(x <= Mid && sum[Ls[rt]]){
            int ans = Min(l, Mid, Ls[rt], x);
            if(ans) return ans;
        }
        return Min(Mid + 1, r, Rs[rt], x);
    }
    int kth(int l, int r, int rt, int x){
        if(l == r){
            return l;
        }
        int Mid = (l + r) >> 1;
        if(x <= sum[Ls[rt]]){
            return kth(l, Mid, Ls[rt], x);
        }
        else{
            return kth(Mid + 1, r, Rs[rt], x - sum[Ls[rt]]);
        }
    }
}a;

线段树合并

struct STree{
    int sum[M], Ls[M], Rs[M], cnt;
    int mx[M], k[M];
    void update(int l, int r, int rt){
        sum[rt] = sum[Ls[rt]] + sum[Rs[rt]];
        mx[rt] = max(mx[Ls[rt]], mx[Rs[rt]]);
        k[rt] = mx[Ls[rt]] >= mx[Rs[rt]] ? k[Ls[rt]] : k[Rs[rt]];
    }
    void add(int l, int r, int &rt, int x, int y){
        if(!rt) rt = ++cnt;
        if(l == r){
            sum[rt] += y;
            mx[rt] += y;
            k[rt] = l;
            return;
        }
        int Mid = (l + r) >> 1;
        if(x <= Mid) add(l, Mid, Ls[rt], x, y);
        else add(Mid + 1, r, Rs[rt], x, y);
        update(l, r, rt);
    }
    int ask(int l, int r, int rt, int x, int y){
        if(x <= l && r <= y){
            return sum[rt];
        }
        int ans = 0;
        int Mid = (l + r) >> 1;
        if(x <= Mid) ans += ask(l, Mid, Ls[rt], x, y);
        if(y > Mid) ans += ask(Mid + 1, r, Rs[rt], x, y);
        return ans;
    }
    int aks(int l, int r, int rt1, int rt2){
        if(!rt1) return rt2;
        if(!rt2) return rt1;
        if(l == r){
            sum[rt1] += sum[rt2];
            mx[rt1] += mx[rt2];
            if(mx[rt1]) k[rt1] = l;
            else k[rt1] = 0;
            return rt1;
        }
        int Mid = (l + r) >> 1;
        Ls[rt1] = aks(l, Mid, Ls[rt1], Ls[rt2]);
        Rs[rt1] = aks(Mid + 1, r, Rs[rt1], Rs[rt2]);
        update(l, r, rt1);
        return rt1;
    }
    int Max(int l, int r, int rt){
        return k[rt];
    }
}a;

可持久化线段树（静态区间第k小）

struct STree{
    int sum[N * 32], L[N * 32], R[N * 32], cnt;
    void update(int rt){
        sum[rt] = sum[L[rt]] + sum[R[rt]];
    }
    void build(int &rt, int l, int r, int x){
        if(!rt) rt = ++cnt;
        if(l == r){
            sum[rt]++;
            return;
        }
        int mid = (l + r) >> 1;
        if(x <= mid) build(L[rt], l, mid, x);
        if(x > mid) build(R[rt], mid + 1, r, x);
        update(rt);
    }
    void add(int p, int &q, int l, int r, int x){
        if(!q) q = ++cnt;
        if(l == r){
            sum[q] = sum[p] + 1;
            return;
        }
        int mid = (l + r) >> 1;
        if(x <= mid){
            R[q] = R[p];
            add(L[p], L[q], l, mid, x);
        }
        if(x > mid){
            L[q] = L[p];
            add(R[p], R[q], mid + 1, r, x);
        }
        update(q);
    }
    int ask(int p, int q, int l, int r, int x){
        if(l == r) return l;
        int mid = (l + r) >> 1;
        int cntl = sum[L[q]] - sum[L[p]];
        if(cntl >= x){
            return ask(L[p], L[q], l, mid, x);
        }
        else{
            return ask(R[p], R[q], mid + 1, r, x - cntl);
        }
    }
}S;

可持久化线段树（动态区间第k小）

struct STree{
	int sum[N * 441], L[N * 441], R[N * 441], cnt;
	int ask(int l, int r, int k){
		if(l == r) return l;
		int cntk = 0;
		for(int i = 1; i <= cntx; i++)
			cntk -= sum[L[cx[i]]];
		for(int i = 1; i <= cnty; i++)
			cntk += sum[L[cy[i]]];
		int mid = (l + r) >> 1;
		if(cntk >= k){
			for(int i = 1; i <= cntx; i++)
				cx[i] = L[cx[i]];
			for(int i = 1; i <= cnty; i++)
				cy[i] = L[cy[i]];
			return ask(l, mid, k);
		}
		else{
			for(int i = 1; i <= cntx; i++)
				cx[i] = R[cx[i]];
			for(int i = 1; i <= cnty; i++)
				cy[i] = R[cy[i]];
			return ask(mid + 1, r, k - cntk);
		}
	}
	void add(int &rt, int l, int r, int x, int y){
		if(!rt) rt = ++cnt;
		sum[rt] += y;
		if(l == r){
			return;
		}
		int mid = (l + r) >> 1;
		if(x <= mid){
			add(L[rt], l, mid, x, y);
		}
		else{
			add(R[rt], mid + 1, r, x, y);
		}
	}
}S;

本栏目推荐文章
• 类模板实现简单的数组
• 类模板和友元
• 类模板分文件编写
• [cpp]: 以模板作为模板参数 -- <template>
• Jenkins邮件模板
• 【opencv学习笔记】028之模板匹配——matchTemplate函数详解
• Templates Generics 模板 范型
• vue模板的首次渲染，和重新渲染，有哪些区别？
• 水晶报表（CrystalReport）模板绘制二维码
• 系统竣工报告模板