算法竞赛模板

这里记录了我经常使用的算法竞赛的板子。

在 C++17 以及以上的高版本 C++ 中，模板类拥有自动类型推断。比如下文中的 ST<T> ，只要你传入了 vector<long long>& a，T 就等于 long long，无需手动指定。

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 1-indexed
// dsu[p] as query
struct dsu {
    int tot;
    vector<int> pa, size;
    dsu(int n) : pa(n+1), size(n+1, 1), tot(n) {
        iota(pa.begin(),pa.end(),0);
        size[0]=0;
    }
    
    int find(int x) { return pa[x]==x? x : pa[x]=find(pa[x]) ;}
    int operator[](int x) {return find(x);}
    
    void unite(int x, int y) {
        x=find(x),y=find(y);
        if (x==y) return;
        tot--;
        if (size[x]<size[y]) swap(x,y);
        pa[y]=x;
        size[x]+=size[y];
    }
};

ST 表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 1-indexed
// st(l,r) as query
template<typename T=int>
struct ST {
    int n;
    vector<vector<T>> st;
    vector<int> lg;
    ST(vector<T>& a): n(a.size()-1), lg(a.size()){
        lg[0]=lg[1]=0;
        for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
        st.resize(lg[n]+1);
        for (int i=0;i<=lg[n];i++) st[i].resize(a.size());
        for (int i=1;i<=n;i++) st[0][i]=a[i];
        for (int i=1;i<=lg[n];i++){
            for (int j=0;j+(1<<i)-1<=n;j++){
                st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
            }
        }
    }
    
    T query(int l,int r){
        int p=lg[r-l+1];
        return max(st[p][l],st[p][r-(1<<p)+1]);
    }
    T operator()(int l,int r){
        return query(l,r);
    }
};

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 1-indexed
// fenwick[p] as prefix query
// fenwick(l,r) as range sum query (not work if modified for RMQ)
template<typename T=int>
struct fenwick {
    int n;
    vector<T> t;
    fenwick(int _n): n(_n), t(_n+1){}
    fenwick(vector<T>& a): n(a.size()-1), t(a.size()){
        for (int i=1;i<=n;i++){
            t[i]+=a[i];
            if (i+(i&(-i))<=n){
                t[i+(i&(-i))]+=t[i];
            }
        }
    }
    
    T query(int p){
        T res=T{};
        while(p){
            res+=t[p];
            p-=(p&(-p));
        }
        return res;
    }
    T operator[](int p){
        return query(p);
    }
    T operator()(int l,int r){
        if (l>r) swap(l,r);
        return query(r)-query(l-1);
    }
    
    void add(int p,T x){
        while(p<=n){
            t[p]+=x;
            p+=(p&(-p));
        }
    }
};

区间加线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// 0-indexed
// segtree(l,r) as range query
template <typename T=int>
struct segtree {
    vector<T> tree, lazy;
    int n;
    void push(int cl, int cr, int p) {
        int cm = cl + (cr - cl) / 2;
        if (cl != cr && lazy[p]) {
            lazy[p * 2] += lazy[p];
            lazy[p * 2 + 1] += lazy[p];
            tree[p * 2] += lazy[p] * (cm - cl + 1);
            tree[p * 2 + 1] += lazy[p] * (cr - cm);
            lazy[p] = 0;
        }
    }
    T query(int l, int r, int cl, int cr, int p) {
        if (l <= cl && cr <= r) return tree[p];
        int m = cl + (cr - cl) / 2;
        T sum = T{};
        push(cl, cr, p);
        if (l <= m) sum += query(l, r, cl, m, p * 2);
        if (r > m) sum += query(l, r, m + 1, cr, p * 2 + 1);
        return sum;
    }

    void add(int l, int r, T val, int cl, int cr, int p) {
        if (l <= cl && cr <= r) {
            lazy[p] += val;
            tree[p] += (cr - cl + 1) * val;
            return;
        }
        int m = cl + (cr - cl) / 2;
        push(cl, cr, p);
        if (l <= m) add(l, r, val, cl, m, p * 2);
        if (r > m) add(l, r, val, m + 1, cr, p * 2 + 1);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }

    void build(int s, int t, int p, vector<T> &arr) {
        if (s == t) {
            tree[p] = arr[s];
            return;
        }
        int m = s + (t - s) / 2;
        build(s, m, p * 2, arr);
        build(m + 1, t, p * 2 + 1, arr);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }
    
    void build(int s, int t, int p, T init) {
        if (s == t) {
            tree[p] = init;
            return;
        }
        int m = s + (t - s) / 2;
        build(s, m, p * 2, init);
        build(m + 1, t, p * 2 + 1, init);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }

    segtree(vector<T> &arr): n(arr.size()), tree(arr.size()<<2), lazy(arr.size()<<2) {
        build(0, n-1, 1, arr);
    }
    segtree(int _n,T init): n(_n), tree(_n<<2), lazy(_n<<2) {
        build(0, n-1, 1, init);
    }
    T query(int l, int r) { return query(l, r, 0, n-1, 1); }
    T operator()(int l,int r){ return query(l,r);}
    void add(int l, int r, T val) { add(l, r, val, 0, n-1, 1); }
};

区间推平线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// 0-indexed
// segtree(l,r) as range query
template <typename T=int>
struct segtree {
    vector<T> tree, lazy;
    vector<bool> if_lazy;
    int n;
    void push(int cl, int cr, int p) {
        int cm = cl + (cr - cl) / 2;
        if (cl != cr && if_lazy[p]) {
            lazy[p * 2] = lazy[p],if_lazy[p*2] = 1;
            lazy[p * 2 + 1] = lazy[p],if_lazy[p*2+1] = 1;
            tree[p * 2] = lazy[p] * (cm - cl + 1);
            tree[p * 2 + 1] = lazy[p] * (cr - cm);
            lazy[p] = 0;
            if_lazy[p] = 0;
        }
    }

    T query(int l, int r, int cl, int cr, int p) {
        if (l <= cl && cr <= r) return tree[p];
        int m = cl + (cr - cl) / 2;
        T sum = T{};
        push(cl, cr, p);
        if (l <= m) sum += query(l, r, cl, m, p * 2);
        if (r > m) sum += query(l, r, m + 1, cr, p * 2 + 1);
        return sum;
    }

    void modify(int l, int r, T val, int cl, int cr, int p) {
        if (l <= cl && cr <= r) {
            lazy[p] = val;
            if_lazy[p] = 1;
            tree[p] = (cr - cl + 1) * val;
            return;
        }
        int m = cl + (cr - cl) / 2;
        push(cl, cr, p);
        if (l <= m) modify(l, r, val, cl, m, p * 2);
        if (r > m) modify(l, r, val, m + 1, cr, p * 2 + 1);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }

    void build(int s, int t, int p, vector<T> &arr) {
        if (s == t) {
            tree[p] = arr[s];
            return;
        }
        int m = s + (t - s) / 2;
        build(s, m, p * 2, arr);
        build(m + 1, t, p * 2 + 1, arr);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }
    
    void build(int s, int t, int p, T init) {
        if (s == t) {
            tree[p] = init;
            return;
        }
        int m = s + (t - s) / 2;
        build(s, m, p * 2, init);
        build(m + 1, t, p * 2 + 1, init);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }

    segtree(vector<T> &arr): n(arr.size()), tree(arr.size()<<2), lazy(arr.size()<<2), if_lazy((arr.size()<<2),0) {
        build(0, n-1, 1, arr);
    }
    segtree(int _n,T init): n(_n), tree(_n<<2), lazy(_n<<2), if_lazy((_n<<2),0) {
        build(0, n-1, 1, init);
    }

    T query(int l, int r) { return query(l, r, 0, n-1, 1); }
    T operator()(int l,int r){ return query(l,r);}
    void modify(int l, int r, T val) { modify(l, r, val, 0, n-1, 1); }
};

单点修改线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// 0-indexed
// segtree(l,r) as range query
template <typename T=int>
struct segtree {
    vector<T> tree;
    int n;
    T query(int l, int r, int cl, int cr, int p) {
        if (l <= cl && cr <= r) return tree[p];
        int m = cl + (cr - cl) / 2;
        T sum = T{};
        if (l <= m) sum += query(l, r, cl, m, p * 2);
        if (r > m) sum += query(l, r, m + 1, cr, p * 2 + 1);
        return sum;
    }

    void add(int idx, T val, int cl, int cr, int p) {
        if (cl == cr && cr == idx) {
            tree[p] += val;
            return;
        }
        int m = cl + (cr - cl) / 2;
        if (idx <= m) add(idx, val, cl, m, p * 2);
        if (idx > m) add(idx, val, m + 1, cr, p * 2 + 1);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }

    void modify(int idx, T val, int cl, int cr, int p) {
        if (cl == cr && cr == idx) {
            tree[p] = val;
            return;
        }
        int m = cl + (cr - cl) / 2;
        if (idx <= m) modify(idx, val, cl, m, p * 2);
        if (idx > m) modify(idx, val, m + 1, cr, p * 2 + 1);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }

    void build(int s, int t, int p, vector<T> &arr) {
        if (s == t) {
            tree[p] = arr[s];
            return;
        }
        int m = s + (t - s) / 2;
        build(s, m, p * 2, arr);
        build(m + 1, t, p * 2 + 1, arr);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }
    
    void build(int s, int t, int p, T init) {
        if (s == t) {
            tree[p] = init;
            return;
        }
        int m = s + (t - s) / 2;
        build(s, m, p * 2, init);
        build(m + 1, t, p * 2 + 1, init);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }

    segtree(vector<T> &arr): n(arr.size()), tree(arr.size()<<2) {
        build(0, n-1, 1, arr);
    }
    segtree(int _n,T init): n(_n), tree(_n<<2) {
        build(0, n-1, 1, init);
    }
    T query(int l, int r) { return query(l, r, 0, n-1, 1); }
    T operator()(int l,int r){ return query(l,r);}
    void add(int idx, T val) { add(idx, val, 0, n-1, 1); }
    void modify(int idx, T val) { modify(idx, val, 0, n-1, 1); }
};

Lucas 定理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// lucas(a,b) as query
template<typename T=long long>
struct lucas
{
    vector<T>fa,inv;
    T p;
    lucas(T _p): p(_p), fa(_p), inv(_p){
        fa[0]=inv[0]=1;
        for (T i=1;i<p;i++){
            fa[i]=fa[i-1]*i%p;
            inv[i]=qpow(fa[i],p-2);
        }
    }
    T qpow(T a,T b){
        T res=1;
        while(b){
                if (b&1) res=res*a%p;
                a=a*a%p;
                b>>=1;
        }
        return res;
    }
    T c(T a,T b){
        if (b>a) return 0;
        return fa[a]*inv[a-b]%p*inv[b]%p;
    }
    T get(T a,T b){
        if (not b) return 1;
        return get(a/p,b/p)*c(a%p,b%p)%p;
    }
    T operator()(T a,T b){ return get(a,b); }
};

Manacher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct Manacher {
    vector<int>p;
    int n;
    Manacher(string &_s): n(_s.size()*2+2), p(_s.size()*2+2,1) {
        string s="$|";
        s.reserve(n);
        for (auto&&c:_s){
            s+=c;
            s+='|';
        }
        for (int t=1,r=0,mid=0;t<n;t++){
            if (t<=r) p[t]=min(p[mid*2-t],r-t+1);
            while (p[t]<=t and t+p[t]<n and s[t-p[t]]==s[t+p[t]]) p[t]++;
            if (p[t]+t>r) r=p[t]+t-1,mid=t;
        }
    }
    bool query(int l,int r){
        // 1-indexed
        l=l*2,r=r*2;
        int mid=(l+r)/2;
        return p[mid]>=(r-mid+1);
    }
    bool operator()(int l,int r){ return query(l,r); }
    int operator[](int i){ return p[i]; }
};

预处理的 KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
struct KMP {
    vector<vector<int>>nxt;
    int n,st,ed;
    KMP(string &p,int _st='a',int _ed='z'): n(p.size()), st(_st), ed(_ed), nxt(_ed-_st+1,vector(p.size(),0)) {
        int pre=0;
        nxt[p[0]-st][0]=1;
        for (int i=1;i<n;i++){
            for (int j=st;j<=ed;j++){
                if (j==p[i])
                    nxt[j-st][i]=i+1;
                else
                    nxt[j-st][i]=nxt[j-st][pre];
            }
            pre=nxt[p[i]-st][pre];
        }
    }
    int find_first(string &s){
        int cur=0;
        for (int i=0;i<s.length();i++){
            cur=nxt[s[i]-st][cur];
            if (cur==n)
                return i-n+1;
        }
        return -1;
    }
    int find_largest(string &s){
        int cur=0,ret=0;
        for (int i=0;i<s.length();i++){
            cur=nxt[s[i]-st][cur];
            if (cur==n)
                return n;
            if (cur>ret)
                ret=cur;
        }
        return ret;
    }
};

Z 函数 / 扩展 KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct exKMP {
    vector<int>z;
    int n;
    exKMP(string &p): n(p.size()), z(p.size()) {
        int l=0;
        for (int i=1;i<n;i++){
            if (l+z[l]>i) z[i]=min(z[i-l],l+z[l]-i);
            while (i+z[i]<n and p[z[i]]==p[i+z[i]]) z[i]++;
            if (i+z[i]>l+z[l]) l=i;
        }
    }
    int query(int i){ return (i==0?n:z[i]); }
    int operator[](int i){ return query(i); }
};

MillerRabin 快速质数判定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
template<typename T=__int128>
struct MillerRabin{
	vector<T> p{2,3,5,7,11,13,17,19,23,29,31,37};
	MillerRabin (){}
	T qpow(T a,T b,T p){
        T res=1;
        while(b){
                if (b&1) res=res*a%p;
                a=a*a%p;
                b>>=1;
        }
        return res;
    }
	bool check(T x){
		if (x<=37){
			for (auto&&i:p) if (i==x) return 1;
			return 0;
		}
		T u=x-1,t=0;
		while (not (u&1))
			(u>>=1),t++;
		for (auto&&i:p){
			T v=qpow(i,u,x);
			if (v==1) continue;
			T s=0;
			for (;s<t;s++){
				if (v==x-1) break;
				v=(v*v)%x;
			}
			if (s==t) return 0;
		}
		return 1;
	}
	bool operator()(T x){ return check(x); }
};
avatar
Alicy Xu
LOLI 控会梦到 AK Leetcode 周赛
文章
8
标签
17
分类
0
Codeforces 关注我
公告
Ciallo World!
最新文章
2025 牛客寒假算法基础集训营 2 个人题解
2025 牛客寒假算法基础集训营 1 个人题解
逆元的计算 / Python 自带的逆元
JQDataSDK Python 基金数据查询
跳跃次数查询 根号分治
标签
sort data structure simulate api combination greedy leetcode sliding window inversion discrete python fenwick dfs string trisection divide math
归档
网站信息
文章数目 :
8
本站访客数 :
本站总浏览量 :
最后更新时间 :