sxy 的模板库
头
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int read() {
int x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == ‘-‘) f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
FHQ Treap
按权值分裂
void Split(Node* o, int k, Node* &x, Node* &y) {
if (o == NULL) {
x = y = NULL; return;
}
if (k >= o->v) {
x = o; Split(o->rs, k, o->rs, y);
}
else {
y = o; Split(o->ls, k, x, o->ls);
}
o->Maintain();
}
按大小分裂
void Split(Node* o, int k, Node* &x, Node* &y) {
if (o == NULL) {
x = y = NULL; return;
}
o->Pushdown();
int ls = (o->ls == NULL ? 0 : o->ls->s) + 1;
if (k >= ls) {
x = o; Split(o->rs, k - ls, o->rs, y);
}
else {
y = o; Split(o->ls, k, x, o->ls);
}
o->Maintain();
}
合并
Node *Merge(Node* x, Node* y) {
if (x == NULL || y == NULL) {
return x == NULL ? y : x;
}
if (x->r < y->r) {
x->rs = Merge(x->rs, y);
x->Maintain();
return x;
}
else {
y->ls = Merge(x, y->ls);
y->Maintain();
return y;
}
}
Dinic
struct Dinic {
int n, s, t, d[N], now[N];
int tot = 1, to[M], cap[M], nxt[M], head[N];
ll maxflow;
queue <int> q;
void Add(int u, int v, int w) {
to[++tot] = v, cap[tot] = w, nxt[tot] = head[u], head[u] = tot;
}
bool BFS() {
memset(d, 0, sizeof(int) * (n + 1));
while (q.size()) q.pop();
q.push(s); d[s] = 1; now[s] = head[s];
while (q.size()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = nxt[i]) {
int y = to[i];
if (!d[y] && cap[i]) {
q.push(y);
d[y] = d[x] + 1;
now[y] = head[y];
if (y == t) return true;
}
}
}
return false;
}
int DFS(int x, int flow) {
if (x == t || flow == 0) {
maxflow += flow;
return flow;
}
int rest = flow, k;
for (int i = now[x]; i && rest; i = nxt[i]) {
now[x] = i;
int y = to[i];
if (d[y] == d[x] + 1 && cap[i]) {
k = DFS(y, min(rest, cap[i]));
if (!k) d[y] = 0;
cap[i] -= k;
cap[i ^ 1] += k;
rest -= k;
}
}
return flow - rest;
}
void Run() {
ll flow = 0;
while (BFS())
while (DFS(s, inf));
}
};
ISAP
struct ISAP {
int n, s, t, d[N], now[N], gap[N];
int tot = 1, to[M], cap[M], nxt[M], head[N];
ll maxflow;
queue <int> q;
void Add(int u, int v, int w) {
to[++tot] = v, cap[tot] = w, nxt[tot] = head[u], head[u] = tot;
}
void BFS() {
q.push(t); d[t] = 1; gap[1]++;
while (q.size()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = nxt[i]) {
int y = to[i];
if (!d[y]) {
q.push(y);
d[y] = d[x] + 1;
gap[d[y]]++;
}
}
}
}
int DFS(int x, int flow) {
if (x == t || flow == 0) {
maxflow += flow;
return flow;
}
int rest = flow, k;
for (int i = now[x]; i; i = nxt[i]) {
now[x] = i;
int y = to[i];
if (d[y] == d[x] - 1 && cap[i]) {
k = DFS(y, min(rest, cap[i]));
cap[i] -= k;
cap[i ^ 1] += k;
rest -= k;
}
if (!rest) return flow;
}
gap[d[x]]--;
if (!gap[d[x]]) d[s] = n + 1;
d[x]++;
gap[d[x]]++;
return flow - rest;
}
void Run() {
BFS();
while (d[s] <= n) {
memcpy(now, head, sizeof(int) * (n + 1));
DFS(s, inf);
}
}
};
MCMF
\(SPFA + EK\)
struct MCMF {
int n, s, t, d[N], flow[N], pre[N], lst[N];
int tot = 1, to[M], cap[M], cost[M], nxt[M], head[N];
ll maxflow, mincost;
bool vis[N];
queue <int> q;
void Add(int u, int v, int w, int c) {
to[++tot] = v, cap[tot] = w, cost[tot] = c, nxt[tot] = head[u], head[u] = tot;
}
bool SPFA() {
memset(d, 0x3f, sizeof(int) * (n + 1));
memset(flow, 0x3f, sizeof(int) * (n + 1));
memset(vis, 0, sizeof(int) * (n + 1));
while (q.size()) q.pop();
q.push(s); d[s] = 0; pre[t] = -1;
while (q.size()) {
int x = q.front(); q.pop();
vis[x] = 0;
for (int i = head[x]; i; i = nxt[i]) {
int y = to[i], z = cost[i];
if (d[y] > d[x] + z && cap[i]) {
d[y] = d[x] + z;
pre[y] = x;
lst[y] = i;
flow[y] = min(flow[x], cap[i]);
if (!vis[y]) {
vis[y];
q.push(y);
}
}
}
}
return pre[t] != -1;
}
void EK() {
while (SPFA()) {
int now = t;
maxflow += flow[t];
mincost += 1ll * flow[t] * d[t];
while (now != s) {
cap[lst[now]] -= flow[t];
cap[lst[now] ^ 1] += flow[t];
now = pre[now];
}
}
}
};
\(SPFA + Dijkstra\)
struct MCMF {
int n, s, t, d[N], now[N];
int tot = 1, to[M], cap[M], cost[M], nxt[M], head[N];
ll maxflow, mincost;
bool vis[N];
queue <int> q;
void Add(int u, int v, int w, int c) {
to[++tot] = v, cap[tot] = w, cost[tot] = c, nxt[tot] = head[u], head[u] = tot;
}
bool SPFA() {
memset(d, 0x3f, sizeof(int) * (n + 1));
memset(vis, 0, sizeof(int) * (n + 1));
while (q.size()) q.pop();
q.push(s); d[s] = 0; now[s] = head[s]; d[t] = inf;
while (q.size()) {
int x = q.front(); q.pop();
vis[x] = 0;
for (int i = head[x]; i; i = nxt[i]) {
int y = to[i], z = cost[i];
if (d[y] > d[x] + z && cap[i]) {
d[y] = d[x] + z;
now[y] = head[y];
if (!vis[y]) {
vis[y];
q.push(y);
}
}
}
}
return d[t] != inf;
}
int Dinic(int x, int flow) {
if (x == t || flow == 0) {
maxflow += flow;
return flow;
}
vis[x] = 1;
int rest = flow, k;
for (int i = now[x]; i && rest; i = nxt[i]) {
now[x] = i;
int y = to[i], z = cost[i];
if (!vis[y] && cap[i] && d[y] == d[x] + z) {
k = Dinic(y, min(rest, cap[i]));
if (!k) d[y] = 0;
cap[i] -= k;
cap[i ^ 1] += k;
rest -= k;
mincost += k * cost[i];
}
}
vis[x] = 0;
return flow - rest;
}
void Run() {
while (SPFA())
while (Dinic(s, inf));
}
};
Dijkstra
struct Dij {
int d[N], vis[N];
int tot, to[M], dis[M], nxt[M], head[N];
priority_queue <pair <int, int> > q;
void Add(int u, int v, int w) {
to[++tot] = v, dis[tot] = w, nxt[tot] = head[u], head[u] = tot;
}
void Run(int s) {
memset(d, 0x3f, sizeof(d));
d[s] = 0;
q.push(make_pair(0, s));
while (q.size()) {
int x = q.top().second; q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int y = to[i], z = dis[i];
if (d[y] > d[x] + z) {
d[y] = d[x] + z;
q.push(make_pair(-d[y], y));
}
}
}
}
};
SPFA
struct SPFA {
int d[N], vis[N];
int tot, to[M], dis[M], nxt[M], head[N];
queue <int> q;
void Add(int u, int v, int w) {
to[++tot] = v, dis[tot] = w, nxt[tot] = head[u], head[u] = tot;
}
void Run(int s) {
memset(d, 0x3f, sizeof(d));
d[s] = 0;
q.push(s);
while (q.size()) {
int x = q.front(); q.pop();
vis[x] = 0;
for (int i = head[x]; i; i = nxt[i]) {
int y = to[i], z = dis[i];
if (d[y] > d[x] + z) {
d[y] = d[x] + z;
if (!vis[y]) {
vis[y] = 1;
q.push(y);
}
}
}
}
}
};
倍增 LCA
struct LCA {
int dep[N], f[N][25];
int tot, to[M], nxt[M], head[N];
void Add(int u, int v) {
to[++tot] = v, nxt[tot] = head[u], head[u] = tot;
}
void DFS(int x, int fa) {
dep[x] = dep[fa] + 1;
for (int i = 1; i <= 24; i++) {
f[x][i] = f[f[x][i - 1]][i - 1];
}
for (int i = head[x]; i; i = nxt[i]) {
int y = to[i];
if (y == fa) continue;
f[y][0] = x;
DFS(y, x);
}
}
int Query(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = 24; i >= 0; i--) {
if (dep[f[x][i]] >= dep[y]) x = f[x][i];
if (x == y) return x;
}
for (int i = 24; i >= 0; i--) {
if (f[x][i] != f[y][i]) {
x = f[x][i]; y = f[y][i];
}
}
return f[x][0];
}
};
ExKMP
struct ExKMP {
int nxt[N], extend[N];
char s[N], t[N];
void Get_Nxt() {
int len = strlen(t);
nxt[0] = len;
for (int a = 1; a < len; a++) {
int p = a;
while (t[p] == t[p - a] && p < len) p++;
nxt[a] = p - a;
for (int i = a + 1; i < p; i++) {
if (i + nxt[i - a] >= p) {
while (t[p] == t[p - i] && p < len) p++;
nxt[i] = p - i;
a = i;
}
else nxt[i] = nxt[i - a];
}
}
}
void Get_Extend() {
int lens = strlen(s), lent = strlen(t);
for (int a = 0; a < lens; a++) {
int p = a;
while (s[p] == t[p - a] && p < lens && p - a < lent) p++;
extend[a] = p - a;
for (int i = a + 1; i < p; i++) {
if (i + nxt[i - a] >= p) {
while (s[p] == t[p - i] && p < lens && p - i < lent) p++;
extend[i] = p - i;
a = i;
}
else extend[i] = nxt[i - a];
}
}
}
};
Trie
struct Trie {
int ch[M][26], ed[M], v[M], cnt;
void Insert(char *s) {
int len = strlen(s), x = 0;
ed[x]++;
for (int i = 0; i < len; i++) {
int y = s[i] - ‘a‘;
if (!ch[x][y]) ch[x][y] = ++cnt;
x = ch[x][y];
ed[x]++;
}
v[x]++;
}
};
AC 自动机
struct AC{
int ch[M][26], fail[M], ed[M], cnt;
queue <int> q;
void Insert(char *s){
int len = strlen(s), now = 0;
for (int i = 0; i < len; i++){
int x = s[i] - ‘a‘;
if (!ch[now][x]) ch[now][x] = ++cnt;
now = ch[now][x];
}
ed[now]++;
}
void Build(){
for (int i = 0; i < 26; i++){
if (ch[0][i]){
fail[ch[0][i]] = 0;
q.push(ch[0][i]);
}
}
while (q.size()){
int x = q.front(); q.pop();
for (int i = 0; i < 26; i++){
if (ch[x][i]){
fail[ch[x][i]] = ch[fail[x]][i];
q.push(ch[x][i]);
}
else ch[x][i] = ch[fail[x]][i];
}
}
}
int Query(char *s){
int len = strlen(s), now = 0, ans = 0;
for (int i = 0; i < len; i++){
now = ch[now][s[i] - ‘a‘];
for (int j = now; j && ~ed[j]; j = fail[j]){
ans += ed[j]; ed[j] = -1;
}
}
return ans;
}
};
Manacher
struct Manacher {
int d[N];
void Solve(char *s, int n) {
for (int i = 1, r = 0, mid = 0; i <= n; i++){
if (i <= r) d[i] = min(d[(mid << 1) - i], r - i + 1);
while (s[i - d[i]] == s[i + d[i]]) d[i]++;
if (d[i] + i > r) r = d[i] + i - 1, mid = i;
}
}
};
void init(){
char ch = getchar();
s[0] = ‘~‘, s[1] = ‘#‘;
while (ch >= ‘a‘ && ch <= ‘z‘){
s[++n] = ch, s[++n] = ‘#‘;
ch = getchar();
}
}