模板合集

轻重链剖分

// time : 20210103
// test on https://www.luogu.com.cn/problem/P3384

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define M 100001

inline void read(int &T) {
    int x = 0; bool f = 0; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = !f; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    T = f ? -x : x;
}

int n, m, r, p, a[M], dfn[M], pre[M], size[M];

namespace Seg {
    #define lson now << 1
    #define rson now << 1 | 1
    struct Node {
        int l, r, w, lazy;
    }tree[M << 2];
    void build(int l, int r, int now) {
        tree[now].l = l, tree[now].r = r;
        if (tree[now].l == tree[now].r) {
            tree[now].w = a[pre[l]]; return;
        }
        int mid = (tree[now].l + tree[now].r) >> 1;
        build(l, mid, lson), build(mid + 1, r, rson);
        tree[now].w = (tree[lson].w + tree[rson].w) % p;
    }
    void pushdown(int now) {
        if (tree[now].l == tree[now].r) return;
        tree[lson].lazy = (tree[lson].lazy + tree[now].lazy) % p;
        tree[rson].lazy = (tree[rson].lazy + tree[now].lazy) % p;
        tree[lson].w = (tree[lson].w + 1ll * (tree[lson].r - tree[lson].l + 1) * tree[now].lazy % p) % p;
        tree[rson].w = (tree[rson].w + 1ll * (tree[rson].r - tree[rson].l + 1) * tree[now].lazy % p) % p;
        tree[now].lazy = 0; return;
    }
    void update(int x, int y, int k, int now) {
        if (tree[now].l >= x && tree[now].r <= y) {
            tree[now].w = (tree[now].w + 1ll * (tree[now].r - tree[now].l + 1) * k % p) % p;
            tree[now].lazy = (tree[now].lazy + k) % p; return;
        }
        if (tree[now].lazy) pushdown(now);
        int mid = (tree[now].l + tree[now].r) >> 1;
        if (x <= mid) update(x, y, k, lson);
        if (y > mid) update(x, y, k, rson);
        tree[now].w = (tree[lson].w + tree[rson].w) % p;
    }
    int query(int x, int y, int now) {
        if (tree[now].l >= x && tree[now].r <= y) return tree[now].w;
        if (tree[now].lazy) pushdown(now);
        int mid = (tree[now].l + tree[now].r) >> 1, ans = 0;
        if (x <= mid) ans = (ans + query(x, y, lson)) % p;
        if (y > mid) ans = (ans + query(x, y, rson)) % p;
        return ans;
    }
}

namespace Cut {
    int pthn, dep[M], head[M];
    int cnt, fa[M], son[M], top[M];
    struct Edge {
        int nxt, to;
    }pth[M << 1];
    void add(int frm, int to) {
        pth[++pthn].to = to, pth[pthn].nxt = head[frm];
        head[frm] = pthn;
    }
    void dfs1(int u, int father) {
        fa[u] = father, dep[u] = dep[father] + 1, size[u] = 1;
        for (int i = head[u]; i; i = pth[i].nxt) {
            int v = pth[i].to;
            if (v != father) {
                dfs1(v, u), size[u] += size[v];
                if (size[v] > size[son[u]]) son[u] = v;
            }
        }
    }
    void dfs2(int u, int tp) {
        dfn[u] = ++cnt, pre[cnt] = u, top[u] = tp;
        if (son[u]) dfs2(son[u], tp);
        for (int i = head[u]; i; i = pth[i].nxt) {
            int v = pth[i].to;
            if (v != fa[u] && v != son[u]) dfs2(v, v);
        }
    }
    void change(int x, int y, int k) {
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
            Seg::update(dfn[top[x]], dfn[x], k, 1);
            x = fa[top[x]];
        }
        if (dfn[x] > dfn[y]) std::swap(x, y);
        Seg::update(dfn[x], dfn[y], k, 1); 
    }
    int ask(int x, int y) {
        int ans = 0;
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
            ans = (ans + Seg::query(dfn[top[x]], dfn[x], 1)) % p;
            x = fa[top[x]];
        }
        if (dfn[x] > dfn[y]) std::swap(x, y);
        ans = (ans + Seg::query(dfn[x], dfn[y], 1)) % p;
        return ans;
    }
}

int main() {
    read(n), read(m), read(r), read(p);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1, u, v; i < n; ++i) {
        read(u), read(v);
        Cut::add(u, v), Cut::add(v, u);
    }
    Cut::dfs1(r, 0), Cut::dfs2(r, r), Seg::build(1, n, 1);
    for (int i = 1, opt, x, y, k; i <= m; ++i) {
        read(opt), read(x);
        if (opt == 1) { read(y), read(k), Cut::change(x, y, k); }
        if (opt == 2) { read(y), printf("%d
", Cut::ask(x, y)); }
        if (opt == 3) { read(y), Seg::update(dfn[x], dfn[x] + size[x] - 1, y, 1); }
        if (opt == 4) { printf("%d
", Seg::query(dfn[x], dfn[x] + size[x] - 1, 1)); }
    }
    return 0;
}

线段树

// time : 20210103
// test on https://www.luogu.com.cn/problem/P3373

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define M 100001
#define lson now << 1
#define rson now << 1 | 1

inline void read(int &T) {
    int x = 0; bool f = 0; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = !f; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    T = f ? -x : x;
}

int n, m, p;
struct Node {
    int l, r, w, add, mul;
}tree[M << 2];

void build(int l, int r, int now) {
    tree[now].l = l, tree[now].r = r;
    tree[now].add = 0, tree[now].mul = 1;
    if (tree[now].l == tree[now].r) {
        read(tree[now].w); return;
    }
    int mid = (tree[now].l + tree[now].r) >> 1;
    build(l, mid, lson), build(mid + 1, r, rson);
    tree[now].w = (tree[lson].w + tree[rson].w) % p;
}

void pushdown(int now) {
    if (tree[now].l == tree[now].r) return;
    tree[lson].mul = 1ll * tree[lson].mul * tree[now].mul % p;
    tree[rson].mul = 1ll * tree[rson].mul * tree[now].mul % p;
    tree[lson].add = (1ll * tree[lson].add * tree[now].mul % p + tree[now].add) % p;
    tree[rson].add = (1ll * tree[rson].add * tree[now].mul % p + tree[now].add) % p;
    tree[lson].w = (1ll * tree[lson].w * tree[now].mul % p + 1ll * (tree[lson].r - tree[lson].l + 1) * tree[now].add % p) % p;
    tree[rson].w = (1ll * tree[rson].w * tree[now].mul % p + 1ll * (tree[rson].r - tree[rson].l + 1) * tree[now].add % p) % p;
    tree[now].mul = 1, tree[now].add = 0;
}

void update1(int x, int y, int k, int now) {
    if (tree[now].l >= x && tree[now].r <= y) {
        tree[now].w = 1ll * tree[now].w * k % p;
        tree[now].mul = 1ll * tree[now].mul * k % p;
        tree[now].add = 1ll * tree[now].add * k % p;
        return;
    }
    if (tree[now].mul != 1 || tree[now].add) pushdown(now);
    int mid = (tree[now].l + tree[now].r) >> 1;
    if (x <= mid) update1(x, y, k, lson);
    if (y > mid) update1(x, y, k, rson);
    tree[now].w = (tree[lson].w + tree[rson].w) % p;
}

void update2(int x, int y, int k, int now) {
    if (tree[now].l >= x && tree[now].r <= y) {
        tree[now].w = (tree[now].w + 1ll * (tree[now].r - tree[now].l + 1) * k % p) % p;
        tree[now].add = (tree[now].add + k) % p; return;
    }
    if (tree[now].mul != 1 || tree[now].add) pushdown(now);
    int mid = (tree[now].l + tree[now].r) >> 1;
    if (x <= mid) update2(x, y, k, lson);
    if (y > mid) update2(x, y, k, rson);
    tree[now].w = (tree[lson].w + tree[rson].w) % p;
}

int query(int x, int y, int now) {
    if (tree[now].l >= x && tree[now].r <= y) return tree[now].w;
    if (tree[now].mul != 1 || tree[now].add) pushdown(now);
    int mid = (tree[now].l + tree[now].r) >> 1, ans = 0;
    if (x <= mid) ans = (ans + query(x, y, lson)) % p;
    if (y > mid) ans = (ans + query(x, y, rson)) % p;
    return ans;
}

int main() {
    read(n), read(m), read(p);
    build(1, n, 1);
    for (int i = 1, opt, x, y, k; i <= m; ++i) {
        read(opt), read(x), read(y);
        if (opt == 1) { read(k), update1(x, y, k, 1); }
        if (opt == 2) { read(k), update2(x, y, k, 1); }
        if (opt == 3) printf("%d
", query(x, y, 1));
    }
    return 0;
}

树状数组

// time : 20210103
// test on https://www.luogu.com.cn/problem/P3374
// test on https://www.luogu.com.cn/problem/P3368

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define M 500001
#define lowbit(x) x & (-x)

inline void read(int &T) {
    int x = 0; bool f = 0; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = !f; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    T = f ? -x : x;
}

int n, m;
struct Bit {
    int c[M];
    void add(int x, int k) {
        while (x <= n) { c[x] += k, x += lowbit(x); }
    }
    int ask(int x, int ans = 0) {
        while (x > 0) { ans += c[x], x -= lowbit(x); }
        return ans;
    }
}b;

int main() {
    read(n), read(m);
    
    //bit1
    for (int i = 1, x; i <= n; ++i) {
        read(x), b.add(i, x);
    }
    for (int i = 1, opt, x, y; i <= m; ++i) {
        read(opt), read(x), read(y);
        if (opt == 1) b.add(x, y);
        else printf("%d
", b.ask(y) - b.ask(x - 1));
    }
    
    //bit2
    for (int i = 1, last = 0, x; i <= n; ++i, last = x) {
        read(x), b.add(i, x - last);
    }
    for (int i = 1, opt, x, y, k; i <= m; ++i) {
        read(opt), read(x);
        if (opt == 1) {
            read(y), read(k);
            b.add(x, k), b.add(y + 1, -k);
        }
        else printf("%d
", b.ask(x));
    }
    
    return 0;
}

缩点（tarjan）

// time : 20210103
// test on https://www.luogu.com.cn/problem/P3387

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#define M 100001

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

inline void read(int &T) {
    int x = 0; bool f = 0; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = !f; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    T = f ? -x : x;
}

bool vis[M];
std::queue<int> q;
int n, m, ans, a[M], x[M], y[M], f[M], pthn, head[M];
int c, t, sc, b[M], s[M], dfn[M], low[M], num[M], ideg[M];
struct Edge {
    int nxt, to;
}pth[M];

void add(int frm, int to) {
    pth[++pthn].to = to, pth[pthn].nxt = head[frm];
    head[frm] = pthn;
}

void format() {
    memset(head, 0, sizeof head);
    for (int i = 1; i <= pthn; ++i) {
        pth[i].nxt = pth[i].to = 0;
    }
    pthn = 0;
}

void tarjan(int u) {
    low[u] = dfn[u] = ++c;
    vis[u] = true, s[++sc] = u;
    for (int i = head[u]; i; i = pth[i].nxt) {
        int v = pth[i].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        int now = s[sc--]; num[now] = ++t;
        b[t] += a[now], vis[now] = false;
        while (now != u) {
            now = s[sc--], num[now] = t;
            b[t] += a[now], vis[now] = false;
        }
    }
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= m; ++i) {
        read(x[i]), read(y[i]);
        add(x[i], y[i]);
    }
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) tarjan(i);
    }
    format();
    for (int i = 1; i <= m; ++i) {
        if (num[x[i]] != num[y[i]]) {
            add(num[x[i]], num[y[i]]);
            ++ideg[num[y[i]]];
        }
    }
    for (int i = 1; i <= t; ++i) {
        if (!ideg[i]) q.push(i), f[i] = b[i];
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        ans = max(ans, f[u]);
        for (int i = head[u]; i; i = pth[i].nxt) {
            int v = pth[i].to; --ideg[v];
            f[v] = max(f[v], f[u] + b[v]);
            if (!ideg[v]) q.push(v);
        }
    }
    std::cout << ans << '
';
    return 0;
}

回滚莫队（不删除莫队）

// time : 20200103
// test on https://www.luogu.com.cn/problem/P5906

#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define M 200001

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

inline void read(int &T) {
    int x = 0; bool f = 0; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = !f; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    T = f ? -x : x; 
}

int n, m, a[M], fir[M], las[M];
int sqrn, num[M], ans[M], fir_[M];
struct query {
    int x, y, id;
    friend bool operator < (query q1, query q2) {
        if (num[q1.x] == num[q2.x]) return q1.y < q2.y;
        else return num[q1.x] < num[q2.x];
    }
}q[M];
struct lsh {
    int w, id;
    friend bool operator < (lsh l1, lsh l2) {
        return l1.w < l2.w;
    }
}b[M];

int main() {
    read(n), sqrn = sqrt(n);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
        b[i].id = i, b[i].w = a[i];
        num[i] = (i - 1) / sqrn + 1;
    }
    std::sort(b + 1, b + n + 1);
    for (int i = 1, now = 0; i <= n; ++i) {
        if (b[i].w != b[i - 1].w) ++now;
        a[b[i].id] = now;
    }
    read(m);
    for (int i = 1; i <= m; ++i) {
        read(q[i].x), read(q[i].y);
        q[i].id = i;
    }
    std::sort(q + 1, q + m + 1);
    int l = 1, r = 0, now = 0, lasb = 0;
    for (int i = 1; i <= m; ++i) {
        if (num[q[i].x] == num[q[i].y]) {
            int temp = 0;
            for (int j = q[i].x; j <= q[i].y; ++j) {
                if (!fir_[a[j]]) fir_[a[j]] = j;
                else temp = max(temp, j - fir_[a[j]]);
            }
            for (int j = q[i].x; j <= q[i].y; ++j) fir_[a[j]] = 0;
            ans[q[i].id] = temp; continue;
        }
        if (lasb != num[q[i].x]) {
            int stop = min(num[q[i].x] * sqrn, n );
            memset(fir, 0, sizeof fir), memset(las, 0, sizeof las);
            l = stop + 1, r = stop, now = 0, lasb = num[q[i].x];
        }
        while (r < q[i].y) {
            ++r;
            if (!fir[a[r]]) fir[a[r]] = las[a[r]] = r;
            else {
                las[a[r]] = r;
                now = max(now, r - fir[a[r]]);
            }
        }
        int l_ = l, temp = now;
        while (l_ > q[i].x) {
            --l_;
            if (!las[a[l_]] && !fir[a[l_]]) las[a[l_]] = l_;
            else temp = max(temp, las[a[l_]] - l_);
        }
        ans[q[i].id] = temp;
        while (l_ < l) {
            if (!fir[a[l_]]) las[a[l_]] = 0;
            ++l_;
        }
    }
    for (int i = 1; i <= m; ++i) printf("%d
", ans[i]);
    return 0;
}

单调栈

// time : 20200103
// test on https://www.luogu.com.cn/problem/P5788

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <stack>
#define M 3000001

inline void read(int &T) {
    int x = 0; bool f = 0; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = !f; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    T = f ? -x : x;
}

std::stack<int> s;
int n, a[M], ans[M];

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= n; ++i) {
        while (!s.empty() && a[s.top()] < a[i]) {
            ans[s.top()] = i; s.pop();
        }
        s.push(i);
    }
    for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
    return 0;
}

单调队列

// time : 20200103
// test on https://www.luogu.com.cn/problem/P1886

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#define M 1000001

inline void read(int &T) {
    int x = 0; bool f = 0; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = !f; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    T = f ? -x : x;
}

std::deque<int> q1, q2;
int n, k, a[M], min[M], max[M];

int main() {
    read(n), read(k);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= n; ++i) {
        while (!q1.empty() && q1.front() < i - k + 1) q1.pop_front();
        while (!q2.empty() && q2.front() < i - k + 1) q2.pop_front();
        while (!q1.empty() && a[q1.back()] >= a[i]) q1.pop_back();
        while (!q2.empty() && a[q2.back()] <= a[i]) q2.pop_back();
        q1.push_back(i), q2.push_back(i);
        min[i] = a[q1.front()], max[i] = a[q2.front()];
    }
    for (int i = k; i <= n; ++i) printf("%d ", min[i]);
    puts("");
    for (int i = k; i <= n; ++i) printf("%d ", max[i]);
    return 0;
}

Trie

// time : 20210109
// test on https://www.luogu.com.cn/problem/P2580

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define M 500001

int n, m;
std::string s;
struct Trie {
    int ender[M];
    int cnt, node[M][27];
    void clear() {
        cnt = 0;
        memset(node, 0, sizeof node);
        memset(ender, 0, sizeof ender);
    }
    void ins() {
        int len = s.length(), now = 0;
        for (int i = 0; i < len; ++i) {
            if (!node[now][s[i] - 'a']) node[now][s[i] - 'a'] = ++cnt;
            now = node[now][s[i] - 'a'];
        }
        ender[now] = true;
    }
    void find() {
        int len = s.length(), now = 0;
        for (int i = 0 ; i < len; ++i) {
            if (node[now][s[i] - 'a']) now = node[now][s[i] - 'a'];
            else { puts("WRONG"); return; }
        }
        ++ender[now];
        if (ender[now] > 2) puts("REPEAT");
        else puts("OK");
    }
}t;

int main() {
    scanf("%d", &n); t.clear();
    for (int i = 1; i <= n; ++i) { std::cin >> s; t.ins(); }
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) { std::cin >> s; t.find(); }
    return 0;
}

倍增求LCA

// time : 20210110
// test on https://www.luogu.com.cn/problem/P3379

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define M 500001

inline void read(int &T) {
    int x = 0; bool f = 0; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = !f; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    T = f ? -x : x;
}

int n, m, s, pthn, head[M];
int lg[M], dep[M], fa[M][21];
struct Edge {
    int nxt, to;
}pth[M << 1];

void add(int frm, int to) {
    pth[++pthn].to = to, pth[pthn].nxt = head[frm];
    head[frm] = pthn;
}

void dfs(int u, int father) {
    fa[u][0] = father, dep[u] = dep[father] + 1;
    for (int i = head[u]; i; i = pth[i].nxt) {
        int x = pth[i].to;
        if (x != father) dfs(x, u);
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) std::swap(x, y);
    while (dep[x] > dep[y]) {
        x = fa[x][lg[dep[x] - dep[y]] - 1];
    }
    if (x == y) return x;
    for (int k = lg[dep[x]] - 1; k >= 0; --k) {
        if (fa[x][k] != fa[y][k]) {
            x = fa[x][k];
            y = fa[y][k];
        }
    }
    return fa[x][0];
}

int main() {
    read(n), read(m), read(s);
    for (int i = 1, u, v; i < n; ++i) {
        read(u), read(v);
        add(u, v), add(v, u);
    }
    for (int i = 1; i <= n; ++i) {
        lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == i);
    }
    dfs(s, 0);
    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 1; i <= n; ++i) {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
        }
    }
    for (int i = 1, x, y; i <= m; ++i) {
        read(x), read(y);
        printf("%d
", lca(x, y));
    }
    return 0;
}