模板库
|
404
|
3
|
OI

1697 字
|
1.3 小时

杂

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++)
#define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i--)
using namespace std;
using LL = long long;
using VI = vector<int>;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    return 0;
}

VScode 用户代码片段

{
    "Print to console": {
        "scope": "cpp",
        "prefix": "tou",
        "body": [
            "#include <bits/stdc++.h>",
            "#define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++)",
            "#define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i--)",
            "using namespace std;",
            "using LL = long long;",
            "using VI = vector<int>;",
            "",
            "signed main() {",
            "  ios::sync_with_stdio(0);",
            "  cin.tie(0); cout.tie(0);",
            "  $0",
            "  return 0;",
            "}",
        ],
        "description": "头文件"
    },
    "Print to console2": {
        "scope": "cpp",
        "prefix": "codeforces",
        "body": [
            "#include <bits/stdc++.h>",
            "#define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++)",
            "#define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i--)",
            "using namespace std;",
            "using LL = long long;",
            "using VI = vector<int>;",
            "",
            "void solve() {",
            "  $0",
            "}",
            "",
            "signed main() {",
            "  ios::sync_with_stdio(0);",
            "  cin.tie(0); cout.tie(0);",
            "  int T; cin >> T;",
            "  while(T--) solve();",
            "  return 0;",
            "}",
        ],
        "description": "头文件"
    }
}

高精度加法

using LL = long long;
using VI = vector<int>;
const LL p = 1e10;

struct LINT {
    vector<LL> A; 
    int n;
    LINT() : A(1) {}
    LINT(LL x) : A(1) {
        for(; x; x /= p) A.push_back(x % p);
        n = (int)A.size() - 1; 
    }
    LINT operator+(LINT B) {
        LINT tmp; tmp.n = max(B.n, n);
        tmp.A.resize(tmp.n + 1);
        rep(i, 1, tmp.n) {
            if(i <= n) tmp.A[i] += A[i];
            if(i <= B.n) tmp.A[i] += B.A[i];
            if(tmp.A[i] >= p && i + 1 > tmp.n) tmp.A.push_back(tmp.A[i] / p), tmp.n++;
            else tmp.A[i + 1] += tmp.A[i] / p;
            tmp.A[i] %= p;
        }
        return tmp;
    } 
    LINT operator*(int x) {
        LINT tmp; tmp.n = n; tmp.A = A;
        rep(i, 1, tmp.n) tmp.A[i] *= x;
        rep(i, 1, tmp.n - 1) tmp.A[i + 1] += tmp.A[i] / p, tmp.A[i] %= p;
        for(; tmp.A[tmp.n] >= p; ) tmp.A.push_back(tmp.A[tmp.n] / p), tmp.A[tmp.n] %= p, tmp.n++;
        return tmp;
    }
    void print() {
        cout << A[n];
        per(i, n - 1, 1) {
            int c = 10;
            while(c < p && A[i] * c < p) cout << 0, c *= 10;
            cout << A[i];
        }
        cout << '\n';
    } 
};

__int128

输出

ostream &operator<<(ostream &os, const BI &n) {
    if (n > 9) os << (n / 10);
    return os << (int)(n % 10);
}

数据结构

树状数组

struct BIT {
    int n;
    vector<LL> T;
    BIT(int _n) : n(_n + 1) ,T(_n + 5) {    };
    int lowbit(int x) {return x & -x;}
    void add(int x, int v) {
        for(++x; x <= n; x += lowbit(x)) (T[x] += v);
    }
    LL ask(int x) {
        LL res = 0;                                 // 不赋初值见祖宗！！！！！ 
        for(++x; x > 0; x -= lowbit(x)) (res += T[x]);
        return res;
    }
    LL query(int l, int r) {
        if(l > r) return 0;
        return ask(r) - ask(l - 1); 
    }
    void clear() {fill(T.begin(), T.end(), 0); }
};

区间修改查询树状数组

struct fenwick {
    int n;
    struct BIT {
        int n;
        vector<int> T;
        BIT(int _n) : n(_n) ,T(_n + 5) {    };
        int lowbit(int x) {return x & -x;}
        void modify(int x, int v) {
            for(x; x <= n; x += lowbit(x)) T[x] += v;
        }
        ll query(int x) {
            ll res = 0;
            for(; x > 0; x -= lowbit(x)) res += T[x];
            return res;
        }
    };
    BIT T1, T2;
    fenwick(int _n) : n(_n), T1(n), T2(n) { }
    void modif(int x, int v) { T1.modify(x, (x - 1) * v); T2.modify(x, v); }
    ll quer(int y) { return T2.query(y) * y - T1.query(y); }
    void modify(int l, int r, int v) { modif(l ,v); modif(r + 1, -v); }
    ll query(int l, int r) { return quer(r) - quer(l - 1); }
};

线段树

线段树模板新(区间最大值)

#define ls (x << 1)
#define rs ((x << 1) + 1)

struct SegTree {
    int n; 
    struct Node {
        ll mx, tag;
    };
    vector<Node> T;
    SegTree(int _n) : n(_n), T((n << 2) + 1) {}
    void apply(int x, int v) {
        T[x].mx = v;
        T[x].tag = v;
    }
    void pushdown(int x) {
        if(!T[x].tag) return ;
        apply(ls, T[x].tag);
        apply(rs, T[x].tag);
        T[x].tag = 0;
    }
    void update(int L, int R, ll v, int x = 1, int l = 1, int r = -1) {
        if(r == -1) r = n;
        if(L <= l && r <= R) {
            T[x].mx = v;
            T[x].tag = v;
            return ;
        }
        int mid = l + r >> 1;
        pushdown(x);
        if(L <= mid) update(L, R, v, ls, l, mid);
        if(R > mid) update(L, R, v, rs, mid + 1, r);
        T[x].mx = max(T[ls].mx, T[rs].mx);
    }
    ll query(int L, int R, int x = 1, int l = 1, int r = -1) {
        if(r == -1) r = n;
        if(L <= l && r <= R) 
            return T[x].mx;
        ll res = -1e18;
        int mid = l + r >> 1;   
        pushdown(x);
        if(L <= mid) res = max(res, query(L, R, ls, l, mid));
        if(R > mid) res = max(res, query(L, R, rs, mid + 1, r));
        return res;
    }
};

#undef ls
#undef rs

区间求和线段树

#define ls (x << 1)
#define rs ((x << 1) | 1)

struct SegTree {
    struct Node {
        ll val, tag;
    };
    vector<Node> T;
    int n;
    SegTree() { }
    SegTree(int _n) : n(_n), T((_n << 2)  +5) {}
    void pushdown(int x, int l, int r) {
        auto &t = T[x];
        if(t.tag == 0) return ;
        int mid =  (l + r) / 2;
        (T[ls].tag += T[x].tag);
        (T[rs].tag += T[x].tag);
        (T[ls].val += 1ll * (mid - l + 1) * T[x].tag) ;
        (T[rs].val += 1ll * (r - (mid + 1) + 1) * T[x].tag ) ;
        t.tag = 0;
    }
    void modify(int L, int R, int v, int x = 1, int l = 1, int r = -1) {
        if(r == -1) r = n;
        auto &t = T[x];
        assert(x <= n << 2);
        if(L <= l && r <= R) {
            (t.tag += v) ;
            (t.val += 1ll * (r - l + 1) * v ) ;
            return ;
        }
        pushdown(x, l, r);
        int mid = (l + r) / 2;
        if(L <= mid) modify(L, R, v, ls, l, mid);
        if(R > mid) modify(L, R, v, rs, mid + 1, r);
        (T[x].val = T[ls].val + T[rs].val) ;
    }
    ll query(int L, int R, int x = 1, int l = 1, int r = -1) {
        if(r == -1) r = n;
        auto &t = T[x];
        if(L <= l && r <= R) {
            return t.val;
        }
        pushdown(x, l, r);
        int mid = (l + r) / 2;
        ll res = 0;
        if(L <= mid) res += query(L, R, ls, l, mid);
        if(R > mid) res += query(L, R, rs, mid + 1, r);
        return res;
    }
};
SegTree T;
#undef ls
#undef rs

历史最值线段树

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i ,a ,b) for(int i = (a); i >= (b); i--)

using namespace std;
const int N = 5e5 + 5;
typedef long long ll;

int n, m;
int a[N];

struct tree{
    ll sum; 
    int l, r, maxa, cnt, se, maxb;
    int add1, add2, add3, add4;
}t[N << 4];

#define ls x << 1
#define rs x << 1 | 1

void pushup(int x) {
    t[x].sum = t[ls].sum + t[rs].sum;
    t[x].maxa = max(t[ls].maxa, t[rs].maxa);
        t[x].maxb = max(t[ls].maxb, t[rs].maxb);
        if(t[ls].maxa == t[rs].maxa) {
        t[x].cnt = t[ls].cnt + t[rs].cnt;
        t[x].se = max(t[ls].se, t[rs].se);
    }
    if(t[ls].maxa > t[rs].maxa)  {
        t[x].cnt = t[ls].cnt;
        t[x].se = max(t[ls].se, t[rs].maxa);
    }
    if(t[ls].maxa < t[rs].maxa) {
        t[x].cnt = t[rs].cnt;
        t[x].se = max(t[ls].maxa, t[rs].se);
    }
}

void apply(int x, int tag1, int tag2, int tag3, int tag4) {
    t[x].sum += 1ll * tag1 * t[x].cnt + 1ll * tag2 * (t[x].r - t[x].l + 1 - t[x].cnt);
    t[x].maxb = max(t[x].maxb, t[x].maxa + tag3);       //在给maxb赋值的时候，将 = 写成 +=，表现：区间历史最大值莫名其妙很大。
    t[x].maxa += tag1;
    if(t[x].se != -2e9) t[x].se += tag2;
    t[x].add3 = max(t[x].add3, t[x].add1 + tag3);
    t[x].add4 = max(t[x].add4, t[x].add2 + tag4);
    t[x].add1 += tag1; t[x].add2 += tag2;
} 

void pushdown(int x) {

    int mxn = max(t[ls].maxa, t[rs].maxa);
    if(t[ls].maxa == mxn) 
        apply(ls, t[x].add1, t[x].add2, t[x].add3, t[x].add4);
    else apply(ls, t[x].add2, t[x].add2, t[x].add4, t[x].add4);     //else 的赋值错误，若不是最大值则应该赋非最大值的懒标记，表现：极少情况下（有可能是数据范围太小了）会偶尔冒出来一个错误的求和操作。
    if(t[rs].maxa == mxn) 
        apply(rs, t[x].add1, t[x].add2, t[x].add3, t[x].add4);
    else apply(rs, t[x].add2, t[x].add2, t[x].add4, t[x].add4);     // else 的赋值错误，若不是最大值则应该赋非最大值的懒标记，表现：极少情况下（有可能是数据范围太小了）会偶尔冒出来一个错误的求和操作。
    t[x].add1 = t[x].add2 = t[x].add3 = t[x].add4 = 0; 
}
void bulid(int x, int l, int r) {
    t[x].l = l; t[x].r = r;
    t[x].add1 = t[x].add2 = t[x].add3 = t[x].add4 = 0;
    if(l == r) {
        t[x].maxa =  t[x].maxb = t[x].sum = a[l];
        t[x].se = -2e9; t[x].cnt = 1; 
        return ;
    }
    int mid = (l + r) >> 1;
    bulid(ls, l, mid);
    bulid(rs, mid + 1, r);
    pushup(x);
}

void modify_add(int x, int l, int r, int v) {
    if(t[x].r < l || t[x].l > r) return ;
    if(l <= t[x].l && t[x].r <= r) {
        apply(x, v, v, v, v);
        return ;
    }
    pushdown(x);    
    modify_add(ls, l, r, v); modify_add(rs, l, r, v);
    pushup(x);
}

void modify_min(int x, int l, int r, int v) {
    if(t[x].r < l || t[x].l > r || v >= t[x].maxa) return ;     //退出条件少写了，表现：把最小值改大了。
    if(l <= t[x].l && t[x].r <= r && t[x].se < v) {             //条件少写了，表现：把最小值改大了。
        int tmp = t[x].maxa - v;
        // t[x].sum -= 1ll * t[x].cnt * tmp;
        // t[x].maxa = v; t[x].add1 -= tmp;
        apply(x, -tmp, 0, -tmp, 0);
        // apply(x, v - t[x].maxa, 0, v - t[x].maxa, 0);
        return ;
    }
    pushdown(x);
    modify_min(ls, l, r, v); modify_min(rs, l, r, v);
    pushup(x);
}

ll query_sum(int x, int l, int r) {
    if(t[x].r < l || t[x].l > r) return 0;
    if(l <= t[x].l && t[x].r <= r) 
        return t[x].sum;
    pushdown(x);
    return query_sum(ls, l, r) + query_sum(rs, l, r);
}

int query_maxa(int x, int l, int r) {
    if(t[x].r < l || t[x].l > r) return -2e9;   //不小心 return 0，而不是返回-inf，表现：最大值输出0
    if(l <= t[x].l && t[x].r <= r) 
        return t[x].maxa;
    pushdown(x);
    return max(query_maxa(ls, l, r), query_maxa(rs, l, r));
}

int query_maxb(int x, int l, int r) {
    if(t[x].r < l || t[x].l > r) return -2e9;   //不小心 return 0，而不是返回-inf，表现：最大值输出0
    if(l <= t[x].l && t[x].r <= r) 
        return t[x].maxb;
    pushdown(x);
    return max(query_maxb(ls, l, r),query_maxb(rs, l, r));
}

#undef ls
#undef rs

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    rep(i, 1, n) cin >> a[i];
    bulid(1, 1, n);
    while(m--) {
        int op, l, r, v;
        cin >> op >> l >> r;
        if(op == 1) {
            cin >> v;
            modify_add(1, l, r, v);
        }
        if(op == 2) {
            cin >> v;
            modify_min(1, l, r, v);
        } 
        if(op == 3) cout << query_sum(1, l, r) << &#039;n&#039;;
        if(op == 4) cout << query_maxa(1, l, r) << &#039;n&#039;;
        if(op == 5) cout << query_maxb(1, l, r) << &#039;n&#039;;
    }

    return 0;
}

// P6242 【模板】线段树 3（区间最值操作、区间历史最值）

线段树合并

struct SegTree {
    static constexpr int N = 5000005 + 5;
    int sum[N], res[N], ls[N], rs[N];
    int n, cnt = 0;
    SegTree(int _n) {n = _n;}
    void update(int x) {
        if(sum[ls[x]] < sum[rs[x]]) {
            res[x] = res[rs[x]];
            sum[x] = sum[rs[x]];
        }
        else {
            res[x] = res[ls[x]];
            sum[x] = sum[ls[x]];
        }
    }
    int merge(int a, int b, int l = 1, int r = -1) {
        if (r == -1) r = n;
        if(!a || !b) return max(a, b);
        if(l == r) {
            sum[a] += sum[b];
            return a;
        }    
        int mid = l + r >> 1;
        ls[a] = merge(ls[a], ls[b], l, mid);
        rs[a] = merge(rs[a], rs[b], mid + 1, r);
        update(a);
        return a;
    }
    int modify(int it, int val, int x, int l = 1, int r = -1)  {
        if(r == -1) r = n;
        if(!x) x = ++cnt;
        if(l == r) {
            sum[x] += val; res[x] = it;
            return x;
        }
        int mid = l + r >> 1;
        if(it <= mid) ls[x] = modify(it, val, ls[x], l, mid);
        else rs[x] = modify(it, val, rs[x], mid + 1, r);
        update(x);
        return x;
    }
}T(1e5);

树链剖分

// P4211 
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++)
#define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i--)
using namespace std;
typedef long long ll;
using VI = vector<int>;
const int mod = 201314;

#define ls (x << 1)
#define rs ((x << 1) | 1)

struct SegTree {
    struct Node {
        ll val, tag;
    };
    vector<Node> T;
    int n;
    SegTree() { }
    SegTree(int _n) : n(_n), T((_n << 2)  +5) {}
    void pushdown(int x, int l, int r) {
        auto &t = T[x];
        if(t.tag == 0) return ;
        int mid =  (l + r) / 2;
        (T[ls].tag += T[x].tag);
        (T[rs].tag += T[x].tag);
        (T[ls].val += 1ll * (mid - l + 1) * T[x].tag) ;
        (T[rs].val += 1ll * (r - (mid + 1) + 1) * T[x].tag ) ;
        t.tag = 0;
    }
    void modify(int L, int R, int v, int x = 1, int l = 1, int r = -1) {
        if(r == -1) r = n;
        auto &t = T[x];
        assert(x <= n << 2);
        if(L <= l && r <= R) {
            (t.tag += v) ;
            (t.val += 1ll * (r - l + 1) * v ) ;
            return ;
        }
        pushdown(x, l, r);
        int mid = (l + r) / 2;
        if(L <= mid) modify(L, R, v, ls, l, mid);
        if(R > mid) modify(L, R, v, rs, mid + 1, r);
        (T[x].val = T[ls].val + T[rs].val) ;
    }
    ll query(int L, int R, int x = 1, int l = 1, int r = -1) {
        if(r == -1) r = n;
        auto &t = T[x];
        if(L <= l && r <= R) {
            return t.val;
        }
        pushdown(x, l, r);
        int mid = (l + r) / 2;
        ll res = 0;
        if(L <= mid) res += query(L, R, ls, l, mid);
        if(R > mid) res += query(L, R, rs, mid + 1, r);
        return res;
    }
};
SegTree T;
#undef ls
#undef rs

const int N = 1e5 + 5;
int si[N], dep[N], fa[N], top[N], hs[N], re[N], dfn[N];
vector<int> G[N];

void dfs1(int x, int f) {
    si[x] = 1, dep[x] = dep[f] + 1; fa[x] = f;
    for(auto to : G[x]) if(to != f) {
        dfs1(to, x);
        si[x] += si[to];
        if(si[hs[x]] < si[to]) hs[x] = to;
    }
}

void dfs2(int x, int tp) {
    top[x] = tp;
    re[x] = ++dfn[0];
    if(hs[x]) dfs2(hs[x], tp);
    for(auto to : G[x]) if(to != fa[x] && to != hs[x]) {
        dfs2(to, to);
    }
}

int n;
void mdf(int x, int y, int v) {
    if(y == 0) return ;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        T.modify(re[top[x]], re[x], v);
        // T.modify(1, n, v);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    T.modify(re[x], re[y], v);
    // T.modify(1, n, v);
}

ll qry(int x, int y) {
    int res = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        res += T.query(re[top[x]], re[x]);
        // res += T.query(1, n);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    res += T.query(re[x], re[y]);
    return res % mod;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int m; cin >> n >> m;
    T = SegTree(n);
    for(int i = 2, x; i <= n; i++) cin >> x, x++, G[x].emplace_back(i), G[i].emplace_back(x);
    struct Node {
        int id, it, z, tag;
    };
    vector<Node> Q(1);
    for(int i = 1, l, r, z; i <= m; i++) 
        cin >> l >> r >> z, l, r++, z++, Q.push_back({i, l, z, 0}), Q.push_back({i, r, z, 1});
    sort(Q.begin() + 1, Q.end(), [](const Node &x, const Node &y) {
        return x.it < y.it;
    });
    dfs1(1, 0);
    dfs2(1, 0);
    vector<array<int, 2>> ans(m + 1);
    int nw = 0;
    rep(i, 1, 2 * m) {
        while(nw < Q[i].it) mdf(1, ++nw, 1);
        ans[Q[i].id][Q[i].tag] = qry(1, Q[i].z);
    }
    rep(i, 1, m) {
        // cout << ans[i][1] << " " << ans[i][0] << &#039;n&#039;;
        cout << (ans[i][1] - ans[i][0] + mod) % mod << &#039;n&#039;;
    }
    return 0;
}

主席树

//主席树 
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++)
#define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i--)
using namespace std;
typedef long long ll;
//#define int long long

struct SegTree {
    int n, idx = 0;
    struct Node {
        int ls, rs, sum;
    };
    vector<Node> T;
    SegTree (int _n) : n(_n), T((_n * 100) + 5) {   }   // 不要忘记乘以 100，不能够再小了。
    int modify(int it, int ls, int l = 1, int r = -1) {
        if(r == -1) r = n;
        int nw = ++idx, mid = l + r >> 1;
        T[nw] = T[ls]; T[nw].sum++;
        if(l < r) {
            if(it <= mid) T[nw].ls = modify(it, T[ls].ls, l, mid);
            else T[nw].rs = modify(it, T[ls].rs, mid + 1, r);
        }   
        return nw;
    } 
    int query(int L, int R, int k, int l = 1, int r = -1) {
        if(r == -1) r = n;
        int mid = l + r >> 1;
        int su = T[T[R].ls].sum - T[T[L].ls].sum;
        if(l >= r) return l;
        if(su >= k) return query(T[L].ls, T[R].ls, k, l, mid);
        else return query(T[L].rs, T[R].rs, k - su, mid + 1, r);
    }
}; 

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q; cin >> n >> q;
    vector<int> A(n + 10), rt(n + 10);
    rep(i, 1, n) cin >> A[i];
    auto B = A;
    sort(B.begin() + 1, B.begin() + 1 + n);
    int nb = unique(B.begin() + 1, B.begin() + 1 + n) - B.begin() - 1;
    SegTree T(nb);
    rep(i, 1, n) {
        int t = lower_bound(B.begin() + 1, B.begin() + 1 + nb, A[i]) - B.begin();   // 二分的时候要在 B 的范围内枚举 
        rt[i] = T.modify(t, rt[i - 1]);
    }
    for(int x, y ,z; q && cin >> x >> y >> z; q--) {
        int t = T.query(rt[x - 1], rt[y], z);
        cout << B[t] << &#039;n&#039;;
    }
    return 0;
}

图论

最小生成树

array<int, 3> E[M];
int vis[M];
ll mns = 0;
namespace kruskal {
    vector<int> fa;
    int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
    bool merge(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return false;
        fa[x] = y;
        return true;
    }
    void work() {
        sort(E + 1, E + 1 + m);
        fa.resize(n + 1);
        iota(fa.begin(), fa.end(0), 0);
        int cnt = 1;
        rep(i, 1, m) {
            int x = E[i][1], y = E[i][2];
            if(merge(x, y)) mns += E[i][0], cnt++, G[x].push_back({y, E[i][0]}), G[y].push_back({x, E[i][0]});
            if(cnt == 0) break;
        }
    }
}

LCA

树链剖分

vector<int> G[maxn];
int si[maxn], top[maxn], hson[maxn], fa[maxn], dep[maxn];

void dfs1(int x, int f) {
    si[x] = 1; dep[x] = dep[f] + 1; fa[x] = f;
    for(auto to : G[x]) {
        if(to == f) continue;
        dfs1(to, x);
        si[x] += si[to];
        if(si[to] > si[hson[x]]) hson[x] = to;
    }
}

void dfs2(int x, int tp) {
    top[x] = tp;
    if(!hson[x]) return ;
    dfs2(hson[x], tp);
    for(auto to : G[x]) {
        if(to == fa[x] || to == hson[x]) continue;
         dfs2(to, to);       
    }
}

int lca(int x, int y) {
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);   
        x = fa[top[x]];
    }
    return (dep[x] < dep[y] ? x : y);
}

倍增

const int maxn = 500000 + 5;
const int maxk = 21; // log2(maxn) + 1

int fa[maxk][maxn];
int depth[maxn];
vector<int> vec[maxn];

void dfs(int x, int f)
{
    fa[0][x] = f;
    depth[x] = depth[f] + 1;
    for (int i = 1; i < maxk; i++)
    {
        fa[i][x] = fa[i - 1][fa[i - 1][x]];
    }
    for (auto to : vec[x])
    {
        if (to == f)
            continue;
        dfs(to, x);
    }
}

int LCA(int x, int y)
{
    if (depth[x] < depth[y])
        swap(x, y);
    for (int i = maxk - 1; i >= 0; i--)
    {
        if (depth[fa[i][x]] >= depth[y])
            x = fa[i][x];
    }
    if (x == y)
        return x;
    for (int i = maxk - 1; i >= 0; i--)
    {
        if (fa[i][x] != fa[i][y])
        {
            x = fa[i][x];
            y = fa[i][y];
        }
    }
    return fa[0][x];
}

dfs 序

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int maxn = 500000 + 5;

int n, m, s;
vector<int> G[maxn];
int dfn[maxn], mi[20][maxn];

int get(int x, int y) {
    return dfn[x] < dfn[y] ? x : y;
}

void dfs(int x, int f) {
    dfn[x] = ++dfn[0]; mi[0][dfn[x]] = f;
    for(auto to : G[x]) if(to != f) dfs(to, x);
}

int lca(int x, int y) {
    if(x == y) return x;
    if((x = dfn[x]) > (y = dfn[y])) swap(x, y);
    int d = log2(y - x++);
    return get(mi[d][x], mi[d][y - (1 << d) + 1]);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> s;
    for(int i = 1, u, v; i < n; i++)  {
        cin >> u >> v;
        G[u].push_back(v); G[v].push_back(u);
    }
    dfs(s, 0);
    for(int i = 1; i <= log2(n); i++) for(int j = 1; j + (1 << i) - 1 <= n; j++) 
        mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]);
    while(m--) {
        int x, y;
        cin >> x >> y;
        cout << lca(x, y) << "n";
    }
    return 0;
}

最短路

Floyd

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
typedef long long ll;
const int N = 500 + 5;
#define int long long

ll a[N][N];
int n, m, q;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    rep(i, 1, n) rep(j, 1, n) a[i][j] = LLONG_MAX;
    for(int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        a[u][v] = a[v][u] = min(a[u][v], w);    //重边处理
    }
    rep(i, 1, n) a[i][i] = 0;               //自己到自己
    rep(k, 1, n) rep(i, 1, n) rep(j ,1 ,n)
        if(a[i][k] != LLONG_MAX && a[k][j] != LLONG_MAX && i != k && j != k)        //ik, jk 不同 
            a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
    for(int i = 1, u, v; i <= q; i++) {
        cin >> u >> v;
        cout << (a[u][v] == LLONG_MAX ? -1 : a[u][v]) << &#039;n&#039;;
    }
    return 0;
}

Dijkstra

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++)
#define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i--)
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int, int> pii;
const int N = 1e5 + 5;

int n, m, s = 1;
vector<pii> G[N];
ll dis[N];
bool vis[N];

void Dijkstra() {
    for(int i = 1; i <= n; i++) dis[i] = 1e18;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    dis[s] = 0; 
    q.push({0, s});

    while(!q.empty()) {
        int x = q.top().second; q.pop();
        if(vis[x]) continue;            //vis数组
        vis[x] = true;
        for(auto to : G[x] ){
            if(dis[to.first] > dis[x] + to.second) {
                dis[to.first] = dis[x] + to.second;
                if(!vis[to.first])
                    q.push({dis[to.first], to.first});

            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> s;
    for(int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        G[u].push_back({v, w});
    }
    Dijkstra();
    rep(i, 1, n) cout << dis[i] << " n"[i == n];

    return 0;
}

网络最大流

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
typedef long long ll;
const int N = 200 + 5, M = 5000 + 5;
#define int long long

int n, m, s, t;
int tot = 1, head[M], cur[M];
int dep[M];
ll ans;

struct edge {
    int v, nxt;
    ll val;
}e[M * 2];

void add(int u, int v, ll w) {
    e[++tot].v = v;
    e[tot].val = w;
    e[tot].nxt = head[u];
    head[u] = tot;

    e[++tot].v = u;
    e[tot].val = 0;
    e[tot].nxt = head[v];
    head[v] = tot;
}

int bfs() {
    queue<int> q;
    memset(dep, 0, sizeof(dep));    //数组没有清空，表现：死循环退不出去。
    q.push(s);
    dep[s] = 1;
    cur[s] = head[s];
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v;
            if(e[i].val > 0 && !dep[v]) {
                q.push(v);
                cur[v] = head[v];
                dep[v] = dep[u] + 1;
                if(v == t) return 1;
            }
        }
    }
    return dep[t];
}

int dfs(int u, ll sum) {
    if(u == t || !sum) return sum;
    ll k, res = 0;
    for(int i = cur[u]; i && sum; i = e[i].nxt) {
        int v = e[i].v;
        cur[u] = i; //没有加弧优化TLE
        if(e[i].val > 0 && dep[v] == dep[u] + 1) {
            k = dfs(v, min(sum, e[i].val));
            if(k == 0) dep[v] = 0;
            e[i].val -= k;
            e[i^1].val += k;    //val错写成v，表现：可能死循环，也可能有一些其他的问题，尚不确定。
            res += k;
            sum -= k;
        }
    }
    return res;
}

signed main()  {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> s >> t;
    rep(i, 1, m) {
        int u, v; ll w;
        cin >> u >> v >> w;
        add(u, v, w);
    }
    while(bfs()) {
        ans +=  dfs(s, LLONG_MAX);
    }
    cout << ans << &#039;n&#039;;

    return 0;
}

SCC

struct SCC {
    int n, idx, cnt;
    vector<VI> G;
    VI stk, dfn, low, belong;
    SCC(int _n) : n(_n), G(n + 1), low(n + 1), belong(n + 1), dfn(n + 1) {
        idx = cnt = 0;
    }   
    void add(int u, int v) {G[u].push_back(v); };
    int dfs(int x) {
        low[x] = dfn[x] = ++idx;
        stk.push_back(x);
        for(auto to : G[x]) {
            if(!dfn[to]) 
                low[x] = min(low[x], dfs(to));
            else if(!belong[to])
                low[x] = min(low[x], low[to]);
        }
        if(low[x] == dfn[x]) {
            cnt++;
            for(int i = -1; i != x; stk.pop_back()) 
                i = stk.back(), belong[i] = cnt;
        }
        return low[x];

    }
};

EBCC

struct EBCC {
    int n, idx;
    vector<VI> G;
    VI dfn, low;
    set<int> ans;
    EBCC(int _n) : n(_n), dfn(_n + 1), low(_n + 1), G(_n + 1) {
        idx = 0;
    }
    void add(int u, int v) {
        G[u].push_back(v), G[v].push_back(u);
    }
    int dfs(int x, int p) {
        int ch = 0;
        low[x] = dfn[x] = ++idx;
        for(auto to : G[x])  {
            if(!dfn[to]) {
                ch++;
                int t = dfs(to, x);
                low[x] = min(low[x], t);
                if(t >= dfn[x] && p != -1) 
                    ans.insert(x);
            }
            else 
                low[x] = min(low[x], dfn[to]);
        }
        if(ch >= 2 && p == -1) ans.insert(x);
        return low[x];
    }
};

点分治

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++)
#define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i--)
using namespace std;
typedef long long ll;
using VI = vector<int>;
const int N = 1e4 + 5;

int n, m;
vector<array<int, 2>> G[N];
int qe[N], vis[N], mx[N], si[N], st[N], dis[N];
vector<int> A(1);
int rt = 0;

void groot(int x, int fa, int sum) {
    si[x] = 1; mx[x] = 0;
    for(auto i : G[x]) {
        int to = i[0];
        if(to == fa || vis[to]) continue;
        groot(to, x, sum);
        si[x] += si[to];
        mx[x] = max(mx[x], si[to]);
    }
    mx[x] = max(mx[x], sum - si[x]);
    if(mx[x] < mx[rt]) rt = x;
}

void gdis(int x, int fa, int v, int ty) {
    A.emplace_back(x);
    st[x] = ty; dis[x] = v;
    for(auto i : G[x]) {
        int to = i[0], w =i[1];
        if(to == fa || vis[to]) continue;
        gdis(to, x, v + w, ty);
    }
}

int ok[N];

void dfs(int x) {
    vis[x] = 1;
    A.assign(1, 0);
    A.emplace_back(x); 
    dis[x] = 0; st[x] = x;
    for(auto i : G[x]) {
        int to = i[0];
        if(vis[to]) continue;
        gdis(to, x, i[1], to);
    }
    sort(A.begin() + 1, A.end(), [&](const int &x, const int &y) {
        return dis[x] < dis[y];
    });
    rep(i ,1, m) {
        int l = 1, r = (int) A.size() - 1;
        while(l < r) {
            if(dis[A[l]] + dis[A[r]] > qe[i]) r--;
            else if(dis[A[l]] + dis[A[r]] < qe[i]) l++;
            else if(st[A[l]] == st[A[r]]) {
                if(dis[A[r]] == dis[A[r - 1]]) r--;
                else l++;
            }
            else {
                ok[i] = 1;
                break;
            }
        }
    }
    for(auto i : G[x]) {
        int to = i[0];
        if(vis[to]) continue;
        rt = 0;
        groot(to, 0, si[to]);
        dfs(rt);
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;    
    for(int i = 1, u, v ,w; i < n; i++ )
        cin >> u >> v >> w, G[u].push_back({v, w}), G[v].push_back({u, w});
    rep(i, 1, m) cin >> qe[i];
    mx[0] = n + 1;
    groot(1, 0, n);
    dfs(rt);
    rep(i ,1, m) cout << (ok[i] ? "AYE" : "NAY") << '\n';
    return 0;
}

树上启发式合并

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++)
#define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i--)
using namespace std;
typedef long long ll;
using VI = vector<int>;
const int N = 1e5 + 5;
vector<int> G[N];

struct BIT {
    int n;
    vector<int> T;
    BIT(int _n) : n(_n) ,T(_n + 5) {    };
    int lowbit(int x) {return x & -x;}
    void add(int x, int v) {
        for(; x && x <= n; x += lowbit(x)) T[x] += v;
    }
    ll ask(int x) {
        ll res = 0;                                 // 不赋初值见祖宗！！！！！ 
        for(; x > 0; x -= lowbit(x)) res += T[x];
        return res;
    }
};

BIT T(N);

int n, m;
int c[N];
int hson[N], si[N], in[N], out[N], nd[N];

void dfs1(int x, int fa) {
    in[x] = ++in[0]; si[x] = 1;
    nd[in[0]] = x;
    for(auto to : G[x]) if(to != fa) {
        dfs1(to, x);
        si[x] += si[to];
        if(si[hson[x]] < si[to]) hson[x] = to;
    }
    out[x] = in[0];
}

int ans[N], cnt[N], tot = 0;
vector<array<int, 2>> q[N];

void update(int u, int v) {
    u = c[u];
    T.add(cnt[u], -1);
    cnt[u] += v;
    T.add(cnt[u], 1);
    // rep(i ,1, n) cout << cnt[i] << " \n"[i == n];
}

void getans(int x) {
    // rep(i, 1, n) cout << cnt[i] << " \n"[i == n];
    for(auto p : q[x]) ans[p[1]] = T.ask(1e5) - T.ask(p[0]);
}

void dfs2(int x, int fa, bool tag) {
    for(auto to : G[x]) if(to != fa && to != hson[x]) 
        dfs2(to, x, 0);
    if(hson[x]) dfs2(hson[x], x, 1);    
    update(x, 1);
    for(auto to : G[x]) if(to != hson[x] && to != fa) 
        rep(i, in[to], out[to]) update(nd[i], 1);
    getans(x);
    if(!tag) rep(i, in[x], out[x]) update(nd[i], -1);
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    fill(cnt, cnt + N, 1);
    T.add(1, n);
    rep(i ,1, n) cin >> c[i];
    for(int i = 1, u, v; i < n; i++) 
        cin >> u >> v, G[u].emplace_back(v), G[v].emplace_back(u);
    for(int u, c, i  =1; i <= m; i++) {
        cin >> u >> c;
        q[u].push_back({c, i});
    }
    dfs1(1, 0);
    dfs2(1, 0, 0);
    rep(i ,1, m) cout << ans[i] << '\n';
    return 0;
}

离线算法

莫队

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++)
#define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i--)
using namespace std;
typedef long long ll;
const int N = 50000 + 5; 

inline ll gcd(ll s1, ll s2){return s2 == 0 ? s1 : gcd(s2, s1 % s2); }

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m; cin >> n >> m;
    int L = sqrt(n);
    vector<int> A(n + 1), cnt(n + 1);
    rep(i, 1, n) cin >> A[i];
    using AI = array<int, 3>;
    vector<AI> Q(m + 1);
    rep(i, 1, m) cin >> Q[i][0] >> Q[i][1], Q[i][2] = i;
    sort(Q.begin() + 1, Q.end(), [&](const AI& x, const AI& y) {
        if(x[0] / L != y[0] / L) return x[0] / L < y[0] / L;
        return (x[0] / L) & 1 ? x[1] < y[1] : x[1] > y[1];
    });
    int l = 1, r = 0;
    ll ans = 0;
    vector<array<ll, 2>> aa(m + 1);
    Q[0][1] = n + 1;
    auto modify = [&](int &t, int tp) {
        if(tp == 1) ans += 1ll * t;
        else ans += 1ll * tp * (t - 1);
        t += tp;
    };
    rep(i, 1, m) {
        int nl = Q[i][0], nr = Q[i][1];
        while(r < nr) modify(cnt[A[++r]], 1);
        while(l > nl) modify(cnt[A[--l]], 1);
        while(r > nr) modify(cnt[A[r--]], -1);
        while(l < nl) modify(cnt[A[l++]], -1);       
        aa[Q[i][2]][0] = ans;
        aa[Q[i][2]][1] = 1ll * (r - l + 1) * (r - l) / 2;
    }
    rep(i, 1, m) {
        ll gd = gcd(aa[i][0], aa[i][1]);
        if(aa[i][0] == 0) cout << "0/1n";
        else cout << aa[i][0] / gd << &#039;/&#039; << aa[i][1] / gd<< &#039;n&#039;;
    }
    return 0;
}

CDQ 分治

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++)
#define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i--)
using namespace std;
typedef long long ll;
using VI = vector<int>;

struct BIT {
    int n;
    vector<int> T;
    BIT(int _n) : n(_n) ,T(_n + 5) {    };
    int lowbit(int x) {return x & -x;}
    void add(int x, int v) {
        for(x; x <= n; x += lowbit(x)) T[x] += v;
    }
    ll ask(int x) {
        ll res = 0;                                 // 不赋初值见祖宗！！！！！ 
        for(; x > 0; x -= lowbit(x)) res += T[x];
        return res;
    }
};

const int N = 1e5 + 5;

int n, m, k;
using AI = array<int, 5>;
vector<AI> A(1);
BIT T(2e5 + 5);

bool cmp(const AI &x, const AI &y) {
    if(x[1] != y[1]) return x[1] < y[1];
    return x[2] < y[2];
}

void cdq(int l, int r) {
    if(l == r) return ;
    int mid = l + r >> 1;
    cdq(l, mid); cdq(mid + 1, r);
    sort(A.begin() + l, A.begin() + mid + 1, cmp);
    sort(A.begin() + mid + 1, A.begin() + r + 1, cmp);
    int i = l, j = mid + 1;
    for(; j <= r; j++) {
        for(; i <= mid && A[i][1] <= A[j][1]; i++) 
            T.add(A[i][2], A[i][3]);
        A[j][4] += T.ask(A[j][2]);
    };
    rep(k, l, i - 1) T.add(A[k][2], -A[k][3]);
    return ;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    vector<AI> tmp(n + 2);
    rep(i, 1, n) rep(j, 0, 2) cin >> tmp[i][j];
    sort(tmp.begin() + 1, tmp.begin() + 1 + n);
    for(int i = 1, t = 0; i <= n; i++) {
        t++;
        if(tmp[i] != tmp[i + 1]) {
            A.push_back(tmp[i]);
            A[A.size() - 1][3] = t;
            t = 0;
        }
    }
    int m = A.size() - 1;
    // rep(i, 1, m) cout << A[i][0] << " " << A[i][1] << " " << A[i][2] << '\n';
    cdq(1, m);
    vector<int> ans(n + 1);
    rep(i, 1, m) ans[A[i][4] + A[i][3] - 1] += A[i][3];
    rep(i, 0, n - 1) cout << ans[i] << '\n';
    return 0;
}

字符串

Hash

struct Hash {
    int n; vector<ULL> XP, H;
    void init(string & s, ULL x) {
        n = s.size(); XP.resize(n + 1); H.resize(n + 1);
        XP[0] = 1;
        rep(i, 1, n) XP[i] = x * XP[i - 1] ;
        H[n] = 0;
        for(int i = n - 1; i >= 0; i--) H[i] = s[i] + x * H[i + 1];
    } 
    ULL c_hash(int i, int j) {
        return H[i] - H[j] * XP[j - i];
    }
};

KMP

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e6 + 5;

char a[maxn], b[maxn];
int nxt[maxn];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("akioi.in", "r", stdin);
    // freoepn("akioi.out", "w", stdout);
    cin >> (a + 1) >> (b + 1);
    int len1 = strlen(a + 1), len2 = strlen(b + 1 );
    for(int i = 2, j = 0; i <= len2; i++) {
        for(; j && b[i] != b[j + 1]; j = nxt[j]);
        j += (b[i] == b[j + 1]);
        nxt[i] = j;
    }
    for(int i = 1, j = 0; i <= len1; i++) {
        for(; j && a[i] != b[j + 1]; j = nxt[j]);
        j += (a[i] == b[j + 1]);
        if(j == len2) {
            cout << i - len2 + 1 << &#039;n&#039;;
            j = nxt[j];
        }
    }
    for(int i = 1; i <= len2; i++) 
        cout << nxt[i] << " n"[i == len2];
    return 0;
}

Manacher

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++)
#define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i--)
using namespace std;
typedef long long ll;
using VI = vector<int>;
const int N = 1.1e7 * 2 + 5;

int R[N];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string s, tmp; cin >> tmp; 
    s += "@|";
    for(auto c : tmp) s += c, s += "|";
    s += "#";
    int n = s.size() - 1;
    int ans = 0; 
    for(int i = 1, c = 0, r = 0; i < n; i++) {
        int &j = R[i] = r < i ? 1 : min(R[c * 2 - i], r - i + 1);
        while(s[i - j] == s[i + j]) j++;
        ans = max(ans, j - 1);
        if(i + j - 1 > r) r = i + j - 1, c = i;
    }
    cout << ans << '\n';
    return 0;
}

Z function

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++)
#define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i--)
using namespace std;
typedef long long ll;
using VI = vector<int>;
const int N = 2e7 + 6;

int z[N], p[N];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string a, b; cin >> b >> a;
    int n = a.size(), m = b.size();
    a = " " + a, b = " " + b;
    z[1] = n;
    for(int i = 2, l = 0, r = 0; i <= n; i++) {
        int &j = z[i] = i > r ? 0 : min(r - i + 1, z[i - l + 1]) ;
        while(a[1 + j] == a[i + j] && j < n) j++;
        if(i + j - 1 > r) r = i + j - 1, l = i;
    }
    for(int i = 1, l = 0, r = 0; i <= m; i++) {
        int &j = p[i] = i > r ? 0 : min(r - i + 1, z[i - l + 1]) ;
        while(j < n && a[1 + j] == b[i + j]) j++;
        if(i + j - 1 > r) r = i + j - 1, l = i;
    }
    ll ans = 0;
    rep(i ,1, n) ans ^= 1ll * i * (z[i] + 1);
    cout << ans << '\n';
    ans = 0;
    rep(i ,1, m) ans ^= 1ll * i * (p[i] + 1);
    cout << ans << '\n';
    return 0;
}

SA

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++)
#define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i--)
using namespace std;
typedef long long ll;
using VI = vector<int>;
constexpr int N = 1e6 + 5;

string s; 
int sa[N], rk[N], ork[N], buc[N], id[N];
int n;

void work() {
    int m = 1 << 7, p = 0;
    rep(i, 1, n) buc[rk[i] = s[i]]++;
    rep(i, 1, m) buc[i] += buc[i - 1];
    per(i, n, 1) sa[buc[rk[i]]--] = i;
    for(int w = 1 ; ; m = p, p = 0, w <<= 1) {
        rep(i, n - w + 1, n) id[++p] = i;
        rep(i ,1, n) if(sa[i] > w) id[++p] = sa[i] - w;
        memset(buc, 0, m + 1 << 2);
        memcpy(ork, rk, n + 1 << 2) ;
        p = 0;
        rep(i, 1, n) buc[rk[i]]++;
        rep(i, 1, m) buc[i] += buc[i - 1];
        per(i, n, 1) sa[buc[rk[id[i]]]--] = id[i];
        rep(i ,1, n) rk[sa[i]] = ork[sa[i - 1]] == ork[sa[i]] && ork[sa[i - 1] + w] == ork[sa[i] + w] ? p : ++p;
//      rep(i, 1, n) cout << sa[i] << " \n"[i == n]; 
        if(p == n) return ;
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> s; 
    n = s.size(); s = " " + s;
    work();
    rep(i, 1, n) cout << sa[i] << " \n"[i == n];
    return 0;
}

数学

矩阵乘法

struct Mat {
    int n; 
    vector<VI> A;
    vector<int>& operator [](int i)  {return A[i];} 
    const vector<int>& operator [](int i) const { return A[i]; } //在矩阵乘法中放入这两个函数之后，便可以直接通过 `ans[1][5]` 访问数组元素，而不是 `ans.a[1][5]`。
    Mat(int _n) : n(_n) {A.assign(n + 1, VI(n + 1, 0)); }
    const Mat operator*(const Mat &B) const {
        Mat C(n);
        rep(i, 0, n) rep(j, 0, n) 
            rep(k, 0, n) (C[i][j] += (A[i][k] * B[k][j]) % mod) %= mod;
        return C;
    }
};

前缀线性基

struct Line {
    vector<int> a, pos;
    int n;
    Line(int _n) : n(_n), a(_n + 1), pos(_n + 1) {}
    void insert(int x, int it) {
        per(i, n, 0)
         if(x >> i & 1) {
            if(!a[i] ) return a[i] = x, pos[i] = it, void();
            else if(pos[i] < it) swap(pos[i], it), swap(a[i], x) ;
            x ^= a[i];
        }
    }
    int query(int it) {
        int ret = 0;
        per(i, n, 0) if(!(ret >> i & 1) && pos[i] >= it) 
            ret ^= a[i];
        return ret;
    }
};

快速幂

LL qpow(LL x, LL y){
    LL ret=  1;
    for(; y; y >>= 1) {
        if(y & 1) (ret = ret * x) %= mod;
        (x = x * x) %= mod;
    }
    return ret;
}

LL inv(int x) {return qpow(x, mod - 2); }

LL add(const LL x, const LL y) {
    return (x + y + mod) % mod;
} 

LL mul(const LL x, const LL y) {
    return (x * y % mod + mod) % mod;
}

LL fac[N], iv[N];

void init() {
    fac[0] = 1;
    rep(i, 1, N - 1) fac[i] = mul(fac[i - 1], i);
    iv[N - 1] = inv(fac[N - 1]); 
    per(i, N - 2, 0) iv[i] = mul(iv[i + 1], i + 1) ;
}

LL C(int x, int y) {
    if(x < 0 || y < 0 || y - x < 0) return 0;
    return mul(fac[y], mul(iv[x], iv[y - x])) ;
}

评论

  1. GGapa
    博主
    Windows Edge 117.0.2045.41
    4 月前
    2024-6-01 8:27:21

    模板库还能炸？我都不知道她炸了多久了。。。。。。

  4. xyf
    Windows Edge 125.0.0.0
    1 月前
    2024-8-09 19:26:47

    怎么学了这么多！

    • GGapa
      博主
      xyf
      Windows Chrome 127.0.0.0
      1 月前
      2024-8-09 19:56:46

      怎么学了这么多还这么菜o(≧口≦)o

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
P8948 [YsOI2022] NOIp 和省选 题解

							
							

							
做题笔记(CSES)

							
							

							
数论相关知识

							
							

							
矩阵乘法解决图上问题 学习笔记

							
							

							
OI 注意事项、易错点以及一些方法

							
							

							
做题笔记(洛谷)

							
							

							
NOIP2023 模拟赛(2023.11.14)

							
							

							
做题笔记(UVA)

							
							

							
做题笔记(AtCoder)

							
							

							
基数排序