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();
  }
}