省选模板：一些准备

有一些出场率比较高的板子，现在还不能完全确定打对的，尽快填了吧。

- [x] Link-Cut-Tree
- [x] 非旋转Treap
- [x] 2-SAT
- [x] 费用流
- [x] exgcd/excrt
- [x] BSGS
- [x] 后缀自动机 (MRT)
- [ ] Min-25筛
- [x] 上下界网络流
- [x] AC自动机
- [x] 边/点双连通分量 (MRT)
- [x] 凸包
- [x] 半平面交
- [x] Manacher (MRT)
- [x] 回文自动机 (MRT)
- [x] 二次剩余($(c+i)^{(p+1)/2},(c^2-a)^{(p-1)/2}\neq 1$)/原根(原根太简单，好写好懂，不打了)
- [ ] 辛普森积分(已经弃坑)
- [x] kosaraju/tarjan
- [ ] KDtree
- [x] 匈牙利算法 (MRT)
- [x] 线性基 (MRT)
- [x] cdq分治
- [x] 虚树
- [ ] 点分治 (MRT)

虚树：
```
#include<cstdio>
#include<algorithm>
#include<vector>
#define LL long long
using namespace std;
const int maxn = 2e6 + 5;
const int L = 19;
struct edge {
	int v, next;
} e[maxn << 1];
int head[maxn], cnt, n, m, q, u, v, sz[maxn];
void adde(const int &u, const int &v) {
	e[++cnt] = (edge) {v, head[u]};
	head[u] = cnt;
}
inline int ABS(int x) {return x < 0 ? -x : x;}

int f2[maxn][20], d[maxn], dfn[maxn], dcnt;
void pre(int u, int p) {
	dfn[u] = ++dcnt;
	f2[u][0] = p, d[u] = d[p] + 1, sz[u] = 1;
	for(register int i = 1; i <= L; ++i)
		f2[u][i] = f2[f2[u][i - 1]][i - 1];
	for(register int i = head[u]; i; i = e[i].next)
		if(e[i].v != p) pre(e[i].v, u), sz[u] += sz[v];
}

int LCA(int u, int v) {
	if(d[u] < d[v]) swap(u, v);
	for(register int i = L; i >= 0; --i)
		if(d[f2[u][i]] >= d[v]) u = f2[u][i];
	if(u == v) return v;
	for(register int i = L; i >= 0; --i) {
		if(f2[u][i] == f2[v][i]) continue;
		u = f2[u][i], v = f2[v][i];
	}
	return f2[u][0];
}

int GetKF(int u, int k) {
	for(register int i = 1 << L, p = L; i; i >>= 1, --p)
		if(k & i) u = f2[u][p];
	return u;
}

bool cmp_dfn(const int &a, const int &b) {
	return dfn[a] < dfn[b];
}

namespace VT {
	edge e[maxn << 1]; 
	int head[maxn], cnt, tmp[maxn], tcnt;
	void adde(const int &u, const int &v) {
		//printf("%d -----> %d\n", u, v);
		e[++cnt] = (edge) {v, head[u]};
		head[u] = cnt, tmp[++tcnt] = u, tmp[++tcnt] = v;
	}
	int stk[maxn], top, is_key[maxn], sz[maxn], f[maxn], g[maxn];
	void ins(int x) {
		if(!top) return stk[++top] = x, void();
		int lca = LCA(stk[top], x);
		if(lca == stk[top]) 
			return stk[++top] = x, void();
		while(top > 1 && dfn[stk[top - 1]] > dfn[lca]) 
			adde(stk[top - 1], stk[top]), --top;
		--top, adde(lca, stk[top + 1]);
		if(stk[top] != lca) stk[++top] = lca;
		stk[++top] = x;
	}
	void DP(int n, int u, int p, int &mx, int &mn, LL &ans) {
		sz[u] = is_key[u];
		int fv = 0, gv = 0;
		if(is_key[u]) f[u] = 0, g[u] = 0;
		else f[u] = 0x3f3f3f3f, g[u] = -0x3f3f3f3f;
		for(register int i = head[u]; i; i = e[i].next) {
			int v = e[i].v;
			if(v == p) continue;
			DP(n, v, u, mx, mn, ans), sz[u] += sz[v];
			if(f[u] > f[v] + (d[v] - d[u]))
				f[u] = f[v] + (d[v] - d[u]), fv = v;
			if(g[u] < g[v] + (d[v] - d[u]))
				g[u] = g[v] + (d[v] - d[u]), gv = v;
		}
		mx = max(mx, g[u]);
		for(register int i = head[u]; i; i = e[i].next) {
			int v = e[i].v;
			if(v == p) continue;
			if(v != fv) mn = min(mn, f[u] + f[v] + d[v] - d[u]);
			if(v != gv) mx = max(mx, g[u] + g[v] + d[v] - d[u]);
			ans += 1ll * (n - sz[v]) * sz[v] * (d[v] - d[u]);
		}
	}
	void GetVT(vector<int > &A) {
		int l = A.size();
		for(register int i = 0; i < l; ++i) 
			is_key[A[i]] = 1;
		sort(A.begin(), A.end(), cmp_dfn);
		for(register int i = 0; i < l; ++i) ins(A[i]);
		while(top > 1) {adde(stk[top - 1], stk[top]), --top;}
		int rt = stk[top], mn = 0x3f3f3f3f, mx = 0;
		LL ans = 0;
		DP(l, rt, 0, mx, mn, ans);
		printf("%lld %d %d\n", ans, mn, mx);
		for(register int i = 0; i < l; ++i) 
			is_key[A[i]] = 0;
		for(register int i = 1; i <= tcnt; ++i)
			head[tmp[i]] = 0, sz[tmp[i]] = 0;
		cnt = 0, top = 0, tcnt = 0;
	}
}
vector<int > V;
int main() {
	scanf("%d", &n);
	for(register int i = 1; i < n; ++i)	{
		scanf("%d%d", &u, &v);
		adde(u, v), adde(v, u);
	}
	pre(1, 0);
	scanf("%d", &q);
	for(register int i = 1; i <= q; ++i) {
		scanf("%d", &m), V.clear();
		for(register int j = 1; j <= m; ++j) {
			scanf("%d", &u);
			V.push_back(u);
		}
		VT::GetVT(V);
	}
	return 0;
}
```

二次剩余：
```
#include<cstdio>
#include<cstdlib>
using namespace std;
int mod;
int c, sqw;

int fpow(int a, int b) {
	int ans = 1;
	while(b) {
		if(b & 1) ans = 1ll * ans * a % mod;
		a = 1ll * a * a % mod, b >>= 1;
	}
	return ans;
}
int plus(int a, int b) {
	return a + b >= mod ? a + b - mod : a + b;
}
int minus(int a, int b) {
	return a - b < 0 ? a - b + mod : a - b;
}
int mul(int a, int b) {
	return 1ll * a * b % mod;
}
int is_sq(int x) {
	return fpow(x, (mod - 1) / 2) == 1; 
}
void GetC(int a) {
	c = rand() % mod;
	while(is_sq(minus(mul(c, c), a)))
		c = rand() % mod;
	sqw = minus(mul(c, c), a);
}
struct NE {
	int r, i;
	NE operator +(const NE &A) const {
		return (NE) {plus(A.r, r), plus(A.i, i)};
	}
	NE operator *(const NE &A) const {
		return (NE) {plus(mul(A.r, r), mul(mul(A.i, i), sqw)), 
					plus(mul(A.i, r), mul(i, A.r))};
	}
};
NE fpow(NE a, int b) {
	NE ans = (NE){1, 0};
	while(b) {
		if(b & 1) ans = ans * a;
		a = a * a, b >>= 1;
	}
	return ans;
}

int sqrt(int x) {
	if(!is_sq(x)) return -1;
	GetC(x);
	NE ans = fpow((NE) {c, 1}, (mod + 1) / 2);
	return ans.r;
}

int main() {
	srand(20020327);
	int t, n;
	scanf("%d", &t);
	while(t--) {
		scanf("%d%d", &n, &mod), n %= mod;
		if(mod == 2) {
			printf("1\n");
			continue;
		}
		int ans = sqrt(n);
		if(ans < 0) printf("No root\n");
		else {
			if(mod - ans < ans)
			printf("%d %d\n", mod - ans, ans);
			else 
			printf("%d %d\n", ans, mod - ans);
		}
	}
	return 0;
}
```

后缀自动机：
```
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
const int maxn = 2e6 + 5;
namespace SAM {
	int trie[maxn][26], fa[maxn], len[maxn], rt[maxn];
	LL sz[maxn];int cnt = 1, last = 1;
	void add(int x, const char &c) {
		int id = c - 'a';
		int p = last, np = ++cnt;
		last = np, len[np] = x + 1;
		rt[np] = 1;
		while(p && !trie[p][id])
			trie[p][id] = np, p = fa[p];
		if(!p) fa[np] = 1;
		else {
			int q = trie[p][id];
			if(len[q] == len[p] + 1) fa[np] = q;
			else {
				int lca = ++cnt;
				len[lca] = len[p] + 1;
				fa[lca] = fa[q];
				fa[q] = fa[np] = lca;
				memcpy(trie[lca], trie[q], sizeof(trie[q]));
				while(p && trie[p][id] == q)
					trie[p][id] = lca, p = fa[p];
			}
		}
	}
	int ton[maxn], nds[maxn];
	void TopMerge() {
		for(register int i = 1; i <= cnt; ++i)
			++ton[len[i]];
		for(register int i = 1; i <= cnt; ++i)
			ton[i] += ton[i - 1];
		for(register int i = 1; i <= cnt; ++i)
			nds[ton[len[i]]--] = i;
		for(register int i = cnt; i >= 1; --i)
			rt[fa[nds[i]]] += rt[nds[i]];
	}
	void dfs(int u, int t) {
		sz[u] = t ? rt[u] : 1;
		for(register int i = 0; i < 26; ++i) {
			int v = trie[u][i];
			if(!v) continue;
			if(!sz[v]) dfs(v, t);
			sz[u] += sz[v];
		}
	}
	char ans[maxn]; int bk;
	bool GetK(int u, LL k, int t) {
		for(register int i = 0; i < 26; ++i) {
			int v = trie[u][i];
			int sv = t ? rt[v] : 1;
			if(!v) continue;
			if(sz[v] >= k) {
				ans[bk++] = i + 'a';
				if(k <= sv) return 1;
				return GetK(v, k - sv, t);
			} else {k -= sz[v];}
		}
		return 0;
	}
}
char s[maxn];int t; LL k;
int main() {
	//freopen("string2.in", "r", stdin);
	scanf("%s", s);
	scanf("%d%lld", &t, &k);
	int l = strlen(s);
	for(register int i = 0; i < l; ++i)
		SAM::add(i, s[i]);
	SAM::TopMerge();
	SAM::dfs(1, t);
	if(!SAM::GetK(1, k, t))
		{printf("-1"); return 0;}
	SAM::ans[SAM::bk] = 0;
	printf("%s", SAM::ans);
	return 0;
}
```

匈牙利算法：
```
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 1e6 + 5;
struct edge {
	int v, next;
} e[maxn << 1];
int mch[maxn], vis[maxn], n, m, E, head[maxn], cnt, ans;
void adde(const int &u, const int &v) {
	e[++cnt] = (edge) {v, head[u]};
	head[u] = cnt;
}
int u, v;
bool dfs(int u) {
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if(!vis[v]) {
			vis[v] = 1;
			if(!mch[v] || dfs(mch[v])) {
				mch[v] = u;
				return 1;
			}
		}
	}
	return 0;
}

int main() {
	scanf("%d%d%d", &n, &m, &E);
	for(register int i = 1; i <= E; ++i) {
		scanf("%d%d", &u, &v);
		if(v > m || u > n) continue;
		adde(u, v);
	}
	ans = 0;
	for(register int i = 1; i <= n; ++i) {
	    //vis判回去不清空，爆零两行泪
		memset(vis, 0, sizeof(int) * (n + 4));
		ans += dfs(i);
	}
	printf("%d", ans);
	return 0;
}
```

上下界最小流：
```
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m, S, T, u, v, U, D;
namespace Dinic {
	const int maxn = 6e5 + 5;
	struct edge {
		int v, w, next;
	} e[maxn << 1];
	int head[maxn], iter[maxn], cnt, SS, TT, dcnt, sum;
	void init(int n) {
		memset(head, -1, sizeof(int) * (n + 5));
		SS = n + 1, TT = n + 2;
	}
	void adde(const int &u, const int &v, const int &w) {
		e[cnt] = (edge) {v, w, head[u]};
		head[u] = cnt++;
		e[cnt] = (edge) {u, 0, head[v]};
		head[v] = cnt++;
	}
	void Add(const int &u, const int &v, const int &U, const int &D) {
		sum += D;
		adde(SS, v, D), adde(u, TT, D), adde(u, v, U - D);
	}
	int layer[maxn];
	int bfs(int S, int T) {
		memset(layer, 0, sizeof(int) * (n + 4));
		memcpy(iter, head, sizeof(int) * (n + 4));
		queue<int > q;
		q.push(S), layer[S] = 1;
		while(!q.empty()) {
			int u = q.front();
			q.pop();
			for(register int i = head[u]; ~i; i = e[i].next) {
				int v = e[i].v;
				if(!e[i].w || layer[v]) continue;
				layer[v] = layer[u] + 1;
				q.push(v);
			}
		}
		return layer[T];
	}
	int dfs(int u, int t, int mn) {
		int ret = 0, tmp;
		if(u == t) return mn;
		for(register int &i = iter[u]; ~i; i = e[i].next) {
			int v = e[i].v;
			if(!e[i].w || layer[v] != layer[u] + 1) continue;
			tmp = dfs(v, t, min(e[i].w, mn - ret));
			ret += tmp, e[i].w -= tmp, e[i ^ 1].w += tmp;
			if(ret == mn) return ret;
		}
		return ret;
	}
	int Dinic(int S, int T) {
		int ans = 0;
		while(bfs(S, T)) 
			{ans += dfs(S, T, inf);}
		return ans;
	}
	int work(int S, int T) {
		adde(T, S, inf);
		int rn = cnt - 2;
		int low = Dinic(SS, TT); 
		int ans = e[rn + 1].w;
		e[rn].w = e[rn + 1].w = 0;
		if(low < sum)
			return printf("please go home to sleep"), -1;
		ans -= Dinic(T, S);
		return ans;
	}
}

int main() {
	scanf("%d%d%d%d", &n, &m, &S, &T), Dinic::init(n);
	for(register int i = 1; i <= m; ++i) 
		scanf("%d%d%d%d", &u, &v, &D, &U), Dinic::Add(u, v, U, D);
	int ans = Dinic::work(S, T);
	if(~ans) printf("%d", ans);
	return 0;
}
```

上下界最大流：
```
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
namespace Dinic {
	const int maxn = 1e5 + 5;
	struct edge {
		int v, w, next;
	} e[maxn << 1];
	int head[maxn], cnt, SS, TT, dcnt, sum;
	void init(int n) {
		memset(head, -1, sizeof(int) * (n + 5));
		SS = n + 1, TT = n + 2;
	}
	void adde(const int &u, const int &v, const int &w) {
		e[cnt] = (edge) {v, w, head[u]};
		head[u] = cnt++;
		e[cnt] = (edge) {u, 0, head[v]};
		head[v] = cnt++;
	}
	void Add(const int &u, const int &v, const int &U, const int &D) {
		sum += D;
		adde(SS, v, D), adde(u, TT, D), adde(u, v, U - D);
	}
	int layer[maxn];
	int bfs(int S, int T) {
		memset(layer, 0, sizeof(layer));
		queue<int > q;
		q.push(S), layer[S] = 1;
		while(!q.empty()) {
			int u = q.front();
			q.pop();
			for(register int i = head[u]; ~i; i = e[i].next) {
				int v = e[i].v;
				if(!e[i].w || layer[v]) continue;
				layer[v] = layer[u] + 1;
				q.push(v);
			}
		}
		return layer[T];
	}
	int dfs(int u, int t, int mn) {
		int ret = 0, tmp;
		if(u == t) return mn;
		for(register int i = head[u]; ~i; i = e[i].next) {
			int v = e[i].v;
			if(!e[i].w || layer[v] != layer[u] + 1) continue;
			tmp = dfs(v, t, min(e[i].w, mn - ret));
			ret += tmp, e[i].w -= tmp, e[i ^ 1].w += tmp;
			if(ret == mn) return ret;
		}
		return ret;
	}
	int Dinic(int S, int T) {
		int ans = 0;
		while(bfs(S, T)) 
			{ans += dfs(S, T, inf);}
		return ans;
	}
	int work(int S, int T) {
		adde(T, S, inf);
		int rn = cnt - 2;
		int low = Dinic(SS, TT); 
		int ans = e[rn + 1].w;
		e[rn].w = e[rn + 1].w = 0;
		if(low < sum)
			return printf("please go home to sleep"), -1;
		ans += Dinic(S, T);
		return ans;
	}
}

int n, m, S, T, u, v, U, D;

xxj(with 消元成最简):
```
#include<cstdio>
#define LL long long
using namespace std;

struct Linear_Base {
	LL mat[65];
	void ins(LL x) {
		for(register LL i = 1ll << 50, p = 50; i; i >>= 1, --p) {
			if(!(x & i)) continue;
			if(!mat[p]) {mat[p] = x; break;}
			x ^= mat[p];
		}	
	}
	void smp() {
		for(register LL i = 1ll << 50, p = 50; i; i >>= 1, --p) {
			for(register int j = p + 1; j <= 50; ++j)
				if(mat[j] & i) mat[j] ^= mat[p];
		}
	}
	LL solve() {
		LL ans = 0;
		for(register LL i = 1ll << 50, p = 50; i; i >>= 1, --p) {
			if((ans ^ mat[p]) > ans) ans ^= mat[p];
		}
		return ans;
	}
} LB;
int n; LL x;
int main() {
	scanf("%d", &n);
	for(register int i = 1; i <= n; ++i)
		scanf("%lld", &x), LB.ins(x);
	printf("%lld", LB.solve());
	return 0;
}
```

Treap:
```
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, u, v;
namespace Treap {
	const int L = 0, R = 1;
	struct node {
		int ch[2], key, rv, sz;
	} t[maxn];
	int root;
	void push_up(int rt) {
		t[rt].sz = t[t[rt].ch[L]].sz + t[t[rt].ch[R]].sz + 1;
	}
	void push_down(int rt) {
		if(t[rt].rv) {
			int &tl = t[rt].ch[L];
			int &tr = t[rt].ch[R];
			swap(tl, tr);
			if(tl) t[tl].rv ^= 1;
			if(tr) t[tr].rv ^= 1;
			t[rt].rv = 0;
		}
	}
	int merge(int u, int v) {
		if(!u || !v) return u + v;
		push_down(u), push_down(v);
		if(t[u].key > t[v].key) {
			t[u].ch[R] = merge(t[u].ch[R], v);
			return push_up(u), u;
		} else {
			t[v].ch[L] = merge(u, t[v].ch[L]);
			return push_up(v), v;
		}
	}
	void split(int &u, int &v, int k) {
		push_down(u);
		if(t[u].sz == k) return v = 0, void();
		if(k <= t[t[u].ch[L]].sz) {
			split(t[u].ch[L], v, k);
			swap(t[u].ch[L], v);
			swap(u, v);
			push_up(v);
		} else {
			split(t[u].ch[R], v, k - 1 - t[t[u].ch[L]].sz);
			push_up(u);
		}
	}
	void init(int n) {
		root = 1, t[1].sz = 1, t[1].key = rand();
		for(register int i = 2; i <= n + 2; ++i)
			t[i].sz = 1, t[i].key = rand(), root = merge(root, i);
	}
	void reverse(int l, int r) {
		int M, R;
		split(root, R, r + 1);
		split(root, M, l);
		t[M].rv ^= 1;
		root = merge(root, M);
		root = merge(root, R);
	}
	void prt(int u) {
		push_down(u);
		if(t[u].ch[L]) prt(t[u].ch[L]);
		if(u > 1 && u < n + 2)
			printf("%d ", u - 1);
		if(t[u].ch[R]) prt(t[u].ch[R]);
	}
}
int main() {
	srand(20020327);
	scanf("%d%d", &n, &m);
	Treap::init(n);
	for(register int i = 1; i <= m; ++i) {
		scanf("%d%d", &u, &v);
		Treap::reverse(u, v);
	}
	Treap::prt(Treap::root);
	return 0;
}
```

半平面交:
```
#include<cstdio>
#include<algorithm>
#include<cmath>
#define eps 1e-20
using namespace std;
const int maxn = 1e6 + 5;
namespace G2D {
	typedef double T;
	struct Point {T x, y;
		void prt() {printf ("%.2lf %.2lf\n", x, y);}};
	struct SEG {Point s, t;};
	int sgn(double x) {return (x > -eps) - (x < eps);}
	Point operator +(const Point &A, const Point &B) 
		{return (Point) {A.x + B.x, A.y + B.y};}
	Point operator -(const Point &A, const Point &B) 
		{return (Point) {A.x - B.x, A.y - B.y};}
	T operator *(const Point &A, const Point &B) 
		{return A.x * B.y - B.x * A.y;}
	int AOnLeft(const Point &A, const Point &B) 
		{return sgn(A * B);}
	int AOnLeft(const SEG &A, const Point &B) 
		{return sgn((A.t - A.s) * (B - A.s));}
	inline T sqr(T x) {return x * x;}
	T Dis(const Point &A, const Point &B) 
		{return sqrt(sqr(A.x - B.x) + sqr(A.y - B.y));}
	Point operator *(const T &x, const Point &p) 
		{return (Point) {p.x * x, p.y * x};}
	Point ItSec(const SEG &A, const SEG &B) {
		double a = (B.s - A.s) * (A.t - A.s); 
		double b = (A.t - A.s) * (B.t - A.s);
		return B.s + (a / (a + b)) * (B.t - B.s);
	}
	int q[maxn], f, b;
	double atanP(const Point &A) {return atan2(A.x, A.y);}
	bool cmp(const SEG &A, const SEG &B) {
		return atanP(A.t - A.s) < atanP(B.t - B.s);
	} 
	void HPI(SEG *A, int n, Point *ans, int &l) {
		sort(A + 1, A + 1 + n, cmp), f = 1;
		q[++b] = 1;
		for(register int i = 2; i <= n; ++i) {
			if(sgn(atanP(A[q[b]].t - A[q[b]].s) - atanP(A[i].t - A[i].s)) == 0) {
				if(AOnLeft(A[i], A[q[b]].t) < 0) q[b] = i; 
				continue;
			}
			//ItSec(A[q[b - 1]], A[q[b]]).prt();
			while(f < b && AOnLeft(A[i], ItSec(A[q[b - 1]], A[q[b]])) <= 0) --b;
			while(f < b && AOnLeft(A[i], ItSec(A[q[f]], A[q[f + 1]])) <= 0) ++f;
			q[++b] = i;
		}
		while(f < b && AOnLeft(A[f], ItSec(A[q[b - 1]], A[q[b]])) <= 0) --b;
		while(f < b && AOnLeft(A[b], ItSec(A[q[f]], A[q[f + 1]])) <= 0) ++f;
		for(register int i = f + 1; i <= b; ++i) {
			ans[++l] = ItSec(A[q[i]], A[q[i - 1]]);
		}
		ans[++l] = ItSec(A[q[b]], A[q[f]]);
		ans[++l] = ItSec(A[q[f]], A[q[f + 1]]);
	}
	inline T GetArea(Point * c, int cnt) {
    	T ans = 0;
    	for(register int i = 1; i < cnt; ++i) {
    		ans += (c[i] - c[0]) * (c[i + 1] - c[0]);
    		//c[i].prt();
    	}
    	return abs(ans);
    }
}

using namespace G2D;
SEG lset[maxn];
Point last, now, convex[maxn], bg;
int n, ec, size, cnt;

int main() {
    scanf("%d", &n);
    for(register int i = 1; i <= n; ++i) {
        scanf("%d", &ec);
        scanf("%lf %lf", &last.x, &last.y), bg = last;
        for(register int i = 2; i <= ec; ++i) {
            scanf("%lf %lf", &now.x, &now.y);
            lset[++size] = (SEG){last, now};
            last = now;
        }
        lset[++size] = (SEG){now, bg};
    }
    HPI(lset, size, convex, cnt);
    if(cnt < 3) return printf("0.000"), 0;
    printf("%.3lf\n", GetArea(convex, cnt) / 2.0);
    return 0;
}
```

Manacher:
```
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn = 2.2e7 + 5;
char s[maxn], c;
int n, RL[maxn], pos, r, ans;
int main() {
    s[n++] = '#';
    c = getchar();
    while(isalpha(c)) 
        s[n++] = c, s[n++] = '#', c = getchar();
    for(register int i = 1; i < n; ++i) {
        if(pos * 2 - i >= 0)
            RL[i] = min(RL[pos * 2 - i], r - i);
        for(register int &j = RL[i]; i - j >= 0 && i + j < n && s[i + j] == s[i - j]; ++j);
        --RL[i]; if(i + RL[i] > r) r = i + RL[i], pos = i;
        ans = max(ans, RL[i]);
    }
    printf("%d", ans);
    return 0;
}
```

秃包:
```
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#define eps 1e-16
using namespace std;
const int maxn = 1e6 + 5;
namespace G2D {
	typedef double T;
	struct Point {T x, y;};
	int sgn(double x) {return (x > -eps) - (x < eps);}
	Point operator +(const Point &A, const Point &B) 
		{return (Point) {A.x + B.x, A.y + B.y};}
	Point operator -(const Point &A, const Point &B) 
		{return (Point) {A.x - B.x, A.y - B.y};}
	T operator *(const Point &A, const Point &B) 
		{return A.x * B.y - B.x * A.y;}
	int AOnLeft(const Point &A, const Point &B) 
		{return sgn(A * B);}
	inline T sqr(T x) {return x * x;}
	T Dis(const Point &A, const Point &B) 
		{return sqrt(sqr(A.x - B.x) + sqr(A.y - B.y));}
	bool cmp(const Point &A, const Point &B) 
		{return A.x < B.x;}
	void convex(Point *v, int &n, Point *ans, int &l) {
		sort(v + 1, v + n + 1, cmp);
		ans[++l] = v[1];
		for(register int i = 2; i <= n; ++i) {
			while(l > 1 && AOnLeft(v[i] - ans[l], ans[l] - ans[l - 1]) > 0) --l;
			ans[++l] = v[i];
		}
		for(register int i = n - 1; i >= 1; --i) {
			while(AOnLeft(v[i] - ans[l], ans[l] - ans[l - 1]) > 0) --l;
			ans[++l] = v[i];
		}
	}
}
double ans;
G2D::Point pt[maxn], con[maxn];
int n, l;

int main() {
	scanf("%d", &n);
	for(register int i = 1; i <= n; ++i) {
		scanf("%lf%lf", &pt[i].x, &pt[i].y);
	}
	G2D::convex(pt, n, con, l);
	for(register int i = 1; i < l; ++i) 
		ans += G2D::Dis(con[i], con[i + 1]);
	printf("%.2lf", ans);
	return 0;
}
```

2-SAT:

```
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
const int maxn = 2e6 + 5;

struct edge {
    int v, next;
} e[maxn << 1];
int head[maxn], cnt;
void adde(const int &u, const int &v) {
    e[++cnt] = (edge) {v, head[u]};
    head[u] = cnt;
}

stack<int > stk;
int dfn[maxn], vis[maxn], blk[maxn], bcnt, low[maxn], dcnt;
void tarjan(int u) {
    stk.push(u);
    dfn[u] = low[u] = ++dcnt;
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(vis[v]) continue;
        if(dfn[v]) low[u] = min(low[u], low[v]);
        else {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
    }
    if(dfn[u] == low[u]) {
        int now;
        ++bcnt;
        do {
            now = stk.top(), stk.pop();
            blk[now] = bcnt;
        } while(now != u);
    }
    vis[u] = 1;
}

int n, m, a, b, c, d, x[maxn][2], xcnt;

int main() {
    scanf("%d%d", &n, &m);
    for(register int i = 1; i <= n; ++i)
        x[i][0] = ++xcnt, x[i][1] = ++xcnt;
    for(register int i = 1; i <= m; ++i) {
        scanf("%d%d%d%d", &a, &b, &c, &d);
        adde(x[a][b], x[c][d ^ 1]);
        adde(x[c][d], x[a][b ^ 1]);
    }
    for(register int i = 1; i <= xcnt; ++i) {
        if(!vis[i]) tarjan(i);
    }
    for(register int i = 1; i <= n; ++i)
        if(blk[x[i][0]] == blk[x[i][1]]) {
            printf("IMPOSSIBLE");
            return 0;
        }
    printf("POSSIBLE\n");
    for(register int i = 1; i <= n; ++i)
    	printf("%d ", (dfn[x[i][0]] < dfn[x[i][1]]));
    return 0;
}
```

AC自动机：
```
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 1e5 + 5;

vector<int > oprs[maxn], opri[maxn];
int snd[maxn], scnt;
namespace BIT {
	#define lowbit(x) ((x) & (-(x)))
	int t[maxn], N;
	void add(int x, int w) {
		for(; x <= N; x += lowbit(x)) t[x] += w;
	}
	int query(int x) {
		int ans = 0;
		for(; x; x -= lowbit(x)) ans += t[x];
		return ans;
	}
}

namespace AC {
	struct edge {
		int v, next;
	} e[maxn];
	int head[maxn], ecnt;
	void adde(const int &u, const int &v) {
		e[++ecnt] = (edge) {v, head[u]};
		head[u] = ecnt;
	}
	int trie[maxn][26], cnt, fa[maxn], now;
	int dfn[maxn], d[maxn], dfe[maxn], dcnt;
	void init() {now = ++cnt;}
	void ins(char c) {
		int id = c - 'a';
		if(!trie[now][id]) 
			trie[now][id] = ++cnt, fa[cnt] = now;
		now = trie[now][id];
	}
	void B() {now = fa[now];}
	void P() {snd[++scnt] = now;}
	void dfs(int u) {
		dfn[u] = ++dcnt;
		for(register int i = head[u]; i; i = e[i].next)
			dfs(e[i].v);
		dfe[u] = dcnt;
	}
	void build() {
		queue<int > q;
		q.push(1);
		memset(fa, 0, sizeof(fa));
		while(!q.empty()) {
			int u = q.front();
			q.pop();
			for(register int i = 0; i < 26; ++i) {
				if(!trie[u][i]) continue;
				int v = trie[u][i], p = fa[u];
				while(p && !trie[p][i]) p = fa[p];
				if(p) fa[v] = trie[p][i];
				else fa[v] = 1;
				adde(fa[v], v);
				q.push(v);
			}
		}
		dfs(1);
	}
	int Q(int x, int y) {
		return (dfn[x] <= dfn[y] && dfe[x] >= dfn[y]) ? d[y] - d[x] : 0;
	}
}
char s[maxn];
int n, l, u, v, ans[maxn];
void solve(int u) {
	using namespace AC;
	BIT::add(dfn[u], 1);
	for(register int i = oprs[u].size() - 1; i >= 0; --i) {
		ans[opri[u][i]] = BIT::query(dfe[oprs[u][i]]) - 
						BIT::query(dfn[oprs[u][i]] - 1);
	}
	for(register int i = 0; i < 26; ++i)
		if(trie[u][i]) solve(trie[u][i]);
	BIT::add(dfn[u], -1);
}
int main() {
	AC::init();
	scanf("%s", s);
	l = strlen(s);
	for(register int i = 0; i < l; ++i) {
		if(s[i] == 'B') AC::B();
		else if(s[i] == 'P') AC::P();
		else AC::ins(s[i]);
	}
	AC::build(), BIT::N = AC::cnt;
	scanf("%d", &n);
	for(register int i = 1; i <= n; ++i) {
		scanf("%d%d", &u, &v);
		oprs[snd[v]].push_back(snd[u]);
		opri[snd[v]].push_back(i);
	}
	solve(1);
	for(register int i = 1; i <= n; ++i)
		printf("%d\n", ans[i]);
	return 0;
}
```

新版点双树(仙人掌链上加):
```
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<stack>
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 998244353;
struct edge {
	int v, next;
} e[maxn << 1];
int head[maxn], cnt, n, m, q, u, v, w, op;
void adde(const int &u, const int &v) {
	e[++cnt] = (edge) {v, head[u]};
	head[u] = cnt;
}

void Add(int &x, const int &a) {
	x += a; if(x >= mod) x -= mod;
	if(x < 0) x += mod;
}

namespace BIT {
	int t[maxn], N;
	#define lowbit(x) ((x)&(-(x)))
	void add(int x, int dt) {
		for(; x <= N; x += lowbit(x))
			Add(t[x], dt);
	}
	void add(int l, int r, int dt) {
		add(l, dt), add(r + 1, -dt);
	}
	int Q(int x) {
		int ans = 0;
		while(x) {Add(ans, t[x]); x -= lowbit(x);}
		return ans;
	}
}

namespace BCT {
	struct edge {
		int v, next;
	} e[maxn << 1];
	int head[maxn], cnt, dcnt, iadd[maxn];
	void adde(const int &u, const int &v) {
		//printf("%d ------> %d\n", u, v);
		e[++cnt] = (edge) {v, head[u]};
		head[u] = cnt;
	}
	int depth[maxn], dfn[maxn], son[maxn], top[maxn], siz[maxn], fa[maxn];
	void dfs(int u, int p) {
		siz[u] = 1, fa[u] = p;
		for(register int i = head[u]; i; i = e[i].next) {
			int v = e[i].v;
			if(v == p) continue;
			dfs(v, u);
			siz[u] += siz[v];
			if(!son[u] || siz[son[u]] < siz[v])
				son[u] = v;
		}
	}
	void dfs2(int u, int tp) {
		top[u] = tp;
		if(u > n) dfn[u] = ++dcnt;
		else dfn[u] = dfn[fa[u]];
		depth[u] = depth[fa[u]] + 1;
		if(son[u]) dfs2(son[u], tp);
		for(register int i = head[u]; i; i = e[i].next) {
			int v = e[i].v;
			if(v == son[u] || v == fa[u]) continue;
			dfs2(v, v);
		}
	}
	void ADD(int u, int v, int w) {
		while(top[u] != top[v]) {
			if(depth[top[u]] < depth[top[v]])
				swap(u, v);
			if(top[u] > n) BIT::add(dfn[top[u]], dfn[u], w);
			else if(top[u] != u) BIT::add(dfn[son[top[u]]], dfn[u], w);
			u = fa[top[u]];
		}
		if(depth[u] < depth[v]) swap(u, v);
		if(v > n) {
			BIT::add(dfn[v], dfn[u], w);
			Add(iadd[fa[v]], w);
		} else {
			if(u != v) BIT::add(dfn[son[v]], dfn[u], w);
			Add(iadd[v], w);
		}
	}
	int Q(int x) {
		return (BIT::Q(dfn[x]) + iadd[x]) % mod;
	}
}

stack<int > stk;
int dfn[maxn], low[maxn], dcnt, bcnt;
int tarjan(int u) {
	stk.push(u), dfn[u] = low[u] = ++dcnt;
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if(dfn[v]) low[u] = min(low[u], dfn[v]);
		else {
			tarjan(v), low[u] = min(low[u], low[v]);
			if(low[v] >= dfn[u]) {
				BCT::adde(++bcnt, u), BCT::adde(u, bcnt);
				int now = 0;
				do {
					now = stk.top(), stk.pop();
					BCT::adde(bcnt, now);
					BCT::adde(now, bcnt);
				} while(now != v);
			}
		}
	}
}

int main() {
	freopen("cac.in", "r", stdin);
	freopen("cac.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &q);
	bcnt = n, BIT::N = n << 1;
	for(register int i = 1; i <= m; ++i)
		scanf("%d%d", &u, &v), adde(u, v), adde(v, u);
	tarjan(1);
	BCT::dfs(1, 0), BCT::dfs2(1, 1);
	for(register int i = 1; i <= q; ++i) {
		scanf("%d", &op);
		if(op == 0) {
			scanf("%d%d%d", &u, &v, &w);
			BCT::ADD(u, v, w);
		} else {
			scanf("%d", &u);
			printf("%d\n", BCT::Q(u));
		}
	}
	return 0;
}
```

LCT:
```
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, u, v;
char s[20];
namespace LCT {
	#define isrt(x) (t[t[x].fa].ch[L] != x && t[t[x].fa].ch[R] != x)
	const int L = 0, R = 1;
	struct node {int ch[2], fa, rv;} t[maxn];
	void push_down(int rt) {
		if(t[rt].rv) {
			swap(t[rt].ch[L], t[rt].ch[R]);
			t[t[rt].ch[R]].rv ^= 1;
			t[t[rt].ch[L]].rv ^= 1;
			t[rt].rv = 0;
		}
	}
	void rotate(int rt) {
		int p = t[rt].fa, a = t[p].fa;
		int r = t[p].ch[R] == rt, l = r ^ 1;
		if(!isrt(p)) t[a].ch[t[a].ch[R] == p] = rt;
		t[rt].fa = a, t[p].fa = rt, t[t[rt].ch[l]].fa = p;
		t[p].ch[r] = t[rt].ch[l], t[rt].ch[l] = p;
	}
	void splay(int x) {
		while(!isrt(x)) {
			int p = t[x].fa, a = t[p].fa;
			push_down(a), push_down(p), push_down(x);
			if(!isrt(p)) 
				if((t[a].ch[R] == p) ^ (t[p].ch[R] == x)) rotate(x);
				else rotate(p);
			rotate(x);
		}
	}
	void change(int u, int v) {
		splay(u), push_down(u);
		t[u].ch[R] = v;
	}
	int access(int u) {
		change(u, 0);
		for(; t[u].fa; u = t[u].fa) 
			change(t[u].fa, u);
		push_down(u);
		while(t[u].ch[L]) 
			u = t[u].ch[L], push_down(u);
		return splay(u), u;
	}
	void link(int u, int v) {
		t[u = access(u)].rv ^= 1, t[u].fa = v;
	}
	void cut(int u, int v) {
		change(u, 0), change(v, 0);
		if(t[u].fa == v) t[u].fa = 0;
		else t[v].fa = 0;
	}
	int Q(int u, int v) {
		return access(u) == access(v);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for(register int i = 1; i <= m; ++i) {
		scanf("%s%d%d", s, &u, &v);
		if(s[0] == 'D') LCT::cut(u, v);
		else if(s[0] == 'C') LCT::link(u, v);
		else if(s[0] == 'Q') printf("%s\n", LCT::Q(u, v) ? "Yes" : "No");
	}
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链