个人ACM模板（待持续补充）

前言

该篇文章创立旨意在于保存博主个人常用的一些模板，便于在遗忘时回顾查看，或者需要时方便回顾，思考到放在博客里可以反复查看，也更利于有需要的人学习使用，于是该博客就诞生了。

该博客的模板由于是博主个人归纳和总结的，所以可能不免会出现一些使用上的问题或者程序内的漏洞，如果存在此类漏洞，可以私信博主进行更改。

代码可以任意转载使用，遇到问题也可以私信博主。

1.排序

(1) 快速排序

int arr[N], n;
//arr数组 n元素个数
inline void quicksort(int l, int r)
{
	if (l >= r) return;
	int x = arr[l + r >> 1], i = l - 1, j = r + 1;
	while (i < j)
	{
		do ++i; while (arr[i] < x);
		do --j; while (arr[j] > x);
		if (i < j) swap(arr[i], arr[j]);
	}
	quicksort(l, j), quicksort(j + 1, r);
}

使用: 
-quicksort(0, n - 1) <排序区间[0, n - 1]>
-quicksort(1, n) <排序区间[1, n]>

均为闭区间 对应数组第一个元素和最后一个元素下标

(2) 归并排序（求逆序对）

int arr[N], tmp[N], n;
//arr数组 tmp临时数组 n元素个数
inline void mergesort(int l, int r)
{
    if (l >= r) return;
    int mid = l + r >> 1;
    mergesort(l, mid), mergesort(mid + 1, r);
    
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
        else tmp[k++] = arr[j++], ans = ans + mid - i + 1;//ans是逆序对
        
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= r) tmp[k++] = arr[j++], ans = ans + mid - i + 1;//ans是逆序对
    
    for (i = l, j = 0; i <= r; ++i, ++j) arr[i] = tmp[j];
}

使用: 
-mergesort(0, n - 1) <排序区间[0, n - 1]>
-mergesort(1, n) <排序区间[1, n]>
-ans <逆序对数>

均为闭区间 对应数组第一个元素和最后一个元素下标

2.基础算法

(1) 二分

bool check(int mid)
{
	return true;
	//return false;
}

void solve()
{
	//板子1
    int l = x, r = y;
    //[l, mid]-> false
    //[mid + 1, r] -> true
    while (l < r)//求区间[x, y]上满足性质的最小值     {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l; //此时l == r

	//板子2
	int l = x, r = y;
	//[l, mid] -> true
	//[mid + 1, r] -> false
    while (l < r)//求区间[x, y]满足性质的最大值
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
	cout << l; //此时l == r
}


使用: 给出区间[x, y]
求出满足性质的 <最小值> 用 <板子1>
求出满足性质的 <最大值> 用 <板子2>

3.数学

(1) 线性筛（朴素，最小质因子，因子数，欧拉函数）

- 朴素线性筛

const int N = 1e5 + 1;//注意是范围+1

vector<int> prime;
bool isp[N];

void euler_seive() {
    for (int i = 2; i < N; ++i) {
        if (!isp[i]) prime.emplace_back(i);
        for (auto& p : prime) {
            if (i * p >= N) break;
            isp[i * p] = true;
            if (i % p == 0) break;
        }
    }
}


使用:
*euler_seive() <预处理>

-if(!isp[idx]) <对 idx 进行素性判断，质数为false>
-prime[idx]

- 最小质因子筛

const int N = 1e5 + 1;//注意是范围+1

vector<int> prime;
int minp[N];

void euler_seive() {
    for (int i = 2; i < N; ++i) {
        if (!minp[i]) minp[i] = i, prime.emplace_back(i);
        for (auto& p : prime) {
            if (i * p >= N) break;
            minp[i * p] = p;
            if (i % p == 0) break;
        }
    }
}


使用:
*euler_seive() <预处理>

-minp[idx] <数字 idx 的最小质因子>
-prime[idx]

- 因子数筛

const int N = 1e5 + 1;//注意是范围 + 1

vector<int> prime;
int fac[N], cnt[N];//cnt为最小质因子数 fac为因子数

void euler_seive() {
    fac[1] = 1;//特判 1
    for (int i = 2; i < N; ++i) {
        if (!fac[i]) fac[i] = 2, cnt[i] = 1, prime.emplace_back(i);
        for (auto& p : prime) {
            if (p * i >= N) break;
            if (i % p == 0) {
                fac[i * p] = fac[i] / (cnt[i] + 1) * (cnt[i] + 2);
                cnt[i * p] = cnt[i] + 1;
                break;
            }
            fac[i * p] = fac[i] * fac[p];
            cnt[i * p] = 1;
        }
    }
}


使用:
*euler_seive() <预处理>

-fac[idx] <数字 idx 的因子数>
-cnt[idx] <数字 idx 的最小质因子数>
-primes[idx]

- 欧拉函数筛

const int N = 1e5 + 1;// 注意是范围 + 1

vector<int> prime;
int phi[N];

void euler_seive() {
    phi[1] = 1;//特判 1
    for (int i = 2; i < N; ++i) {
        if (!phi[i]) phi[i] = i - 1, prime.emplace_back(i);
        for (auto& p : prime) {
            if (i * p >= N) break;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p;
                break;
            }
            phi[i * p] = phi[i] * (p - 1);
        }
    }
}


使用:
*euler_seive() <预处理>

-phi[idx] <数字 idx 的欧拉函数值>
-primes[idx]

(2) 快速幂 (龟速乘)

using i64 = long long;

const int mod = 1e9 + 7;

// a 为底数 b 为指数 mod 为模数
i64 qpow(i64 a, i64 b) {
    i64 res = 1; a %= mod;
    for (; b; b >>= 1, a = a * a % mod) {
        if (b & 1) res = res * a % mod;
    }
    return res;
}

//龟速乘
// a, b 为两个因数 mod 为模数
i64 smul(i64 a, i64 b) {
    i64 res = 0;
    for (; b; b >>= 1, a = (a + a) % mod) {
        if (b & 1) res = (res + a) % mod;
    }
    return res;
}


使用:
-qpow(a, b) < a 的 b 次方>
-smul(a, b) < a 乘 b >

(3) 欧几里得算法 (gcd, exgcd)

using i64 = long long;

//朴素gcd
i64 gcd(i64 a, i64 b)
{
	return b ? gcd(b, a % b) : a;
}

//exgcd
i64 x, i64 y;
i64 exgcd(i64 a, i64 b, i64& x, i64& y)
{
	i64 res;
	if (!b) { x = 1, y = 0; return a; }
	else res = exgcd(b, a % b, y, x), y -= a / b * x;
	return res;
}

使用:
朴素gcd: 
-gcd(a, b)

exgcd求逆元:
-exgcd(a, mod, x, y), x = (x % mod + mod) % mod

(4) jiangly的模板元板子

constexpr int P = 998244353;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(i64 x) : x(norm(x % P)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};

(5) jiangly的组合数板子

using i64 = long long;
template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
 
template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % P)} {}
    
    constexpr int norm(int x) const {
        if (x < 0) {
            x += P;
        }
        if (x >= P) {
            x -= P;
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(P - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    constexpr MInt &operator*=(MInt rhs) {
        x = 1LL * x * rhs.x % P;
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};
 
template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
 
constexpr int P = 998244353;
using Z = MInt<P>;
 
struct Comb {
    int n;
    std::vector<Z> _fac;
    std::vector<Z> _invfac;
    std::vector<Z> _inv;
    
    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }
    
    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;

(6) ygg的组合数板子

using i64 = long long;
const int mod = 1e9 + 7;
struct Comb {
    const int N;
    vector<i64> fac, invfac;
    Comb(int n) : N(n), fac(n + 2), invfac(n + 2) { init(); };
    i64 qpow(i64 x, i64 p) {
        i64 res = 1 % mod; x %= mod;
        for (; p; p >>= 1, x = x * x % mod)
            if (p & 1) res = res * x % mod;
        return res;
    }
    i64 inv(i64 x) { return qpow(x, mod - 2); };
    void init() {
        fac[0] = 1;
        for (int i = 1; i <= N; ++i) fac[i] = fac[i - 1] * i % mod;
        invfac[N] = inv(fac[N]);
        for (int i = N - 1; i >= 0; --i) invfac[i] = (invfac[i + 1] * (i + 1)) % mod;
    }
    i64 C(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
    }
    i64 A(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac[n] * invfac[n - m] % mod;
    }
};

4.数据结构

(1) 单调队列 (单调递减，递增)

void solve()
{
	int n, k;//n为数组长度 k为区间长度
	vector<int> arr(n), q(n);//arr为元素 q为单调队列
	
	int hh = 0, tt = -1;//hh为队头指针 tt为队尾指针
	for (int i = 0; i < n; ++i)
	{
		while (hh <= tt && q[hh] + k <= i) ++hh;//判断过期
		while (hh <= tt && arr[i] <= arr[q[tt]]) --tt;//对递减:弹出不满足元素
		//while (hh <= tt && arr[i] >= arr[q[tt]]) --tt;//对递增:弹出不满足元素
		q[++tt] = i;//更新队尾 存下标
		if (i >= k - 1) //操作
	}
}

使用:
如 solve() 函数所示

(2) 树状数组（前缀和，差分）

using i64 = long long;
int tree[N], n;//tree存树 n为数组下标

i64 Query(int x)//查询闭区间 [1,x] 的前缀和
{
	i64 res = 0;
	for (int i = x; i > 0; i -= i & -i) 
		res += tree[i];
	return res;
}

void Modify(int l, int z)//向闭区间 [l,n] 加上数值 z
{
	for (int i = l; i <= n; i += i & -i)
		tree[i] += z;
}

void solve()
{
    //构造前缀和树状数组
    for (int i = 1, z; i <= n; ++i)
    {
        cin >> z;
        upd(i, z);
    }
    //构造差分树状数组
    for (int i = 1, num, last = 0; i <= n; ++i)
    {
        cin >> num;
        upd(i, num - last);
        last = num;
    }
    //用已有数组构造
    for (int i = 1, num, last = 0; i <= n; ++i)
    {
    	upd(i, arr[i]);//前缀和
    	upd(i, arr[i] - arr[i - 1])//差分
    }
}

使用: 
前缀和树状数组:
-upd(i, z) <使区间 [i,n] 加上 z>
-qry(y) - qry(x - 1) <查询[x,y]的区间和>

差分树状数组:
-upd(x, z), upd(y + 1, -z) <同时使用，使区间 [x,y] 每个数都加上 z>
-qry(x) <查询数组下标为 x 的值>

(3) 线段树（维护区间和模板）

using i64 = long long;

#define lson k << 1, l, mid//宏定义减少代码量
#define rson k << 1 | 1, mid + 1, r
i64 seg[N << 2], lazy[N << 2];//四倍空间

void pushdown(int k, int l, int r)
{
	//左儿子有mid - l + 1个元素 右儿子有 r - mid个元素
	//lt为左儿子下标 rt为右儿子下标
	int mid = l + r >> 1, lt = k << 1, rt = k << 1 | 1;
	seg[lt] += lazy[k] * (mid - l + 1), seg[rt] += lazy[k] * (r - mid);//更新seg
	lazy[lt] += lazy[k], lazy[rt] += lazy[k], lazy[k] = 0;//更新懒标记
}

void build(int k, int l, int r)//构建线段树
{
	lazy[k] = 0;
	if (l == r) return void(cin >> seg[k]);//直接构建
	//if (l == r) return void(seg[k] = arr[l]);用已有数组构建
	//if (l == r) return void (seg[k] = arr[id[l]]);重链剖分建树
	int mid = l + r >> 1;
	build(lson), build(rson);
	seg[k] = seg[k << 1] + seg[k << 1 | 1];
}

void upd(int k, int l, int r, int x, int y, i64 z)//用 z 更新闭区间[x, y]
{
	if (l >= x && r <= y)
	{
		lazy[k] = lazy[k] + z;
		seg[k] += z * (r - l + 1);
		return;
	}
	int mid = l + r >> 1;
	if (lazy[k]) pushdown(k, l, r);
	if (x <= mid) upd(lson, x, y, z);
	if (y > mid) upd(rson, x, y, z);
	seg[k] = seg[k << 1] + seg[k << 1 | 1];
}

i64 qry(int k, int l, int r, int x, int y)//查询闭区间[x, y]
{
	if (l >= x && r <= y) return seg[k];
	if (lazy[k]) pushdown(k, l, r);
	int mid = l + r >> 1;
	i64 res = 0;
	if (x <= mid) res += qry(lson, x, y);
	if (y > mid) res += qry(rson, x, y);
	return res;
}

使用: 
*build(1, 1, n) (建树)

-upd(1, 1, n, x, y, z) (如上)
-qry(1, 1, n, x, y) (如上)

前三个1, 1, n为固定输入 n为数组最后一个元素下标 数组区间严格为[1, n]
后三个x y z分别代表区间 [x,y] 和 增添修改的值(查询时不用z)

(4) 重链剖分（维护树结构）

int siz[N], dep[N], son[N], fa[N];//dfs1相关
//siz 以该节点为树的大小 dep节点的深度 son节点的重儿子 fa节点的父亲
int dfn[N], id[N], top[N], cnt;//dfs2相关
//dfn 剖分序 id建树回溯原下标 top节点的重链头 cnt维护dfn序

inline void dfs1(int u, int ufa)//跑dfs1相关 预处理dfs2
{
	siz[u] = 1, dep[u] = dep[ufa] + 1, fa[u] = ufa;
	for (auto& x : g[u])
	{
		if (x == ufa) continue;
		dfs1(x, u), siz[u] += siz[x];
		if (siz[x] > siz[son[u]]) son[u] = x;
	}
}

inline void dfs2(int u, int tp)//跑dfn序
{
	top[u] = tp, id[++cnt] = u, dfn[u] = cnt;
	if (son[u]) dfs2(son[u], tp);
	for (auto& x : g[u])
		if (x == fa[u] || x == son[u]) continue;
		else dfs2(x, x);
}

void updlink(int x, int y, i64 z)//对节点x->y的最短链上每个节点都加上z
{
	while (top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		upd(1, 1, n, dfn[top[x]], dfn[x], z);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	upd(1, 1, n, dfn[x], dfn[y], z);
}

i64 qrylink(int x, int y)//询问节点x->y的最短链上每个节点的和
{
	i64 res = 0;
	while (top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		res += qry(1, 1, n, dfn[top[x]], dfn[x]);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	res += qry(1, 1, n, dfn[x], dfn[y])
	return res;
}

使用: 给出树上两点(x, y) 和 根(root)
*build(1, 1, n) <预处理线段树 建树如线段树所示>
*dfs1(root, 0), dfs2(root, root) <剖分 root为根>

-updlink(x, y, z) <给 x 到 y 最短链上的所有节点加上 z>
-qrylink(x, y) <查询从 x 到 y 最短链上所有节点的和>
-upd(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, z) <给以节点x为根的子树都加上z>
-qry(1, 1, n, dfn[x], dfn[x] + siz[x] - 1) <查询以节点x为根的子树上所有节点的和>

(5) 分块（维护区间和模板）

using i64 = long long;
i64 arr[N], n;//arr是原数组 n是数组长度
// len 块长 tot 块数;
i64 len, tot;
// sum 单块的和
// lt,rt 这个块的左右下标
// pos 数组下标 [i] 所在的块编号
// lazy 懒标记
i64 sum[M], lt[M], rt[M], lazy[M], pos[N];

void build()
{
    len = (i64)sqrt(n), tot = (n - 1) / len + 1;
    // 处理区间left block, right block下标
    for (int i = 1; i <= tot; ++i) lt[i] = rt[i - 1] + 1, rt[i] = i * len;
    rt[tot] = n;// 末端特判
    for (int i = 1; i <= tot; ++i)//初始化tot个块
        for (int j = lt[i]; j <= rt[i]; ++j)
            pos[j] = i, sum[i] += arr[j];
}

void upd(int x, int y, i64 z)// 对区间[x, y] 加上值z
{
    int lb = pos[x], rb = pos[y];//lb rb 代表左右两块的编号
    if (lb == rb)// 区间[x, y]在同块内时
    {
        for (int i = x; i <= y; ++i) arr[i] += z, sum[lb] += z;
        return;
    }
    for (int i = lb + 1; i <= rb - 1; ++i) sum[i] += len * z, lazy[i] += z;//更新[x, y]中间的整块 和 懒标记
    for (int i = x; i <= rt[lb]; ++i) arr[i] += z, sum[lb] += z;//补上小段[x , rt[lb]]
    for (int i = y; i >= lt[rb]; --i) arr[i] += z, sum[rb] += z;//补上小段[lt[rb] , y]
}

i64 qry(int x, int y)//查询 [x, y] 区间的和
{
    int lb = pos[x], rb = pos[y]; i64 res = 0;
    if (lb == rb)// 区间[x, y]在同块内时
    {
        for (int i = x; i <= y; ++i) res += arr[i] + lazy[lb];
        return res;
    }
    for (int i = lb + 1; i <= rb - 1; ++i) res += sum[i];// 区间[x, y]中间的整块
    for (int i = x; i <= rt[lb]; ++i) res += arr[i] + lazy[lb];//补上小段[x , rt[lb]]
    for (int i = y; i >= lt[rb]; --i) res += arr[i] + lazy[rb];//补上小段[lt[rb] , y]
    return res;
}



使用: 给出区间[x, y]
*build() <预处理分块>

-upd(x, y, z) <将[x, y]上的数字都加上z>
-qry(x, y) <查询[x, y]的区间和>

(6) 并查集

int fa[N], siz[N];//fa是父亲 siz是所在并查集大小

int find(int x)//查询父节点
{
    while (x != fa[x]) x = fa[x] = fa[fa[x]];
    return x;
}
//查询 x 所在并查集大小
int size(int x) { return siz[find(x)]; }
//查询是否在同一区间 
bool same(int x, int y) { return find(x) == find(y); }

bool merge(int x, int y)//合并 x 和 y 所在并查集
{
    x = find(x), y = find(y);
    if (x == y) return false;
    siz[x] += siz[y];
    fa[y] = x;
    return true;
}

使用: 给出两点 (x, y)
*for(int i = 1; i <= n; ++i) siz[i] = 1, fa[i] = i; <预处理并查集>

-find(x) <查询 x 节点的父亲>
-size(x) <查询 x 节点所在并查集大小>
-same(x, y) <查询 x 节点和 y 节点是否在同一并查集内>
-merge(x, y) <合并 x 节点和 y 节点的并查集>

(7) 可持久化线段树（维护区间和）

using i64 = long long;

const int N = 4e6 + 5, M = 1e5 + 5;

//seg是树的值 ls是左儿子 rs是右儿子 lazy是懒标记
//lson rson 用来优化代码量
#define seg(x) tree[x].val
#define ls(x) tree[x].l
#define rs(x) tree[x].r
#define lson(x) tree[x].l, l, mid
#define rson(x) tree[x].r, mid + 1, r
#define lazy(x) tree[x].lazy

//ver代表着每一次修改的根节点下标 idx辅助开点
int ver[M], idx, n, m;

struct Segtree {
    i64 val;
    int l, r, lazy;
}tree[N];

void build(int k, int l, int r) {
    seg(k) = lazy(k) = 0;//多测清空
    if (l == r) return void(cin >> seg(k));//构建方式可参考线段树
    int mid = l + r >> 1;
    //动态开点确保空间复杂度
    ls(k) = ++idx, rs(k) = ++idx;
    build(lson(k)), build(rson(k));
    seg(k) = seg(ls(k)) + seg(rs(k));
}

//pre代表着历史版本
void upd(int pre, int k, int l, int r, int x, int y, int z) {
    tree[k] = tree[pre];//先让其等于历史值
    if (l >= x && r <= y) {
        lazy(k) += z;
        seg(k) += z * (r - l + 1);
        return;
    }
    int mid = l + r >> 1;
    //在修改的同时动态开点
    if (x <= mid) ls(k) = ++idx, upd(ls(pre), lson(k), x, y, z);
    if (y > mid) rs(k) = ++idx, upd(rs(pre), rson(k), x, y, z);
    seg(k) = seg(ls(k)) + seg(rs(k)) + lazy(k) * (r - l + 1);//注意同时加上懒标记
}

//因为空间大小原因不可下放标记 利用永久化标记 mark 辅助查询
i64 qry(int k, int l, int r, int x, int y, i64 mark) {
    if (l >= x && r <= y) return seg(k) + (r - l + 1) * mark;
    int mid = l + r >> 1;
    i64 res = 0;
    if (x <= mid) res += qry(lson(k), x, y, mark + lazy(k));
    if (y > mid) res += qry(rson(k), x, y, mark + lazy(k));
    return res;
}

void solve() {

    cin >> n >> m;

    idx = 0;
    ver[0] = ++idx;
    build(ver[0], 1, n);

    char op; int x, y, z, now = 0;
    for (int i = 1; i <= m; ++i) {
        cin >> op;
        if (op == 'C') {
            cin >> x >> y >> z;
            ver[++now] = ++idx;
            upd(ver[now - 1], ver[now], 1, n, x, y, z);
        }
        else if (op == 'Q') {
            cin >> x >> y;
            cout << qry(ver[now], 1, n, x, y, 0) << '\n';
        }
        else if (op == 'H') {
            cin >> x >> y >> z;
            cout << qry(ver[z], 1, n, x, y, 0) << '\n';
        }
        else if (op == 'B'){
            cin >> now;
        }
    }
}


使用：给出一个区间 <[x, y]> 和 <历史版本z> 或 <修改值z>

<预处理线段树，版本从 0 开始>
*idx = 0, ver[0] = ++idx，build(ver[now], 1, n) 

<使当前版本的区间 [x, y] 同时加上一个值 z ，并更新当前版本> (Change)
-ver[++now] = ++idx <更新版本>
-upd(ver[now - 1], ver[now], 1, n, x, y, z); 

<查询当前版本区间 [x, y] 的数字的和> (Query)
-qry(ver[now], 1, n, x, y, 0)

<查询第 z 次修改的版本区间 [x, y] 的数字的和> (History)
-qry(ver[z], 1, n, x, y, 0)

<将当前版本回溯至第 z 次修改的版本> (Back)
-now = z

以上四种操作分别对应 solve() 中: op = C, Q, H, B。
单次修改需要的空间开销很大，请不要吝啬空间，能开多大则开多大。
<除动态开点及宏定义外，其他内容与线段树结构相似>

(8) 珂朵莉树（ODT）

using i64 = long long;

struct Node {
    i64 l, r;
    mutable i64 v;
    Node(i64 l, i64 r, i64 v) : l(l), r(r), v(v) {}
    bool operator<(const Node& t) const { return l < t.l; };
};

set<Node> ODT;
//拆分区间操作 <ODT核心>
set<Node>::iterator split(i64 pos) {
    auto it = ODT.lower_bound(Node(pos, 0, 0));
    if (it != ODT.end() && it->l == pos) return it;
    i64 l = (--it)->l, r = it->r, v = it->v;
    ODT.erase(it);
    ODT.emplace(l, pos - 1, v);
    return ODT.emplace(pos, r, v).first;
}
//区间赋值操作
void assign(i64 l, i64 r, i64 v) {
    auto end = split(r + 1), begin = split(l);
    ODT.erase(begin, end);
    ODT.emplace(l, r, v);
}
//区间加
void add(i64 l, i64 r, i64 v) {
    auto end = split(r + 1);
    for (auto it = split(l); it != end; ++it)
        it->v += v;
}
//快速幂模板
i64 qpow(i64 a, i64 b, i64 Mod) {
    i64 res = 1 % Mod; a %= Mod;
    for (; b; b >>= 1, a = a * a % Mod)
        if (b & 1) res = res * a % Mod;
    return res;
}
//区间平方和
i64 rangepow(i64 l, i64 r, i64 x, i64 y) {
    i64 res = 0;
    auto end = split(r + 1);
    for (auto it = split(l); it != end; ++it)
        res = (res + qpow(it->v, x, y) * (it->r - it->l + 1)) % y;
    return res;
}
//区间第k小数
i64 kth(i64 l, i64 r, i64 k) {
    auto end = split(r + 1);
    vector<pair<i64, i64>> rnk;
    for (auto it = split(l); it != end; ++it)
        rnk.emplace_back(it->v, it->r - it->l + 1);
    sort(rnk.begin(), rnk.end());
    int rnksz = rnk.size();
    for (int i = 0; i < rnksz; ++i) {
        k -= rnk[i].second;
        if (k <= 0) return rnk[i].first;
    }
    return -1;
}


使用: 给出数组 <arr>，区间 <[l, r]>，<数字x> 和 <模数y>

*利用for循环插入数组中的每一个点 <预处理>
	for (int i = 1; i <= n; ++i) {
	    ODT.emplace(i, i, arr[i]);
	}

-assign(l, r, x) <将闭区间 [l, r] 内所有数字改为 x>
-add(l, r, x) <将闭区间 [l, r] 内所有数字加上 x>
-kth(l, r, x) <求出闭区间 [l, r] 内第 x 小的数字>
-rangepow(l, r, x, y) <求出闭区间 [l, r] 内所有数字在模 y 下的 x 次方之和>

(9) 莫队模板

i64 tot;//每一块的长度
struct Ask {
    int l, r, id;
    bool operator<(const Ask& t) const {
        if (l / tot != t.l / tot) return l < t.l;
        if (l / tot & 1) return r > t.r;
        return r < t.r;
    }
};

void solve() {

    int n, q;
    cin >> n >> q;

    tot = n / sqrtl(n);//算出块长

    vector<int> ans(q);//答案
    vector<Ask> ask(q);//离线
    sort(ask.begin(), ask.end());

    int cur = 0;//当前的答案贡献
    auto add = [&](int pos) {
        //加入的贡献
    };

    auto del = [&](int pos) {
        //删除的贡献
    };

    int i = 1, j = 0;
    for (int now = 0; now < q; ++now) {
        int l = ask[now].l, r = ask[now].r, id = ask[now].id;
        while (i > l) add(--i);
        while (j < r) add(++j);
        while (i < l) del(i++);
        while (j > r) del(j--);
        ans[id] = cur;//等于答案贡献
    }
    //多测清空
    while (j < n) add(++j);
    while (i <= n) del(i++);

}

(10) 主席树模板（静态查询区间第 k 小）

const int N = 2e5 + 10;//数组长度

int idx;
struct Segtree {
    int cnt, l, r;
}tree[N << 5];//32倍空间

//宏定义减少代码量
#define seg(k) tree[k].cnt
#define ls(k) tree[k].l
#define rs(k) tree[k].r
#define lson(k) tree[k].l, l, mid
#define rson(k) tree[k].r, mid + 1, r

//创建新节点
int creat(int pre) {
    tree[++idx] = tree[pre];
    return idx;
}

//更新版本
int upd(int& pre, int l, int r, int x, int y) {
    int cur = creat(pre);
    if (l >= x && r <= y) {
        ++seg(cur);
        return cur;
    }
    int mid = l + r >> 1;
    if (x <= mid) ls(cur) = upd(ls(pre), l, mid, x, y);
    if (y > mid) rs(cur) = upd(rs(pre), mid + 1, r, x, y);
    seg(cur) = seg(ls(cur)) + seg(rs(cur));
    return cur;
}

//区间第 k 小
int kth_small(int& pre, int& k, int l, int r, int rnk) {
    if (l == r) return l;
    int mid = l + r >> 1, cnt = seg(ls(k)) - seg(ls(pre));
    if (rnk <= cnt) return kth_small(ls(pre), lson(k), rnk);
    else return kth_small(rs(pre), rson(k), rnk - cnt);
}

//区间第 k 大
int kth_big(int& pre, int& k, int l, int r, int rnk) {
    if (l == r) return l;
    int mid = l + r >> 1, cnt = seg(rs(k)) - seg(rs(pre));
    if (rnk <= cnt) return kth_big(rs(pre), rson(k), rnk);
    else return kth_big(ls(pre), lson(k), rnk - cnt);
}

void solve() {

    int n, m;
    cin >> n >> m;
    vector<int> arr(n + 1), b(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        b[i] = arr[i];
    }

    //离散化下标
    b[0] = INT32_MIN;//初始化为负无穷 便于离散化下标从 1 开始
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    int len = b.size() - 1;

    //版本数组
    vector<int> ver(n + 1);

    //把每一个版本记录下来
    for (int i = 1; i <= n; ++i) {
        int pos = lower_bound(b.begin(), b.end(), arr[i]) - b.begin();
        //更新版本
        ver[i] = upd(ver[i - 1], 1, len, pos, pos);
    }

    int l, r, k;
    for (int i = 1; i <= m; ++i) {
        cin >> l >> r >> k;
        //获得第 k 小的数字离散化的下标
        int pos = kth_small(ver[l - 1], ver[r], 1, len, k);

        //输出第 k 小数
        cout << b[pos] << '\n';
    }
}


使用: 给出数组 <arr>，区间 <[l, r]>，<数字k>

如 solve() 函数所示

5.图论

(1) Dijkstra （堆优化）

using PII = pair<int, int>;
using i64 = long long;

const int N = 2e5 + 1, inf = 1e9;

vector<PII> g[N]; //存图
vector<int> dist(N, inf); //存距离 初始化为无穷 inf

void dijkstra(int s) {
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.emplace(0, s);
    dist[s] = 0;// s 为起点

    while (heap.size()) {
        auto [dis, u] = heap.top(); heap.pop();
        if (dist[u] < dis) continue;
        for (auto& [v, w] : g[u]) {
            if (dist[v] > dis + w) {
                dist[v] = dis + w;
                heap.emplace(dist[v], v);
            }
        }
    }
}


使用: 
*dijkstra() <最短路>

-dist[idx]

(2) Spfa

- 朴素

const int N = 2e5 + 1, inf = 1e9;

vector<PII> g[N]; //存图
vector<int> dist(N, inf); //存距离 初始化为无穷 inf
bool vis[N];
int cnt[N];

void SPFA(int s) {
    queue<int> que;
    que.push(s);
    dist[s] = 0;// s 为起点

    while (que.size()) {
        auto u = que.front(); que.pop();
        vis[u] = false;
        for (auto& [v, w] : g[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                //cnt[v] = cnt[u] + 1;
                //if (cnt[v] > n) return true; 有负环记得函数换成bool
                if (!vis[v]) {
                    vis[v] = true;
                    que.push(v);
                }
            }
        }
    }
    //return false;无负环记得函数换成bool
}


使用:
*spfa() <最短路>

-if(spfa()) <判负环>
-dist[idx]

- SLF优化

const int N = 2e5 + 1, inf = 1e9;

vector<PII> g[N]; //存图
vector<int> dist(N, inf); //存距离 初始化为无穷 inf
bool vis[N];
int cnt[N];

//Small Lable First
bool SPFA(int s) {
    deque<int> que;
    que.push_back(s);
    dist[s] = 0;// s 为起点

    while (que.size()) {
        auto u = que.front(); que.pop_front();
        vis[u] = false;
        for (auto& [v, w] : g[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                //cnt[v] = cnt[u] + 1;
                //if (cnt[v] > n) return true; 有负环
                if (!vis[v]) {
                    vis[v] = true;
                    if (que.size() && dist[v] < dist[que.front()]) {
                        que.push_front(v);
                    } else {
                        que.push_back(v);
                    }
                }
            }
        }
    }
    //return false;无负环
}


使用:
*spfa() <最短路>

-if(spfa()) <判负环>
-dist[idx]

- LLL优化

//Large Label Last
bool spfa()
{
    //s为起点
    queue<int> que;
    que.push(s);
    dist[s] = 0;
    i64 sum = 0, num = 1;//多创建两个变量维护

    while (que.size())
    {
        int t = que.front();
        // LLL优化：队头要是比对内平均值大 先放后面 否则出队
        while (dist[t] * num > sum)
        {
            que.pop();
            que.push(t);
            t = que.front();
        }
        que.pop();
        sum -= dist[t], --num;
        //---
        visit[t] = false;
        for (int u = h[t]; u; u = ne[u])
        {
            int v = e[u];
            if (dist[v] > dist[t] + w[u])
            {
                dist[v] = dist[t] + w[u];
                //cnt[v] = cnt[t] + 1;判负环
                //if (cnt[v] > n) return true;
                if (!visit[v])
                {
                    que.push(v);
                    visit[v] = true;
                    sum += dist[v], ++num;//注意补上入队值
                }
            }
        }
    }
    //return false;判负环
}

使用:
*spfa() <最短路>

-if(spfa()) <判负环>
-dist[idx]

- SLF + LLL 优化

//Small Label First & Large Label Last
bool spfa()//老老实实用SLF好像会比SLF+LLL快
{

    deque<int> que;
    que.push_back(s);
    dist[s] = 0;
    i64 sum = dist[s], num = 1;//LLL

    while (que.size())
    {
        auto t = que.front();

        while (dist[t] * num > sum) //LLL
        {
            que.pop_front();
            que.push_back(u);
            t = que.front();
        }
        sum -= dist[t], --num;
        que.pop_front();

        visit[t] = false;
        for (int u = h[t]; u; u = ne[u])
        {
            int v = e[u];
            if (dist[v] > dist[t] + w[u])
            {
                dist[v] = dist[u] + w[u];
                //cnt[v] = cnt[t] + 1;判负环
                //if (cnt[v] > n) return true;
                if (!visit[v])
                {
                    visit[v] = true;
                    if (que.size() && dist[que.front()] > dist[v])//SLF
                        que.push_front(v);
                    else
                        que.push_back(v);
                    sum += dist[v], ++num;//LLL
                }
            }
        }
    }
    //return false;判负环
}

(3) Kruskal最小生成树

const int M = 4e5 + 1, N = 2e5 + 1;

struct Edge {
    int u, v, w;
    bool operator<(const Edge& rhs) const {
        return w < rhs.w;
    }
} edge[M];

int fa[N], n, m;// n 为点数 m 为边数

int find(int x) {
    while (fa[x] != x) x = fa[x] = fa[fa[x]];
    return x;
}

bool kruskal() {
    sort(edge, edge + m);//边存储为 [0, m - 1] 区间
    iota(fa, fa + n, 0);
    int sum = 0, cnt = 0;
    for (int i = 0; i < m; ++i) {
        int u = edge[i].u, v = edge[i].v, w = edge[i].w;
        u = find(u), v = find(v);
        if (u != v) {
            fa[u] = v;
            sum += w;
            ++cnt;
        }
    }
    return cnt == n - 1; //判断是否能构成最小生成树
    //return sum; 返回最小生成树边权和 注意改成int
}


使用:
*kruskal() <处理生成树>

-if(kruskal()) <判联通图>
-res

(4) 最近公共祖先LCA (倍增，重链剖分)

- 倍增

const int N = 2e5 + 1, logn = 21;

vector<int> g[N];//vector存图

int dep[N], nxt[N][22];//dep为深度 nxt为倍增表

void DFS(int u, int ufa) {
    dep[u] = dep[ufa] + 1, nxt[u][0] = ufa;
    for (int j = 1; (1 << j) <= dep[u]; ++j) {
        nxt[u][j] = nxt[nxt[u][j - 1]][j - 1];
    }
    for (auto& v : g[u]) {
        if (v == ufa) continue;
        DFS(v, u);
    }
}

int LCA(int u, int v) {
    if (dep[u] > dep[v]) {
        swap(u, v);
    }
    for (int j = logn; j >= 0; --j) {
        if (dep[u] - (1LL << j) >= dep[v]) {
            u = nxt[u][j];
        }
    }
    if (u == v) return u;
    for (int j = logn; j >= 0; --j) {
        if (nxt[u][j] != nxt[v][j]) {
            u = nxt[u][j];
            v = nxt[v][j];
        }
    }
    return nxt[u][0];
}


使用: 
*DFS(root, 0) <初始化 root为根>

-LCA(u, v) <获得点 u 和点 v 的LCA>

- 重链剖分

const int N = 2e5 + 1;

vector<int> g[N];//vector存图

int dep[N], fa[N], siz[N], son[N]; //DFS1相关
int dfn[N], rdfn[N], top[N], idx; //DFS2相关

void DFS1(int u, int ufa) {
    dep[u] = dep[ufa] + 1, siz[u] = 1, fa[u] = ufa;
    for (auto& v : g[u]) {
        if (v == ufa) continue;
        DFS1(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) {
            son[u] = v;
        }
    }
}

void DFS2(int u, int tp) {
    dfn[u] = ++idx, rdfn[idx] = u, top[u] = tp;
    if (son[u]) DFS2(son[u], tp);
    for (auto& v : g[u]) {
        if (v == fa[u] || v == son[u]) continue;
        DFS2(v, v);
    }
}

int LCA(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) {
            swap(u, v);
        }
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) {
        swap(u, v);
    }
    return u;
}


使用: 给出两个点(x, y)
*DFS1(root, 0), DFS2(root, root) <预处理 root为根>

-LCA(x, y) <求出点 u 和点 v 的LCA>

(5) 求树的重心

int cnt[N], mx[N], cent[2], n;
//cnt代表以u为节点不包含父上级的节点数
//mx代表以u为节点包含父上级的最大重量
//cnt存两个重心
inline void getcent(int u, int fa)
{
	cnt[u] = 1, mx[u] = 0;
	for (auto& x : g[u])
		if (x != fa)
			getcent(x, u),
			cnt[u] += cnt[x],
			mx[u] = max(mx[u], cnt[x]);
	mx[u] = max(mx[u], n - cnt[u]);
	if (mx[u] <= n / 2)
		cent[cent[0] != 0] = u;
}

使用: 
*getcent(1, -1) <初始化>

-cent[0], cent[1] <两个重心>

(6) Johnson全源最短路

using i64 = long long;
using PII = pair<int, int>;

//dist为正图的最短路 一维为起点 二维为终点
vector<vector<i64>> dist(N, vector<i64>(N, 0x3f3f3f3f));
vector<i64> d(N, 0x3f3f3f3f);//势能
vector<PII> g[N];//存图
int cnt[N], n, m;//n为点数 m为边数
bool vis[N];

bool spfa()//跑虚拟图
{
	queue<int> que;
	que.push(0);
	d[0] = 0;
	while (que.size())
	{   
		//t为当前点
		auto t = que.front(); que.pop();
		vis[t] = false;
		//u为邻点 w为边权
		for (auto& [u, w] : g[t])
			if (d[u] > d[t] + w)
			{
				d[u] = d[t] + w;
				cnt[u] = cnt[t] + 1;//判负环
				if (cnt[u] > n) return true;
				if (!vis[u])
					que.push(u),
					vis[u] = true;
			}
	}
	return false;
}

void dijkstra(int s)//以s为起点跑最短路
{
	for (int i = 0; i <= n; ++i) vis[i] = false;
	priority_queue<PII, vector<PII>, greater<PII>> heap;
	heap.push({ 0, s });
	dist[s][s] = 0;

	while (heap.size())
	{
		//dist为当前点距离 t为点标号
		auto [dis, t] = heap.top(); heap.pop();
		
		if (vis[t]) continue;
		vis[t] = true;
		//u为邻点 w为边权
		for (auto& [u, w] : g[t])
			if (dist[s][u] > dis + w)
				dist[s][u] = dis + w,
				heap.push({ dist[s][u], u });
	}
}

void solve()
{
	for (int i = 0, x, y, z; i < m; ++i)
	{
		cin >> x >> y >> z;
		g[x].emplace_back(y, z);
		g[y].emplace_back(x, z);
	}
	
	for (int i = 1; i <= n; ++i) //建势能图
		g[0].emplace_back(i, 0);
	
	if (spfa())//跑势能图+判负环
		return void(cout << -1 << '\n');
		
	for (int i = 1; i <= n; ++i)//重定义边权
		for(auto& [u, w] : g[i]) 
			w += d[i] - d[u];//i为起点 u为终点
	//跑n次dijkstra
	for (int i = 1; i <= n; ++i)
		dijkstra(i);

	for (int i = 1; i <= n; ++i)//输出正确的最短路
		for (int j = 1; j <= n; ++j)
			cout << dist[i][j] + d[j] - d[i] << " \n"[j == n];
}

使用: 
如 solve() 函数所示