板子。

并查集
int findfa(int x) {return x == fa[x] ? x : fa[x] = findfa(fa[x]);}
nim游戏
        read(T);
	while(T--) {
		read(n); ans = 0;
		for(int x, i = 1; i <= n; ++i) read(x), ans ^= x;
		puts(ans ? "Yes" : "No");
	}

 

KMP
for(int i = 2, j = 0; i <= n; ++i) {
		while(j && s[i] != s[j+1]) j = nxt[j];
		if(s[j+1] == s[i]) ++j; nxt[i] = j;
	}
	for(int i = 1, j = 0; i <= m; ++i) {
		while(j > 0 && t[i] != s[j+1]) j = nxt[j];
		if(s[j+1] == t[i]) ++j;
		if(j == n) printf("%d\n", i-n+1);
	}

 

欧拉定理/扩展欧拉定理
#include <bits/stdc++.h>
using namespace std;
int a, P = 1e9+7, m, b, phi, flag;
void read(int &x) {
	char ch; while(ch = getchar(), ch < '!'); x = ch - 48; if(x > P) flag = 1, x %= P;
	while(ch = getchar(), ch > '!') {
		if(1ll * x * 10 >= P || (1ll * x * 10 % P + ch - 48) >= P) flag = P;
		x = (1ll * x * 10 % P + ch - 48) % P;
	}
}
int getphi(int x) {
	int res = x;
	for(int i = 2; i*i <= x; ++i)
		if(x % i == 0) {
			res = res / i * (i - 1);
			while(x % i == 0) x /= i;
		}
	if(x > 1) res = res / x * (x - 1);
	return res;
}
int power(int a, int b) {
	int res = 1;
	for(; b; a = 1ll*a*a%m, b >>= 1) if(b&1) res = 1ll*res*a%m;
	return res;
}
int main() {
	read(a); read(m);
	phi = getphi(m); P = phi;
	read(b);
	if(flag) b += phi;
	printf("%d\n", power(a, b));
}

 

Lucas
int C(int n, int m) {
	if(m > n) return 0;
	return 1ll * fac[n] * power(fac[m], P-2) * power(fac[n-m], P-2);
}
int Lucas(int n, int m) {
	if(m == 0) return 1;
	return 1ll * C(n%P, m%P) * Lucas(n/P, m/P) % P;
}

 

匈牙利算法
struct Edge {int to, next;} e[MAXN << 1];
int match[MAXN], n, m, E, tag, ans, h[MAXN], en, vis[MAXN];
void addedge(int u, int v) {e[en] = (Edge) {v, h[u]}; h[u] = en++;}
bool dfs(int u) {
	for(int v, i = h[u]; ~i; i = e[i].next) {
		if(vis[v = e[i].to] != tag) {
			vis[v] = tag;
			if(!match[v] || dfs(match[v])) {
				match[v] = u; return 1;
			}
		}
	} return 0;
}
int main() {
	read(n); read(m); read(E); memset(h, -1, sizeof h);
	for(int u, v, i = 1; i <= E; ++i) {
		read(u), read(v);
		if(u > n || v > m) continue;
		addedge(u, v);
	}
	for(int i = 1; i <= n; ++i) ++tag, ans += dfs(i);
	printf("%d\n", ans);
}
树状数组
void U(int x, int k) {for(; x <= n; t[x] += k, x += x&-x);}
int Q(int x) {int w = 0; for(; x; w += t[x], x -= x&-x); return w;}
线段树

(【模板】线段树2 代码)

#include <bits/stdc++.h>
#define int long long
#define L(u) (u<<1)
#define R(u) (u<<1|1)
#define mid ((l+r)>>1)
using namespace std;
const int MAXN = 100050;
void read(int &x) {
	char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
	while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
int t[MAXN << 2], add[MAXN << 2], mul[MAXN << 2], n, m, P, a[MAXN];
void ADD(int u, int l, int r, int k) {
	t[u] = (t[u] + k * (r - l + 1) % P) % P; add[u] = (add[u] + k) % P;
}
void MUL(int u, int l, int r, int k) {
	t[u] = t[u] * k % P; add[u] = add[u] * k % P; mul[u] = mul[u] * k % P;
}
void PU(int u) {t[u] = (t[L(u)] + t[R(u)]) % P;}
void PD(int u, int l, int r) {
	MUL(L(u), l, mid, mul[u]); MUL(R(u), mid+1, r, mul[u]); mul[u] = 1;
	ADD(L(u), l, mid, add[u]); ADD(R(u), mid+1, r, add[u]); add[u] = 0;
}
void build(int u, int l, int r) {
	mul[u] = 1; if(l == r) {t[u] = a[l]; return;}
	build(L(u), l, mid); build(R(u), mid+1, r); PU(u);
}
void MA(int u, int l, int r, int tl, int tr, int k) {
	if(tr < l || tl > r) return;
	if(tl <= l && r <= tr) {ADD(u, l, r, k); return;} PD(u, l, r);
	MA(L(u), l, mid, tl, tr, k); MA(R(u), mid+1, r, tl, tr, k); PU(u);
}
void MM(int u, int l, int r, int tl, int tr, int k) {
	if(tr < l || tl > r) return;
	if(tl <= l && r <= tr) {MUL(u, l, r, k); return;} PD(u, l, r);
	MM(L(u), l, mid, tl, tr, k); MM(R(u), mid+1, r, tl, tr, k); PU(u);
}
int Q(int u, int l, int r, int tl, int tr) {
	if(tr < l || tl > r) return 0;
	if(tl <= l && r <= tr) return t[u]; PD(u, l, r);
	return (Q(L(u), l, mid, tl, tr) + Q(R(u), mid+1, r, tl, tr)) % P;
}
signed main() {
	read(n); read(P);
	for(int i = 1; i <= n; ++i) read(a[i]);
	build(1, 1, n);
	read(m);
	for(int opt, x, y, k; m--; ) {
		read(opt); read(x); read(y);
		if(opt == 1) read(k), MM(1, 1, n, x, y, k);
		if(opt == 2) read(k), MA(1, 1, n, x, y, k);
		if(opt == 3) printf("%lld\n", Q(1, 1, n, x, y));
	}
}

 

Manacher
void Manacher() {
	int mr = 0, mid;
	for(int i = 0; i < n; ++i) {
		p[i] = i < mr ? min(p[(mid << 1) - i], p[mid] + mid - i) : 1;
		for(; s[i-p[i]] == s[i+p[i]]; ++p[i]);
		if(p[i] + i > mr) mr = i + p[i], mid = i;
	}
}

 

主席树
#include <bits/stdc++.h>
#define L(u) t[u].ch[0]
#define R(u) t[u].ch[1]
#define mid ((l + r) >> 1)
using namespace std;
const int MAXN = 100050;
void read(int &x) {
	char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
	while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
struct JZM_T {int ch[2], v;} t[MAXN << 6];
int cnt, rt[MAXN << 6], o[MAXN], a[MAXN], n, m;
void build(int &u, int l, int r) {
	t[u = ++cnt].v = 0;
	if(l != r) build(L(u), l, mid), build(R(u), mid+1, r);
}
void update(int &u, int v, int l, int r, int p, int k) {
	t[u = ++cnt] = t[v]; t[u].v += k;
	if(l != r) p <= mid ? update(L(u), L(v), l, mid, p, k) : update(R(u), R(v), mid+1, r, p, k);
}
int query(int tl, int tr, int l, int r, int k) {
	if(l == r) return o[l]; int s = t[L(tr)].v - t[L(tl)].v;
	return k <= s ? query(L(tl), L(tr), l, mid, k) : query(R(tl), R(tr), mid+1, r, k-s);
}
int main() {
	read(n); read(m);
	for(int i = 1; i <= n; ++i) read(a[i]), o[i] = a[i];
	sort(o+1, o+n+1); int _n = unique(o+1, o+n+1)-o-1; build(rt[0], 1, _n);
	for(int i = 1; i <= n; ++i)
		update(rt[i], rt[i-1], 1, _n, lower_bound(o+1, o+_n+1, a[i])-o, 1);
	for(int l, r, k; m--; ) {
		read(l); read(r); read(k);
		printf("%d\n", query(rt[l-1], rt[r], 1, _n, k));
	}
}

 

三分
double f(double x) {
	double res = 0, base = 1;
	for(int i = 1; i <= n + 1; ++i) res = res * x + a[i];
	return res;
}
int main() {
	scanf("%d%lf%lf", &n, &l, &r);
	for(int i = 1; i <= n + 1; ++i) scanf("%lf", &a[i]);
	while(fabs(r-l) >= eps) {
		double mid = (l + r) / 2;
		if(f(mid - eps) < f(mid + eps)) l = mid;
		else r = mid;
	}
	printf("%.5lf\n", l);
}
线性逆元
inv[1] = 1;
for(int i = 2; i <= n; ++i)
	inv[i] = 1ll * (P - P / i) % P * inv[P % i]	% P;
Kruscal
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200050;
void read(int &x) {
	char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
	while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
struct E {
	int u, v, w;
	bool operator < (const E &b) const {
		return w < b.w;
	}
} e[MAXN];
int n, m, fa[MAXN], cnt, ans;
int findfa(int x) {return x == fa[x] ? x : fa[x] = findfa(fa[x]);}
int main() {
	read(n); read(m);
	for(int i = 1; i <= n; ++i) fa[i] = i;
	for(int i = 1; i <= m; ++i) read(e[i].u), read(e[i].v), read(e[i].w);
	sort(e+1, e+m+1);
	for(int i = 1; i <= m; ++i) {
		int x = findfa(e[i].u), y = findfa(e[i].v);
		if(x == y) continue;
		ans += e[i].w; ++cnt;
		if(cnt == n-1) break;
		fa[x] = y;
	}
	printf("%lld\n", ans);
}

 

高斯消元
for(int i = 1; i <= n; ++i) {
	int p = i;
	for(int j = i + 1; j <= n; ++j)
		if(fabs(a[j][i]) > fabs(a[p][i])) p = j;
	if(a[p][i] == 0) {puts("No Solution"); return 0;}
	for(int j = 1; j <= n+1; ++j) swap(a[i][j], a[p][j]);
	for(int j = 1; j <= n; ++j) {
		if(i == j) continue;
		double t = a[j][i] / a[i][i];
		for(int k = i; k <= n+1; ++k) a[j][k] -= a[i][k] * t;
	}
}
for(int i = 1; i <= n; ++i) printf("%.2lf\n", a[i][n+1] / a[i][i]);
exgcd
lint exgcd(lint a, lint b, lint &x, lint &y) {
	if(!b) {x = 1; y = 0;  return a;}
	lint g = exgcd(b, a%b, x, y), t = x; 
	x = y; y = t - a / b * y; return g;
}
2-SAT&Tarjan
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4000050;
void read(int &x) {
	char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
	while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
struct Edge {int to, next;} e[MAXN << 1];
int n, m, col[MAXN], dfn[MAXN], low[MAXN], idx, cntcol, ins[MAXN], to, h[MAXN], en, top, stk[MAXN];
int X(int x, int p) {return p ? x+n : x;}
void addedge(int u, int v) {e[en] = (Edge) {v, h[u]}; h[u] = en++;}
void tarjan(int u) {
	dfn[u] = low[u] = ++idx;
	stk[++top] = u; ins[u] = 1;
	for(int v, i = h[u]; ~i; i = e[i].next)
		if(!dfn[v = e[i].to]) tarjan(v), low[u] = min(low[u], low[v]);
		else if(ins[v]) low[u] = min(low[u], dfn[v]);
	if(low[u] == dfn[u]) {
		++cntcol; int v;
		do {
			v = stk[top--];
			col[v] = cntcol;
			ins[v] = 0;
		} while(v != u);
	}
}
int main() {
	read(n); read(m); memset(h, -1, sizeof h);
	for(int u, v, p1, p2, i = 1; i <= m; ++i) {
		read(u); read(p1); read(v); read(p2);
		addedge(X(u, p1^1), X(v, p2));
		addedge(X(v, p2^1), X(u, p1));
	}
	for(int i = 1; i <= 2*n; ++i) if(!col[i]) tarjan(i);
	for(int i = 1; i <= n; ++i)
		if(col[X(i, 0)] == col[X(i, 1)]) {puts("IMPOSSIBLE"); return 0;}
	puts("POSSIBLE");
	for(int i = 1; i <= n; ++i)
		putchar(col[X(i, 0)] > col[X(i, 1)] ? '1' : '0'), putchar(' ');
	puts("");
}

 

Dinic
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
void read(int &x) {
	char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
	while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
struct Edge {int to, next, w;} e[MAXN << 1];
int n, m, s, t, h[MAXN], d[MAXN], en;
void addedge(int u, int v, int w) {
	e[en] = (Edge) {v, h[u], w}; h[u] = en++;
	e[en] = (Edge) {u, h[v], 0}; h[v] = en++;
}
bool bfs() {
	memset(d, -1, sizeof d); queue <int> q; q.push(s); d[s] = 0;
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(int v, i = h[u]; ~i; i = e[i].next)
			if(d[v = e[i].to] == -1 && e[i].w > 0)
				d[v] = d[u] + 1, q.push(v);
	}
	return d[t] != -1;
}
int dfs(int u, int f) {
	int r = 0;
	if(u == t) return f;
	for(int v, i = h[u]; ~i && r < f; i = e[i].next)
		if(d[(v = e[i].to)] == d[u] + 1 && e[i].w > 0) {
			int x = dfs(v, min(e[i].w, f-r));
			e[i].w -= x; e[i^1].w += x; r += x;
		}
	if(!r) d[u] = -1; return r;
}
int dinic() {
	int x, ans = 0;
	while(bfs()) while(x = dfs(s, 1e9)) ans += x;
	return ans;
}
int main() {
	read(n); read(m); read(s); read(t); memset(h, -1, sizeof h);
	for(int u, v, w, i = 1; i <= m; ++i) read(u), read(v), read(w), addedge(u, v, w);
	printf("%d\n", dinic());
}

 

费用流
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100050;
void read(int &x) {
	char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
	while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
struct Edge {int to, next, f, c;} e[MAXN << 1];
int h[MAXN], en, n, m, s, t, d[MAXN], vis[MAXN], pos[MAXN], fa[MAXN], flow[MAXN], mc, mf;
void addedge(int u, int v, int f, int c) {
	e[en] = (Edge) {v, h[u], f, c}; h[u] = en++;
	e[en] = (Edge) {u, h[v], 0, -c}; h[v] = en++;
}
bool SPFA() {
	memset(d, 63, sizeof d); memset(vis, 0, sizeof vis); memset(flow, 63, sizeof flow);
	queue <int> q; q.push(s); d[s] = 0; vis[s] = 1;
	while(!q.empty()) {
		int u = q.front(); q.pop(); vis[u] = 0;
		for(int v, i = h[u]; ~i; i = e[i].next)
			if(d[v = e[i].to] > d[u] + e[i].c && e[i].f) {
				d[v] = d[u] + e[i].c; pos[v] = i;
				fa[v] = u; flow[v] = min(flow[u], e[i].f);
				if(!vis[v]) vis[v] = 1, q.push(v);
			}
	} return flow[s] != flow[t];
}
void mcmf() {
	while(SPFA()) {
		mc += flow[t]; mf += flow[t] * d[t];
		for(int u = t; u != s; u = fa[u]) e[pos[u]].f -= flow[t], e[pos[u]^1].f += flow[t];
	}
}
int main() {
	read(n); read(m); read(s); read(t); memset(h, -1, sizeof h);
	for(int u, v, f, c, i = 1; i <= m; ++i) {
		read(u); read(v); read(f); read(c);
		addedge(u, v, f, c);
	}
	mcmf();
	printf("%d %d\n", mc, mf);
}
树剖

这个真的丢人了,写了半个小时

#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define L(u) ((u) << 1)
#define R(u) ((u) << 1 | 1)
#define int long long
using namespace std;
const int MAXN = 100050;
void read(int &x) {
	char ch; int f = 1; while(ch = getchar(), ch < '!' || ch == '-') if(ch == '-') f = -1;
	x = ch - 48; while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48; x *= f;
}
struct Edge {int to, next; } e[MAXN << 1];
int dep[MAXN], dfn[MAXN], id[MAXN], idx, fa[MAXN], top[MAXN], siz[MAXN], son[MAXN];
int t[MAXN << 2], tag[MAXN << 2], P, w[MAXN], n, Q, rt, h[MAXN], en;
void addedge(int u, int v) {e[en] = (Edge) {v, h[u]}; h[u] = en++;}
void ADD(int u, int l, int r, int k) {t[u] = (t[u] + 1ll*k*(r-l+1)%P) % P; tag[u] = (tag[u] + k) % P;}
void PD(int u, int l, int r) {ADD(L(u), l, mid, tag[u]); ADD(R(u), mid+1, r, tag[u]); tag[u] = 0;}
void PU(int u) {t[u] = (t[L(u)] + t[R(u)]) % P;}
void build(int u, int l, int r) {
	if(l == r) {t[u] = w[id[l]]; return; }
	build(L(u), l, mid); build(R(u), mid+1, r); PU(u); 
}
void upd(int u, int l, int r, int tl, int tr, int k) {
	if(tr < l || tl > r) return; if(tl <= l && r <= tr) ADD(u, l, r, k);
	else PD(u, l, r), upd(L(u), l, mid, tl, tr, k), upd(R(u), mid+1, r, tl, tr, k), PU(u);
}
int qry(int u, int l, int r, int tl, int tr) {
	if(tr < l || tl > r) return 0; if(tl <= l && r <= tr) return t[u]; PD(u, l, r);
	return (qry(L(u), l, mid, tl, tr) + qry(R(u), mid+1, r, tl, tr)) % P;
}
void dfs1(int u, int p) {
	fa[u] = p; siz[u] = 1; dep[u] = dep[p] + 1;
	for(int v, i = h[u]; ~i; i = e[i].next)
		if((v = e[i].to) != p) {
			dfs1(v, u); siz[u] += siz[v];
			if(siz[son[u]] < siz[v]) son[u] = v;
		}
}
void dfs2(int u, int p) {
	id[dfn[u] = ++idx] = u; top[u] = p;
	if(son[u]) dfs2(son[u], p);
	for(int v, i = h[u]; ~i; i = e[i].next)
		if((v = e[i].to) != fa[u] && v != son[u]) dfs2(v, v);
}
void addpath(int x, int y, int k) {
	for(; top[x] != top[y]; x = fa[top[x]]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		upd(1, 1, n, dfn[top[x]], dfn[x], k);
	}
	if(dep[x] > dep[y]) swap(x, y);
	upd(1, 1, n, dfn[x], dfn[y], k);
}
int qrypath(int x, int y) {
	int res = 0;
	for(; top[x] != top[y]; x = fa[top[x]]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		res = (res + qry(1, 1, n, dfn[top[x]], dfn[x])) % P;
	}
	if(dep[x] > dep[y]) swap(x, y);
	return (res + qry(1, 1, n, dfn[x], dfn[y])) % P;
}
void addroot(int x, int k) {upd(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, k); }
int qryroot(int x) {return qry(1, 1, n, dfn[x], dfn[x] + siz[x] - 1);}
signed main() {
	read(n); read(Q); read(rt); read(P); memset(h, -1, sizeof h);
	for(int i = 1; i <= n; ++i) read(w[i]);
	for(int u, v, i = 1; i < n; ++i) read(u), read(v), addedge(u, v), addedge(v, u);
	dfs1(rt, 0);
	dfs2(rt, rt); 
	build(1, 1, n); 
	for(int op, x, y, z; Q--; ) {
		read(op); read(x);
		if(op == 1) read(y), read(z), addpath(x, y, z);
		if(op == 2) read(y), printf("%lld\n", qrypath(x, y));
		if(op == 3) read(z), addroot(x, z);
		if(op == 4) printf("%lld\n", qryroot(x));
	}
}

 

dijkstra
void dijkstra() {
	memset(d, 0x3f, sizeof d);
	d[s] = 0; q.push((D) {s, 0});
	while(!q.empty()) {
		int u = q.top().u; q.pop();
		if(vis[u]) continue; vis[u] = 1;
		for(int v, i = h[u]; ~i; i = e[i].next)
			if(d[v = e[i].to] > d[u] + e[i].w) {
				d[v] = d[u] + e[i].w;
				if(!vis[v]) q.push((D) {v, d[v]});
			}
	}
}

 

矩阵快速幂
struct Maxtir {
	int a[5][5], n;
	void init(int _n, int x) {
		n = _n; memset(a, 0, sizeof a);
		for(int i = 1; i <= n; ++i) a[i][i] = x;
	}
	Maxtir operator * (const Maxtir &b) const {
		Maxtir c; c.init(3, 0);
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= n; ++j)
				for(int k = 1; k <= n; ++k)
					c.a[i][j] = (c.a[i][j] + 1ll*a[i][k]*b.a[k][j]%P) % P;
		return c;
	}
} ori, trans;
Maxtir power(Maxtir a, int b) {
	Maxtir res; res.init(3, 1);
	for(; b; a = a * a, b >>= 1) if(b&1) res = res * a;
	return res;
}
cdq
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100050;
void read(int &x) {
	char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
	while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
struct Dot {int x, y, z, w, ans;} b[MAXN], a[MAXN];
bool cmpy(Dot a, Dot b) {return a.y == b.y ? a.z < b.z : a.y < b.y;}
bool cmpx(Dot a, Dot b) {return a.x == b.x ? cmpy(a, b) : a.x < b.x;}
int n, m, _n, cnt[MAXN];
struct BITS {
	int t[MAXN];
	void U(int x, int k) {for(; x <= m; t[x] += k, x += x&-x);}
	int Q(int x) {int res = 0; for(; x; res += t[x], x -= x&-x); return res;}
} T;
void cdq(int l, int r) {
	if(l == r) return; int mid = (l + r) >> 1;
	cdq(l, mid); cdq(mid+1, r);
	sort(a+l, a+mid+1, cmpy); sort(a+mid+1, a+r+1, cmpy);
	int i = mid + 1, j = l;
	for(; i <= r; ++i) {
		for(; a[j].y <= a[i].y && j <= mid; ++j) T.U(a[j].z, a[j].w);
		a[i].ans += T.Q(a[i].z);
	} for(int k = l; k < j; ++k) T.U(a[k].z, -a[k].w);
}
int main() {
	read(_n); read(m);
	for(int i = 1; i <= _n; ++i) read(b[i].x), read(b[i].y), read(b[i].z);
	sort(b+1, b+_n+1, cmpx);
	for(int c = 0, i = 1; i <= _n; ++i) {
		++c;
		if(b[i].x != b[i+1].x || b[i].y != b[i+1].y || b[i].z != b[i+1].z)
			a[++n] = b[i], a[n].w = c, c = 0;
	} cdq(1, n);
	for(int i = 1; i <= n; ++i) cnt[a[i].ans + a[i].w - 1] += a[i].w;
	for(int i = 0; i < _n; ++i) printf("%d\n", cnt[i]);
}

 

LCA
int Min(int x, int y) {return dep[x] < dep[y] ? x : y;}
void dfsRMQ(int u, int p) {
	st[++idx][0] = u; dfn[u] = idx; dep[u] = dep[p] + 1;
	for(int v, i = h[u]; ~i; i = e[i].next)
		if((v = e[i].to) != p) dfsRMQ(v, u), st[++idx][0] = u;
}
void LCAinit() {
	for(int i = 2; i <= (n << 1); ++i) lg2[i] = lg2[i>>1] + 1;
	dep[1] = 1; dfsRMQ(rt, 0);
	for(int j = 1; j < 20; ++j)
		for(int i = 1; i + (1 << j) <= (n << 1); ++i)
			st[i][j] = Min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
}
int LCA(int x, int y) {
	x = dfn[x]; y = dfn[y];
	if(x > y) swap(x, y);
	int k = lg2[y-x+1];
	return Min(st[x][k], st[y-(1<<k)+1][k]);
}

 

AC自动机
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 50;
int ap[MAXN], m;
char S[250][250], T[MAXN];
struct SoumAsuMire {
	int ch[MAXN][26], cnt, last[MAXN], f[MAXN], tag[MAXN];
	void clear() {
		memset(ch, 0, sizeof ch); memset(last, 0, sizeof last); memset(f, 0, sizeof f);
		memset(tag, 0, sizeof tag); memset(ap, 0, sizeof ap); cnt = 0;
	}
	void insert(char *s, int id) {
		int u = 0, n = strlen(s);
		for(int i = 0; i < n; ++i) {
			int c = s[i] - 'a';
			u = ch[u][c] ? ch[u][c] : ch[u][c] = ++cnt;
		} tag[u] = id;
	}
	void init() {
		queue <int> q; q.push(0);
		while(!q.empty()) {
			int u = q.front(), k = f[u]; q.pop();
			for(int c = 0; c < 26; ++c) {
				int v = ch[u][c];
				if(!v) {ch[u][c] = ch[k][c]; continue;}
				f[v] = u ? ch[k][c] : 0;
				last[v] = tag[f[v]] ? f[v] : last[f[v]];
				q.push(v);
			}
		}
	}
	void query(char *t) {
		int u = 0, n = strlen(t), res = 0;
		for(int i = 0; i < n; ++i) {
			int c = t[i] - 'a';
			u = ch[u][c];
			for(int v = u; v; v = last[v]) if(tag[v]) ++ap[tag[v]];
		}
		for(int i = 1; i <= m; ++i) res = max(res, ap[i]);
		printf("%d\n", res);
		for(int i = 1; i <= m; ++i)
			if(res == ap[i]) printf("%s\n", S[i]);
	}
} SAM;
int main() {
	while(scanf("%d", &m) && m) {
		SAM.clear();
		for(int i = 1; i <= m; ++i) {
			scanf("%s", S[i]);
			SAM.insert(S[i], i);
		}
		SAM.init();
		scanf("%s", T);
		SAM.query(T);
	}
}

 

ST表

#define bl(x) ((x-1)/siz+1)
#define L(x) ((x-1)*siz+1)
#define R(x) std::min(x*siz, n)
int st[MAXN][21], n, m, lg2[MAXN];
void ST_Build() {
	for(int j = 1; j <= 21; ++j)
		for(int i = 1; i + (1 << j) - 1 <= n; ++i)
			st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);
}
int ST_query(int l, int r) {
	int k = lg2[r-l+1];
	return max(st[l][k], st[r-(1<<k)+1][k]);
}
int main() {
	read(n); read(m);
	for(int i = 2; i <= n; ++i) lg2[i] = lg2[i>>1] + 1;
	for(int i = 1; i <= n; ++i) read(st[i][0]); ST_Build();
	for(int l, r; m--; ) {
		read(l); read(r);
		printf("%d\n", ST_query(l, r));
	}
}

 

ST表(邪教)

 


#define bl(x) ((x-1)/siz+1)
#define L(x) ((x-1)*siz+1)
#define R(x) std::min(x*siz, n)
int st[B][15], _n, n, a[MAXN], pre[MAXN], suf[MAXN], m, lg2[MAXN];
void STbuild() {
	for(int j = 1; j <= 12; ++j)
		for(int i = 1; i+(1<<j)-1 <= _n; ++i)
			st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);
}
int STquery(int l, int r) {
	if(l > r) return 0;
	int k = lg2[r-l+1];
	return max(st[l][k], st[r-(1<<k)+1][k]);
}
int main() {
	fastIO::init(); n = read(); m = read(); _n = bl(n);
	for(int i = 2; i <= n; ++i) lg2[i] = lg2[i>>1] + 1;
	for(int i = 1; i <= n; ++i) a[i] = read(), st[bl(i)][0] = max(st[bl(i)][0], a[i]);
	for(int i = 1; i <= _n; ++i) {
		pre[L(i)] = a[L(i)]; suf[R(i)] = a[R(i)];
		for(int j = L(i)+1; j <= R(i); ++j) pre[j] = max(pre[j-1], a[j]);
		for(int j = R(i)-1; j >= L(i); --j) suf[j] = max(suf[j+1], a[j]);
	}
	STbuild();
	for(int res, l, r; m--; ) {
		l = read(); r = read();
		if(bl(l) == bl(r)) {
			res = 0;
			for(int i = l; i <= r; ++i) res = max(res, a[i]);
			print(res);
		} else print(max(STquery(bl(l)+1, bl(r)-1), max(suf[l], pre[r])));
		print('\n');
	} fastIO::flush();
}
点分治
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000050;
void read(int &x) {
	char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
	while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
struct Edge {int to, next, w;} e[MAXN << 1];
int n, m, siz[MAXN], rt, f[MAXN], ans[10000050], h[MAXN], en, vis[MAXN], dis[MAXN], stk[MAXN], top;
void addedge(int u, int v, int w) {e[en] = (Edge) {v, h[u], w}; h[u] = en++;}
void getroot(int u, int p, int S) {
	siz[u] = 1, f[u] = 0;
	for(int v, i = h[u]; ~i; i = e[i].next)
		if((v = e[i].to) != p && !vis[v])
			getroot(v, u, S), siz[u] += siz[v], f[u] = max(f[u], siz[v]);
	f[u] = max(f[u], S - siz[u]); rt = f[u] < f[rt] ? u : rt;
}
void getdis(int u, int p) {
	stk[++top] = dis[u];
	for(int v, i = h[u]; ~i; i = e[i].next)
		if((v = e[i].to) != p && !vis[v])
			dis[v] = dis[u] + e[i].w, getdis(v, u);
}
void solve(int u, int w, int t) {
	top = 0, dis[u] = w, getdis(u, 0);
	for(int i = 1; i <= top; ++i)
		for(int j = 1; j <= top; ++j)
			if(i != j) ans[stk[i] + stk[j]] += t;
	//这一段统计答案复杂度是错的,但这个部分因题而异,作为模板没有大碍。 
}
void devide(int u) {
	solve(u, 0, 1); vis[u] = 1;
	for(int v, i = h[u]; ~i; i = e[i].next)
		if(!vis[(v = e[i].to)]) {
			solve(v, e[i].w, -1), rt = 0, f[0] = n;
			getroot(v, u, siz[u]), devide(rt);
		}
}
int main() {
	read(n); read(m); memset(h, -1, sizeof h);
	for(int u, v, w, i = 1; i < n; ++i)
		read(u), read(v), read(w),
		addedge(u, v, w), addedge(v, u, w);
	rt = 0, f[0] = n, getroot(1, 0, n), devide(rt);
	for(int k; m--; ) read(k), puts(ans[k] ? "AYE" : "NAY");
}

 

后缀自动机
struct SoumAsuMire {
	int ch[MAXN][26], fa[MAXN], len[MAXN], cnt, last, siz[MAXN], c[MAXN], a[MAXN];
	void init() {
		memset(ch, 0, sizeof ch); memset(fa, 0, sizeof fa); memset(len, 0, sizeof len);
		memset(c, 0, sizeof c); memset(a, 0, sizeof a); memset(siz, 0, sizeof siz); last = cnt = 1;
	}
	void insert(int c) {
		int p = last, np = ++cnt; last = np; len[np] = len[p] + 1;
		for(; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
		if(!p) fa[np] = 1;
		else {
			int q = ch[p][c];
			if(len[q] == len[p] + 1) fa[np] = q;
			else {
				int nq = ++cnt; len[nq] = len[p] + 1;
				memcpy(ch[nq], ch[q], sizeof ch[q]);
				fa[nq] = fa[q]; fa[q] = fa[np] = nq;
				for(; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
			}
		} siz[np] = 1;
	}
	void build(char *s) {
		int n = strlen(s);
		for(int i = 0; i < n; ++i) insert(s[i] - 'a');
	}
	lint GetSize() {
		lint ans = 0;
		for(int i = 1; i <= cnt; ++i) ++c[len[i]];
		for(int i = 1; i <= cnt; ++i) c[i] += c[i-1];
		for(int i = 1; i <= cnt; ++i) a[c[len[i]]--] = i;
		for(int i = cnt; i; --i) {
			int p = a[i];
			siz[fa[p]] += siz[p];
			if(siz[p] > 1) ans = max(1ll * siz[p] * len[p], ans);
		} return ans;
	}
} SAM;

 

UPDATING……

怎么都这么短啊喂

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

正在获取,请稍候...
00:00/00:00