模板

模板汇总，不定期更新

基本模板

IO 优化

//Author:xht37
#include <bits/stdc++.h>

#define ui unsigned int
#define ll long long
#define ul unsigned ll
#define ld long double

#define pi pair <int, int>
#define fi first
#define se second
#define mp make_pair

#define ls (p << 1)
#define rs (ls | 1)
#define md ((t[p].l + t[p].r) >> 1)

#define vi vector <int>
#define pb push_back
#define pq priority_queue

#define dbg(x) cerr << #x" = " << (x) << endl
#define debug(...) fprintf(stderr, __VA_ARGS__)

#define fl(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

namespace io {
	const int SI = 1 << 21 | 1;
	char IB[SI], *IS, *IT, OB[SI], *OS = OB, *OT = OS + SI - 1, c, ch[100];
	int f, t;
	#define gc() (IS == IT ? (IT = (IS = IB) + fread(IB, 1, SI, stdin), IS == IT ? EOF : *IS++) : *IS++)
	inline void flush() {
		fwrite(OB, 1, OS - OB, stdout), OS = OB;
	}
	inline void pc(char x) {
		*OS++ = x;
		if (OS == OT) flush();
	}

	template <class I>
	inline void rd(I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + (c & 15), c = gc());
		x *= f;
	}
	template <class I>
	inline void rd(I &x, I &y) {
		rd(x), rd(y);
	}
	template <class I>
	inline void rd(I &x, I &y, I &z) {
		rd(x), rd(y), rd(z);
	}
	template <class I>
	inline void rda(I *a, int n) {
		for (int i = 1; i <= n; i++) rd(a[i]);
	}
	inline void rdc(char &c) {
		for (c = gc(); c < 33 || c > 126; c = gc());
	}
	inline void rds(char *s, int &n) {
		for (c = gc(); c < 33 || c > 126; c = gc());
		for (n = 0; c >= 33 && c <= 126; s[++n] = c, c = gc());
	}
	inline void rds(string &s) {
		for (c = gc(); c < 33 || c > 126; c = gc());
		for (s.clear(); c >= 33 && c <= 126; s.pb(c), c = gc());
	}

	template <class I>
	inline void print(I x, char k = '\n') {
		if (!x) pc('0');
		if (x < 0) pc('-'), x = -x;
		while (x) ch[++t] = x % 10 + '0', x /= 10;
		while (t) pc(ch[t--]);
		pc(k);
	}
	template <class I>
	inline void print(I x, I y) {
		print(x, ' '), print(y);
	}
	template <class I>
	inline void print(I x, I y, I z) {
		print(x, ' '), print(y, ' '), print(z);
	}
	template <class I>
	inline void printa(I *a, int n) {
		for (int i = 1; i <= n; i++) print(a[i], " \n"[i==n]);
	}
	inline void printc(char c) {
		pc(c);
	}
	inline void prints(char *s, int n) {
		for (int i = 1; i <= n; i++) pc(s[i]);
		pc('\n');
	}
	inline void prints(string s) {
		int n = s.length();
		while (t < n) pc(s[t++]);
		pc('\n'), t = 0;
	}
	struct Flush {
		~Flush() {
			flush();
		}
	} flusher;
}
using io::rd;
using io::rda;
using io::rdc;
using io::rds;
using io::print;
using io::printa;
using io::printc;
using io::prints;

int main() {
	
	return 0;
}

模运算

const int P = P;

struct modint {
	int x;
	inline modint(int x = 0) : x(x) {}
	inline modint &operator = (int o) { return x = o, *this; }
	inline modint &operator += (modint o) { return (x += o.x) >= P && (x -= P), *this; }
	inline modint &operator -= (modint o) { return (x -= o.x) < 0 && (x += P), *this; }
	inline modint &operator *= (modint o) { return x = 1ll * x * o.x % P, *this; }
	template <class I>
	inline modint &operator ^= (I b) {
		modint a = *this, c;
		if (!~b) b = P - 2;
		c.x = 1 % P;
		while (b) {
			if (b & 1) c *= a;
			a *= a, b >>= 1;
		}
		return x = c.x, *this;
	}
	inline modint &operator /= (modint o) { return *this *= o ^ -1; }
	inline modint &operator += (int o) { return (x += o) >= P && (x -= P), *this; }
	inline modint &operator -= (int o) { return (x -= o) < 0 && (x += P), *this; }
	inline modint &operator *= (int o) { return x = 1ll * x * o % P, *this; }
	inline modint &operator /= (int o) { return *this *= (modint)o ^ -1; }
	template <class I>
	inline friend modint operator + (modint a, I b) { return a += b; }
	template <class I>
	inline friend modint operator - (modint a, I b) { return a -= b; }
	template <class I>
	inline friend modint operator * (modint a, I b) { return a *= b; }
	template <class I>
	inline friend modint operator ^ (modint a, I b) { return a ^= b; }
	template <class I>
	inline friend modint operator / (modint a, I b) { return a /= b; }
	inline friend bool operator == (modint a, int b) { return a.x == b; }
	inline friend bool operator != (modint a, int b) { return a.x != b; }
	inline friend bool operator < (modint a, int b) { return a.x < b; }
	inline friend bool operator <= (modint a, int b) { return a.x <= b; }
	inline friend bool operator > (modint a, int b) { return a.x > b; }
	inline friend bool operator >= (modint a, int b) { return a.x >= b; }
	inline friend bool operator == (modint a, modint b) { return a.x == b.x; }
	inline friend bool operator != (modint a, modint b) { return a.x != b.x; }
	inline friend bool operator < (modint a, modint b) { return a.x < b.x; }
	inline friend bool operator <= (modint a, modint b) { return a.x <= b.x; }
	inline friend bool operator > (modint a, modint b) { return a.x > b.x; }
	inline friend bool operator >= (modint a, modint b) { return a.x >= b.x; }
	inline bool operator ! () { return !x; }
	inline modint operator - () { return x ? P - x : 0; }
};
inline void rd(modint &x) { rd(x.x); }
inline void print(modint x, char k = '\n') { print(x.x, k); }

//const int NP = 1e6 + 7;
//modint p[NP], v[NP], vp[NP];
//inline void init(int n) {
//  p[0] = v[0] = 1;
//  for (int i = 1; i <= n; i++) p[i] = p[i-1] * i;
//  vp[n] = 1 / p[n];
//  for (int i = n; i; i--) v[i] = vp[i] * p[i-1], vp[i-1] = vp[i] * i;
//}
//inline modint binom(int n, int m) {
//  return (m < 0 || n < m) ? 0 : p[n] * vp[m] * vp[n-m];
//}

随机数

namespace Rd {
	inline bool gt() {
		int a = rand(), b = rand();
		while (a == b) a = rand(), b = rand();
		return a < b;
	}
	template <class I>
	inline I rd(I k) {
		I w = 1;
		while (w < k) w <<= 1;
		while (w >= k) {
			I o = 1, x = 0;
			while (o < k) o <<= 1, x = x << 1 | gt();
			w = x;
		}
		return w;
	}
	template <class I>
	inline I rdm(I l, I r) {
		return l == r ? l : l + rd(r - l + 1);
	}
	template <class I>
	inline void rdms(I *a, int n) {
		for (int i = n; i; i--) swap(a[i], a[rdm(1,i)]);
	}
}
using Rd::rdm;
using Rd::rdms;

int main() {
//	freopen("1.in", "w", stdout);

	int seed;
	rd(seed);
	srand(seed ^ time(0));

	
	return 0;
}

对拍模板

Windows

#include <bits/stdc++.h>

using namespace std;

const int T = 1e5;
const string cpp = "1", io = "1";

int main() {
	for (int i = 1; i <= T; i++) {
		FILE *fp = fopen("tmp.in", "w");
		fprintf(fp, "%d\n", i);
		fclose(fp);
		system(("rd.exe < tmp.in > " + io + ".in").c_str());
		double l = clock();
		system((cpp + ".exe < " + io + ".in > " + io + ".out").c_str());
		double r = clock();
		system(("bl.exe < " + io + ".in > " + io + ".ans").c_str());
		if (system(("fc " + io + ".out " + io + ".ans").c_str()))
			return puts("WA"), 0;
		else printf("%d AC %.3fs\n\n\n", i, (r - l) / CLOCKS_PER_SEC);
	}
	return 0;
}

Linux

#include <bits/stdc++.h>

using namespace std;

const int T = 1e5;

int main() {
	for (int i = 1; i <= T; i++) {
		system("./rd");
		double l = clock();
		system("./1");
		double r = clock();
		system("./bl");
		if (system("diff 1.out 1.ans")) return puts("WA"), 0;
		else printf("%d AC %.3fs\n", i, (r - l) / CLOCKS_PER_SEC);
	}
	return 0;
}

动态规划模板

矩阵加速

struct mat {
	modint a[N][N];
	inline friend mat operator * (const mat &x, const mat &y) {
		mat z;
		for (int i = 0; i < N; i++)
			for (int k = 0; k < N; k++)
				for (int j = 0; j < N; j++)
					z.a[i][j] += x.a[i][k] * y.a[k][j];
		return z;
	}
	inline friend mat operator ^ (mat x, ll y) {
		mat z;
		for (int i = 0; i < N; i++) z.a[i][i] = 1;
		while (y) {
			if (y & 1) z = z * x;
			x = x * x, y >>= 1;
		}
		return z;
	}
};

字符串模板

KMP

const int N = 1e6 + 7;
int n, m, p[N], ans;
char a[N], b[N];

int main() {
	rds(a, n), rds(b, m);
	for (int i = 2, j = 0; i <= m; i++) {
		while (j && b[i] != b[j+1]) j = p[j];
		if (b[i] == b[j+1]) ++j;
		p[i] = j;
	}
	for (int i = 1, j = 0; i <= n; i++) {
		while (j && a[i] != b[j+1]) j = p[j];
		if (a[i] == b[j+1]) ++j;
		ans += j == m;
	}
	print(ans);
	return 0;
}

AC 自动机

struct AC {
	int trie[N][27], fail[N], t = 1;
	
	inline int ins(char *s, int n) {
		int p = 1;
		for (int i = 1; i <= n; i++) {
			int c = s[i] - 'a';
			if (!trie[p][c]) trie[p][c] = ++t;
			p = trie[p][c];
		}
		return p;
	}
	
	inline void main() {
		queue<int> q;
		for (int i = 0; i < 26; i++)
			if (trie[1][i]) fail[trie[1][i]] = 1, q.push(trie[1][i]);
			else trie[1][i] = 1;
		while (q.size()) {
			int x = q.front();
			q.pop();
			for (int i = 0; i < 26; i++)
				if (trie[x][i]) fail[trie[x][i]] = trie[fail[x]][i], q.push(trie[x][i]);
				else trie[x][i] = trie[fail[x]][i];
		}
	}
	
	inline int get(char *s, int n) {
		int p = 1;
		for (int i = 1; i <= n; i++) {
			int c = s[i] - 'a';
			p = trie[p][c];
		}
		return p;
	}
} ac;

SA

int n;
char s[N];

struct SA {
	int m, sa[N], rk[N<<1|1], tp[N<<1|1], tx[N], he[N];
	inline void sort() {
		for (int i = 1; i <= m; i++) tx[i] = 0;
		for (int i = 1; i <= n; i++) ++tx[rk[i]];
		for (int i = 1; i <= m; i++) tx[i] += tx[i-1];
		for (int i = n; i; i--) sa[tx[rk[tp[i]]]--] = tp[i];
	}
	inline bool pd(int i, int j, int k) {
		return tp[i] == tp[j] && tp[i+k] == tp[j+k];
	}
	inline void main() {
		m = 127;
		for (int i = 1; i <= n; i++) rk[i] = s[i], tp[i] = i;
		sort();
		for (int k = 1, p = 0; p < n; k <<= 1, m = p) {
			p = 0;
			for (int i = 1; i <= k; i++) tp[++p] = n - k + i;
			for (int i = 1; i <= n; i++)
				if (sa[i] > k) tp[++p] = sa[i] - k;
			sort(), swap(rk, tp), rk[sa[1]] = p = 1;
			for (int i = 2; i <= n; i++)
				rk[sa[i]] = p += !pd(sa[i], sa[i-1], k);
		}
	}
	inline void height() {
		for (int i = 1, p = 0; i <= n; i++) {
			if (p) --p;
			int j = sa[rk[i]-1];
			while (s[i+p] == s[j+p]) ++p;
			he[rk[i]] = p;
		}
	}
} sa;

数组版 SAM

struct SAM {
	int l, ch[N<<1|1][26], len[N<<1|1], pa[N<<1|1], t;
	inline void add(int c) {
		int w = ++t, p = l;
		len[w] = len[l] + 1;
		while (~p && !ch[p][c]) ch[p][c] = w, p = pa[p];
		if (!~p) return pa[l=w] = 0, void();
		int q = ch[p][c];
		if (len[p] + 1 == len[q]) return pa[l=w] = q, void();
		int k = ++t;
		pa[k] = pa[q], memcpy(ch[k], ch[q], sizeof(ch[k]));
		len[k] = len[p] + 1, pa[w] = pa[q] = k;
		while (~p && ch[p][c] == q) ch[p][c] = k, p = pa[p];
		l = w;
	}
	inline void build() {
		pa[0] = -1;
		for (int i = 1; i <= n; i++) add(s[i] - 'a');
	}

	int b[N<<1], c[N];
	inline void sort() {
		for (int i = 1; i <= n; i++) c[i] = 0;
		for (int i = 1; i <= t; i++) ++c[len[i]];
		for (int i = 1; i <= n; i++) c[i] += c[i-1];
		for (int i = 1; i <= t; i++) b[c[len[i]]--] = i;
	}
} sam;

map 版 SAM

struct SAM {
	int l, len[N<<1|1], pa[N<<1|1], t;
	map<char, int> ch[N<<1|1];
	inline void add(char c) {
		int w = ++t, p = l;
		len[w] = len[l] + 1;
		while (~p && !ch[p][c]) ch[p][c] = w, p = pa[p];
		if (!~p) return pa[l=w] = 0, void();
		int q = ch[p][c];
		if (len[p] + 1 == len[q]) return pa[l=w] = q, void();
		int k = ++t;
		pa[k] = pa[q], ch[k] = ch[q];
		len[k] = len[p] + 1, pa[w] = pa[q] = k;
		while (~p && ch[p][c] == q) ch[p][c] = k, p = pa[p];
		l = w;
	}
	inline void build() {
		pa[0] = -1;
		for (int i = 1; i <= n; i++) add(s[i]);
	}

	int b[N<<1|1], c[N];
	inline void sort() {
		for (int i = 1; i <= n; i++) c[i] = 0;
		for (int i = 1; i <= t; i++) ++c[len[i]];
		for (int i = 1; i <= n; i++) c[i] += c[i-1];
		for (int i = 1; i <= t; i++) b[c[len[i]]--] = i;
	}
} sam;

数论模板

分解质因数

inline vector<pair<ll, int>> divide(ll n) {
	vector<pair<ll, int>> p;
	for (ll i = 2; i * i <= n; i++)
		if (!(n % i)) {
			p.pb(mp(i, 0));
			while (!(n % i)) ++p.back().se, n /= i;
		}
	if (n > 1) p.pb(mp(n, 1));
	return p;
}

线性筛

namespace shai {
	const int N = 1e6 + 7;
	int p[N], v[N], phi[N], miu[N];

	inline void init(int n) {
		v[1] = phi[1] = miu[1] = 1;
		for (int i = 2; i <= n; i++) {
			if (!v[i]) p[++p[0]] = v[i] = i, phi[i] = i - 1, miu[i] = -1;
			for (int j = 1; j <= p[0] && i * p[j] <= n && p[j] <= v[i]; j++)
				v[i*p[j]] = p[j],
				phi[i*p[j]] = phi[i] * (p[j] - 1 + (p[j] == v[i])),
				miu[i*p[j]] = p[j] == v[i] ? 0 : -miu[i];
		}
	}
}

线性基

inline bool ins(int x) {
	for (int i = n - 1; ~i; i--)
		if (x >> i & 1) {
			if (!b[i]) return b[i] = x, 1;
			x ^= b[i];
		}
	return 0;
}

多项式模板

拉格朗日插值

const int N = 2e3 + 7;
int n;
modint k, x[N], y[N], ans;

int main() {
	rd(n), rd(k);
	for (int i = 1; i <= n; i++) rd(x[i]), rd(y[i]);
	for (int i = 1; i <= n; i++) {
		modint a = y[i], b = 1;
		for (int j = 1; j <= n; j++)
			if (i != j) a *= k - x[j], b *= x[i] - x[j];
		ans += a / b;
	}
	print(ans);
	return 0;
}

FFT

namespace FFT {
	const int N = 1 << 21 | 1;
	const double PI = acos(-1);
	struct I {
		double x, y;
		inline I() {}
		inline I(double x, double y) : x(x), y(y) {}
		inline I &operator = (int o) { return x = o, y = 0, *this; }
		inline I operator + (const I o) const { return I(x + o.x, y + o.y); }
		inline I operator - (const I o) const { return I(x - o.x, y - o.y); }
		inline I operator * (const I o) const {
			return I(x * o.x - y * o.y, x * o.y + y * o.x);
		}
	} a[N], b[N];
	inline void rd(I &x) { int o; ::rd(o), x = o; }
	inline void print(I x, char k = '\n') { ::print((int)(x.x + 0.5), k); }
	int n, m, k, l, r[N];
	inline void fft(I *a, int n, int x) {
		for (int i = 0; i < n; i++) if (i < r[i]) swap(a[i], a[r[i]]);
		for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1) {
			I W = I(cos(PI / k), x * sin(PI / k));
			for (int i = 0; i < n; i += o) {
				I w = I(1, 0);
				for (int j = 0; j < k; j++, w = w * W) {
					I x = a[i+j], y = w * a[i+j+k];
					a[i+j] = x + y, a[i+j+k] = x - y;
				}
			}
		}
	}
	inline void solve() {
		k = 1, l = 0;
		while (k <= n + m) k <<= 1, ++l;
		for (int i = 0; i < k; i++)
			r[i] = (r[i>>1] >> 1) | ((i & 1) << (l - 1));
		for (int i = n + 1; i < k; i++) a[i] = 0;
		for (int i = m + 1; i < k; i++) b[i] = 0;
		fft(a, k, 1), fft(b, k, 1);
		for (int i = 0; i < k; i++) a[i] = a[i] * b[i];
		fft(a, k, -1);
		for (int i = 0; i <= n + m; i++) a[i].x /= k;
	}
}

NTT

namespace NTT {
	const int N = 1 << 21 | 1;
	const modint g = 3, vg = 1 / g;
	int n, m, k, l, r[N];
	modint vk, a[N], b[N];
	inline void ntt(modint *a, int n, modint x) {
		for (int i = 0; i < n; i++)
			if (i < r[i]) swap(a[i], a[r[i]]);
		for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1) {
			modint W = x ^ ((P - 1) / o);
			for (int i = 0; i < n; i += o) {
				modint w = 1;
				for (int j = 0; j < k; j++, w *= W) {
					modint x = a[i+j], y = a[i+j+k] * w;
					a[i+j] = x + y, a[i+j+k] = x - y;
				}
			}
		}
	}
	inline void solve() {
		k = 1, l = 0;
		while (k <= n + m) k <<= 1, ++l;
		vk = (modint)1 / k;
		for (int i = 0; i < k; i++)
			r[i] = r[i>>1] >> 1 | (i & 1) << (l - 1);
		for (int i = n + 1; i < k; i++) a[i] = 0;
		for (int i = m + 1; i < k; i++) b[i] = 0;
		ntt(a, k, g), ntt(b, k, g);
		for (int i = 0; i < k; i++) a[i] *= b[i];
		ntt(a, k, vg);
		for (int i = 0; i <= n + m; i++) a[i] *= vk;
	}
}

FWT

int n, m;
modint A[N], B[N], a[N], b[N];

inline void in() {
	for (int i = 0; i < n; i++) a[i] = A[i], b[i] = B[i];
}

inline void get() {
	for (int i = 0; i < n; i++) a[i] *= b[i];
}

inline void out() {
	for (int i = 0; i < n; i++) print(a[i], " \n"[i==n-1]);
}

inline void OR(modint *f, modint x) {
	for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
		for (int i = 0; i < n; i += o)
			for (int j = 0; j < k; j++)
				f[i+j+k] += f[i+j] * x;
}

inline void AND(modint *f, modint x) {
	for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
		for (int i = 0; i < n; i += o)
			for (int j = 0; j < k; j++)
				f[i+j] += f[i+j+k] * x;
}

inline void XOR(modint *f, modint x) {
	for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
		for (int i = 0; i < n; i += o)
			for (int j = 0; j < k; j++) {
				modint p = f[i+j] * x, q = f[i+j+k] * x;
				f[i+j] = p + q, f[i+j+k] = p - q;
			}
}

int main() {
	rd(m), n = 1 << m;
	for (int i = 0; i < n; i++) rd(A[i]);
	for (int i = 0; i < n; i++) rd(B[i]);
	in(), OR(a, 1), OR(b, 1), get(), OR(a, P - 1), out();
	in(), AND(a, 1), AND(b, 1), get(), AND(a, P - 1), out();
	in(), XOR(a, 1), XOR(b, 1), get(), XOR(a, (modint)1 / 2), out();
	return 0;
}

计数模板

Prufer 序列

int n, f[N], p[N], d[N];
ll ans;

inline void TP() {
	for (int i = 1; i < n; i++) rd(f[i]), ++d[f[i]];
	for (int i = 1, j = 1; i <= n - 2; i++, j++) {
		while (d[j]) ++j; p[i] = f[j];
		while (i <= n - 2 && !--d[p[i]] && p[i] < j) p[i+1] = f[p[i]], ++i;
	}
	for (int i = 1; i <= n - 2; i++) ans ^= 1ll * i * p[i];
}

inline void PT() {
	for (int i = 1; i <= n - 2; i++) rd(p[i]), ++d[p[i]]; p[n-1] = n;
	for (int i = 1, j = 1; i < n; i++, j++) {
		while (d[j]) ++j; f[j] = p[i];
		while (i < n && !--d[p[i]] && p[i] < j) f[p[i]] = p[i+1], ++i;
	}
	for (int i = 1; i < n; i++) ans ^= 1ll * i * f[i];
}

数据结构模板

ST 表

int st[2][N][21];

inline void init(int *a, int n) {
	int w = log2(n);
	for (int i = 1; i <= n; i++)
		st[0][i][0] = st[1][i][0] = a[i];
	for (int i = 1; i <= w; i++)
		for (int l = 1, r = 1 << i; r <= n; l++, r++)
			st[0][l][i] = min(st[0][l][i-1], st[0][l+(1<<(i-1))][i-1]),
			st[1][l][i] = max(st[1][l][i-1], st[1][l+(1<<(i-1))][i-1]);
}

inline int Min(int l, int r) {
	int w = log2(r - l + 1);
	return min(st[0][l][w], st[0][r-(1<<w)+1][w]);
}

inline int Max(int l, int r) {
	int w = log2(r - l + 1);
	return max(st[1][l][w], st[1][r-(1<<w)+1][w]);
}

树状数组

struct BIT {
	vector<ll> c;
	inline BIT() {}
	inline BIT(int n) { c.resize(n); }
	inline void add(ui x, ll k) {
		while (x < c.size()) c[x] += k, x += x & -x;
	}
	inline ll ask(ui x) {
		ll k = 0;
		while (x) k += c[x], x -= x & -x;
		return k;
	}
};

线段树

struct SGT {
	struct T {
		int l, r;
		ll x, z;
	} t[N<<2|1];

	inline void update(int p) {
		t[p].x = t[ls].x + t[rs].x;
	}

	inline void work(int p, ll x) {
		t[p].x += x * (t[p].r - t[p].l + 1), t[p].z += x; 
	}

	inline void spread(int p) {
		if (t[p].z) work(ls, t[p].z), work(rs, t[p].z), t[p].z = 0;
	}

	void build(int p, int l, int r) {
		t[p].l = l, t[p].r = r;
		if (l == r) return t[p].x = a[l], void();
		build(ls, l, md), build(rs, md + 1, r);
		update(p);
	}

	void add(int p, int l, int r, ll x) {
		if (t[p].l >= l && t[p].r <= r) return work(p, x);
		spread(p);
		if (l <= md) add(ls, l, r, x);
		if (r > md) add(rs, l, r, x);
		update(p);
	}

	ll ask(int p, int l, int r) {
		if (t[p].l >= l && t[p].r <= r) return t[p].x;
		spread(p);
		ll ret = 0;
		if (l <= md) ret += ask(ls, l, r);
		if (r > md) ret += ask(rs, l, r);
		return ret;
	}
};

树链剖分

namespace HLD {
	int d[N], f[N], s[N], son[N], dfn[N], rnk[N], top[N], num;

	void dfs(int x) {
		s[x] = 1;
		for (int y : e[x])
			if (y != f[x]) {
				f[y] = x, d[y] = d[x] + 1;
				dfs(y), s[x] += s[y];
				if (s[y] > s[son[x]]) son[x] = y;
			}
	}

	void dfs(int x, int p) {
		dfn[x] = ++num, rnk[num] = x;
		top[x] = p;
		if (son[x]) dfs(son[x], p);
		for (int y : e[x])
			if (y != f[x] && y != son[x])
				dfs(y, y);
	}

	inline int lca(int x, int y) {
		while (top[x] != top[y]) {
			if (d[top[x]] < d[top[y]]) swap(x, y);
			x = f[top[x]];
		}
		return d[x] < d[y] ? x : y;
	}

	inline void main() {
		d[1] = 1, dfs(1), dfs(1, 1);
	}
}

LCT

struct LCT {
	int f[N], ch[N][2], s[N], v[N], a[N], c[N];
	#define lc ch[p][0]
	#define rc ch[p][1]
	#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1, c[p] = c[ch[p][0]] ^ c[ch[p][1]] ^ a[p]
	#define get(p) (p == ch[f[p]][1])
	#define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])
	#define isrt(p) (ch[f[p]][0] != p && ch[f[p]][1] != p)
	inline void spd(int p) {
		if (p && v[p]) {
			if (lc) rev(lc);
			if (rc) rev(rc);
			v[p] = 0;
		}
	}
	inline void rot(int p) {
		int x = f[p], y = f[x], u = get(p), v = get(x), o = isrt(x);
		f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
		f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
		if ((f[p] = y) && !o) ch[y][v] = p;
	}
	void pre(int p) {
		if (!isrt(p)) pre(f[p]);
		spd(p);
	}
	inline void splay(int p) {
		pre(p);
		for (int x = f[p]; !isrt(p); rot(p), x = f[p])
			if (!isrt(x)) rot(get(p) == get(x) ? x : p);
	}
	inline void access(int p) {
		for (int x = 0; p; p = f[x=p]) splay(p), rc = x, upd(p);
	}
	inline void mkrt(int p) {
		access(p), splay(p), rev(p);
	}
	inline void split(int x, int y) {
		mkrt(x), access(y), splay(y);
	}
	inline int fdrt(int p) {
		access(p), splay(p);
		while (lc) spd(p), p = lc;
		return splay(p), p;
	}
	inline bool link(int x, int y) {
		mkrt(x);
		return fdrt(y) != x && (f[x] = y);
	}
	inline bool cut(int x, int y) {
		mkrt(x);
		if (fdrt(y) != x || s[x] != 2) return 0;
		return f[y] = ch[x][1] = 0, upd(x), 1;
	}
	inline void chg(int p, int x) {
		mkrt(p), a[p] = x, upd(p);
	}
} lct;

FHQ Treap

struct Treap {
	int rt, tot, ch[N][2], a[N], d[N], s[N];
	#define lc ch[p][0]
	#define rc ch[p][1]
	#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1
	#define clr(p) ch[p][0] = ch[p][1] = a[p] = d[p] = s[p] = 0
	inline void split(int p, int k, int &x, int &y) {
		if (!p) return x = y = 0, void();
		if (a[p] <= k) x = p, split(rc, k, rc, y);
		else y = p, split(lc, k, x, lc);
		upd(p);
	}
	inline int merge(int x, int y) {
		if (!x || !y) return x | y;
		if (d[x] < d[y]) return ch[y][0] = merge(x, ch[y][0]), upd(y), y;
		return ch[x][1] = merge(ch[x][1], y), upd(x), x;
	}
	inline void ins(int k) {
		a[++tot] = k, s[tot] = 1, d[tot] = rand();
		if (!rt) return rt = tot, void();
		int x, y;
		split(rt, k, x, y), rt = merge(merge(x, tot), y);
	}
	inline int rnk(int k) {
		int x, y, ret;
		return split(rt, k - 1, x, y), ret = s[x] + 1, merge(x, y), ret;
	}
	inline int kth(int k) {
		int p = rt;
		while (1)
			if (k <= s[lc]) p = lc;
			else {
				k -= s[lc] + 1;
				if (!k) return a[p];
				p = rc;
			}
	}
	inline int pre(int k) {
		return kth(rnk(k) - 1);
	}
	inline int nxt(int k) {
		return kth(rnk(k + 1));
	}
	inline void del(int k) {
		int x, y, z;
		split(rt, k, x, z), split(x, k - 1, x, y);
		rt = merge(merge(x, merge(ch[y][0], ch[y][1])), z);
		clr(y);
	}
} treap;

普通莫队

int n, m, T, a[N], ans[N], now;
struct Q {
	int l, r, x, y, i;
	inline Q() {}
	inline Q(int l, int r, int i) : l(l), r(r), i(i) { x = l / T, y = r; }
	inline friend bool operator < (const Q &a, const Q &b) {
		return a.x == b.x ? (a.x & 1) ? a.y < b.y : a.y > b.y : a.x < b.x;
	}
} q[N];

inline void work(int x, int k) {
	
}

int main() {
	rd(n, m), T = n / sqrt(m), rda(a, n);
	for (int i = 1, l, r; i <= m; i++) rd(l, r), q[i] = Q(l, r, i);
	sort(q + 1, q + m + 1);
	for (int i = 1, l = 1, r = 0; i <= m; i++) {
		while (l > q[i].l) work(--l, 1);
		while (r < q[i].r) work(++r, 1);
		while (l < q[i].l) work(l++, -1);
		while (r > q[i].r) work(r--, -1);
		ans[q[i].i] = now;
	}
	for (int i = 1; i <= m; i++) print(ans[i]);
	return 0;
}

带修莫队

int n, m, k, T, a[N], u[N], v[N], ans[N], now;
struct Q {
	int l, r, t, x, y, z, i;
	inline Q() {}
	inline Q(int l, int r, int t, int i) : l(l), r(r), t(t), i(i) { x = l / T, y = r / T, z = t; }
	inline friend bool operator < (const Q &a, const Q &b) {
		return a.x == b.x ? a.y == b.y ? (a.y & 1) ? a.z < b.z : a.z > b.z : (a.x & 1) ? a.y < b.y : a.y > b.y : a.x < b.x;
	}
} q[N];

inline void work(int x, int k) {
	
}

inline void update(int i, int x) {
	
}

int main() {
	rd(n, m), T = pow(n, 2.0 / 3.0), rda(a, n);
	for (int i = 1, l, r, t = 0; i <= m; i++) {
		char o;
		rdc(o);
		if (o == 'Q') rd(l, r), ++k, q[k] = Q(l, r, t, k);
		else ++t, rd(u[t], v[t]);
	}
	sort(q + 1, q + k + 1);
	for (int i = 1, l = 1, r = 0, t = 0; i <= k; i++) {
		while (l > q[i].l) work(a[--l], 1);
		while (r < q[i].r) work(a[++r], 1);
		while (l < q[i].l) work(a[l++], -1);
		while (r > q[i].r) work(a[r--], -1);
		while (t < q[i].t) update(i, ++t);
		while (t > q[i].t) update(i, t--);
		ans[q[i].i] = now;
	}
	for (int i = 1; i <= k; i++) print(ans[i]);
	return 0;
}

图论模板

堆优化 Dijkstra 最短路

inline void dij(int S, int *d) {
	for (int i = 1; i <= n; i++) d[i] = inf, v[i] = 0;
	d[S] = 0, q.push(mp(0, S));
	while (q.size()) {
		int x = q.top().se;
		q.pop();
		if (v[x]) continue;
		v[x] = 1;
		for (pi o : e[x]) {
			int y = o.fi, z = o.se;
			if (d[y] > d[x] + z)
				d[y] = d[x] + z, q.push(mp(-d[y], y));
		}
	}
}

Prim 最小生成树

const int inf = 1 << 30;
int n, m, f[N], a[N][N], d[N];
bool v[N];
vi e[N];
ll ans;

inline void prim() {
	for (int i = 0; i <= n; i++) d[i] = inf;
	d[1] = 0;
	for (int i = 1; i <= n; i++) {
		int x = 0;
		for (int j = 1; j <= n; j++)
			if (!v[j] && d[j] < d[x]) x = j;
		v[x] = 1, ans += d[x];
		if (f[x]) e[x].pb(f[x]), e[f[x]].pb(x);
		for (int y = 1; y <= n; y++)
			if (!v[y] && d[y] > a[x][y])
				d[y] = a[x][y], f[y] = x;
	}
}

int main() {
	rd(n, m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			a[i][j] = inf;
	for (int i = 1; i <= n; i++) a[i][i] = 0;
	for (int i = 1, x, y, z; i <= m; i++)
		rd(x, y, z), a[x][y] = a[y][x] = min(a[x][y], z);
	prim();
	print(ans);
	return 0;
}

虚树

int s[N], t;
vi g[N];

inline vi virtual_tree(vi p) {
	sort(p.begin(), p.end(), [&](int x, int y) { return dfn[x] < dfn[y]; });
	vi q = p;
	for (int x : p) {
		int lca = HLD::lca(x, s[t]);
		if (lca != s[t]) {
			while (t && d[s[t-1]] >= d[lca]) g[s[t-1]].pb(s[t]), --t;
			if (lca != s[t]) g[lca].pb(s[t]), q.pb(s[t] = lca);
		}
		s[++t] = x;
	}
	while (t > 1) g[s[t-1]].pb(s[t]), --t;
	return t = 0, q;
}

匈牙利算法

namespace XYL {
	bool v[N];
	int f[N], ans;
	
	bool dfs(int x) {
		for (int y : e[x])
			if (!v[y]) {
				v[y] = 1;
				if (!f[y] || dfs(f[y])) return f[y] = x, 1;
			}
		return 0;
	}
	
	inline void main() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n + m; j++) v[j] = 0;
			ans += dfs(i);
		}
		for (int i = 1; i <= n + m; i++)
			if (f[i]) f[f[i]] = i;
	}
}

Dinic 最大流

namespace Dinic {
	const int N = 1e5 + 7, M = 2e6 + 7;
	const ll inf = 1e18;
	int n, S, T, d[N];
	int h[N], hi[N], e[M], t[M], tot;
	ll f[M], mxf;
	
	inline void add(int x, int y, ll z, bool o = 1) {
		e[++tot] = y, f[tot] = z, t[tot] = h[x], h[x] = tot;
		if (o) add(y, x, 0, 0);
	}
	
	inline bool bfs() {
		for (int i = 1; i <= n; i++) d[i] = 0;
		queue<int> q;
		q.push(S), d[S] = 1;
		while (q.size()) {
			int x = q.front();
			q.pop();
			for (int i = h[x]; i; i = t[i]) {
				int y = e[i];
				ll z = f[i];
				if (d[y] || !z) continue;
				q.push(y), d[y] = d[x] + 1;
				if (y == T) return 1;
			}
		}
		return 0;
	}
	
	ll dfs(int x, ll now = inf) {
		if (x == T) return now;
		ll rst = now;
		for (int &i = hi[x]; i; i = t[i]) {
			int y = e[i];
			ll z = f[i];
			if (d[y] != d[x] + 1 || !z) continue;
			ll k = dfs(y, min(z, rst));
			if (!k) d[y] = 0;
			else f[i] -= k, f[i^1] += k, rst -= k;
			if (!rst) break;
		}
		return now - rst;
	}
	
	inline void main() {
		while (bfs()) {
			for (int i = 1; i <= n; i++) hi[i] = h[i];
			ll now;
			while ((now = dfs(S))) mxf += now;
		}
	}
	
	inline void init(int _n, int _S, int _T) {
		n = _n, S = _S, T = _T, tot = 1, mxf = 0;
		for (int i = 1; i <= n; i++) h[i] = 0; 
	}
}

Dinic 最小费用最大流

namespace Dinic {
	const int N = 1e5 + 7, M = 2e6 + 7;
	const ll inf = 1e18;
	int n, S, T;
	int h[N], hi[N], e[M], t[M], tot;
	ll d[N], f[M], c[M], mxf, ans;
	bool v[N];
	
	inline void add(int x, int y, ll z, ll w, bool o = 1) {
		e[++tot] = y, f[tot] = z, c[tot] = w, t[tot] = h[x], h[x] = tot;
		if (o) add(y, x, 0, -w, 0);
	}
	
	inline bool bfs() {
		for (int i = 1; i <= n; i++) d[i] = inf, v[i] = 0;
		queue<int> q;
		q.push(S), d[S] = 0, v[S] = 1;
		while (q.size()) {
			int x = q.front();
			q.pop(), v[x] = 0;
			for (int i = h[x]; i; i = t[i]) {
				int y = e[i];
				ll z = f[i], w = c[i];
				if (d[y] <= d[x] + w || !z) continue;
				d[y] = d[x] + w;
				if (!v[y]) q.push(y), v[y] = 1;
			}
		}
		return d[T] != inf;
	}
	
	ll dfs(int x, ll now = inf) {
		if (x == T) return now;
		v[x] = 1;
		ll rst = now;
		for (int &i = hi[x]; i; i = t[i]) {
			int y = e[i];
			ll z = f[i], w = c[i];
			if (v[y] || d[y] != d[x] + w || !z) continue;
			ll k = dfs(y, min(z, rst));
			if (!k) d[y] = inf;
			else ans += k * w, f[i] -= k, f[i^1] += k, rst -= k;
			if (!rst) break;
		}
		v[x] = 0;
		return now - rst;
	}
	
	inline void main() {
		while (bfs()) {
			for (int i = 1; i <= n; i++) hi[i] = h[i];
			ll now;
			while ((now = dfs(S))) mxf += now;
		}
	}
	
	inline void init(int _n, int _S, int _T) {
		n = _n, S = _S, T = _T, tot = 1, mxf = 0, ans = 0;
		for (int i = 1; i <= n; i++) h[i] = 0; 
	}
}

无源汇上下界可行流

namespace no_ok_flow {
	const int N = 1e5 + 7;
	int n, S, T;
	ll d[N], s;
	inline void add(int x, int y, ll l, ll r) {
		Dinic::add(x, y, r - l), d[y] += l, d[x] -= l;
	}
	inline bool main() {
		for (int i = 1; i <= n; i++)
			if (d[i] > 0) Dinic::add(S, i, d[i]), s += d[i];
			else if (d[i] < 0) Dinic::add(i, T, -d[i]);
		Dinic::main();
		return Dinic::mxf == s;
	}
	inline void init(int _n) {
		n = _n, s = 0, S = n + 1, T = n + 2;
		Dinic::init(n + 2, S, T);
		for (int i = 1; i <= n; i++) d[i] = 0;
	}
}

有源汇上下界最大流

namespace yes_max_flow {
	const ll inf = 1e18;
	int n, S, T;
	inline bool main() {
		no_ok_flow::add(T, S, 0, inf);
		if (!no_ok_flow::main()) return 0;
		Dinic::S = S, Dinic::T = T, Dinic::mxf = 0;
		return Dinic::main(), 1;
	}
	inline void init(int _n, int _S, int _T) {
		n = _n, S = _S, T = _T;
		no_ok_flow::init(n);
	}
}

有源汇上下界最小流

namespace yes_min_flow {
	const ll inf = 1e18;
	int n, S, T;
	inline bool main() {
		no_ok_flow::main();
		no_ok_flow::add(T, S, 0, inf);
		Dinic::main();
		return Dinic::mxf == no_ok_flow::s;
	}
	inline void init(int _n, int _S, int _T) {
		n = _n, S = _S, T = _T;
		no_ok_flow::init(n);
	}
}

无源汇上下界最小费用可行流

namespace no_min_cost_flow {
	const int N = 1e5 + 7;
	int n, S, T;
	ll d[N], s;
	inline void add(int x, int y, ll l, ll r, ll w) {
		Dinic::add(x, y, r - l, w), d[y] += l, d[x] -= l;
	}
	inline bool main() {
		for (int i = 1; i <= n; i++)
			if (d[i] > 0) Dinic::add(S, i, d[i], 0), s += d[i];
			else if (d[i] < 0) Dinic::add(i, T, -d[i], 0);
		Dinic::main();
		return Dinic::mxf == s;
	}
	inline void init(int _n) {
		n = _n, s = 0, S = n + 1, T = n + 2;
		Dinic::init(n + 2, S, T);
		for (int i = 1; i <= n; i++) d[i] = 0;
	}
}