Visits: 1701

模板汇总，不定期更新

基本模板

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