My Algorithm Template

Competetive Programming Code Template in C/C++

杂活

开头

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;

void solve(){
    
    
    
}

int main(){
    
    cin.tie(nullptr)->sync_with_stdio(false);
    
    int _ = 1;
    cin>>_;
    while(_--){
        
        solve();
        
    }
    
    return 0;
}

O1快速乘

1
2
3
4
5
// O1快速乘
inline ll multi(ll x,ll y,ll Mod){
	ll tmp=(x*y-(ll)((long double)x/Mod*y+1.0e-8)*Mod);
	return tmp<0 ? tmp+Mod : tmp;
}

快读&快写

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
// really fast read
inline char _nc(){
    static char buf[100000],*L=buf,*R=buf;
    return L==R&&(R=(L=buf)+fread(buf,1,100000,stdin),L==R)?EOF:*L++;
}
template<class T> void read(T &x) {
    x=0;int f=0;char ch=_nc();
    while(ch<'0'||ch>'9'){f|=(ch=='-');ch=_nc();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=_nc();}
    x=f?-x:x;
    return;
}

// fast read
template<class T> void read(T &x) {
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}

//fast write
template<class T>
inline void write(T x){
	if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}

字符串

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
// KMP algorithm 下标从0开始
vector<int> KMP(string s){
	int len = s.size();
	vector<int> kmp(len);
	for(int j=0,i=1;i<len;++i){
		while(j && s[j]!=s[i]) j = kmp[j-1];
		if(s[j]==s[i]) j++;
		kmp[i] = j;
	}
	return kmp;
}

// KMP algorithm 下标从1开始
vector<int> KMP(string s){
	s = "*" + s;
	int len = s.size();
	vector<int> kmp(len);
	for(int j=0,i=2;i<len;++i){
		while(j && s[j+1]!=s[i]) j = kmp[j];
		if(s[j+1]==s[i]) j++;
		kmp[i] = j;
	}
	return kmp;
}

// Z algorithm 下标从0开始
vector<int> Z_algorithm(string s){
	int len = s.size();
	vector<int> z(len);
	for(int l=0,i=1;i<len;++i){
		if(i<l+z[l]) z[i] = min(z[i-l], l+z[l]-i);
		while(i+z[i]<len && s[z[i]]==s[i+z[i]]) ++z[i];
		if(i+z[i]>l+z[l]) l = i;
	}
	z[0] = len;
	return z;
}

trie

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
77
78
79
80
81
82
83
84
/*

    字典树（前缀树）模板

*/


// 指针版本（动态开点）
class Trie {
public:
    vector<Trie*> child;
    bool isEnd;
    int cnt; // 以当前节点字符为前缀的字符串个数

    Trie() : child(26), isEnd(false), cnt(0) {}

    void insert(string &s) { // 插入一个字符串
        Trie* node = this;
        for (auto &&ch: s) {
            int c = ch - 'a';
            if (!node->child[c]) node->child[c] = new Trie();
            node = node->child[c];
            node->cnt ++;
        }
        node->isEnd = true;
    }

    int query(string &s) {
        Trie* node = this;
        int res = 0;
        for (auto &&ch: s) {
            int c = ch - 'a';
            if(!node->child[c]) break;
            node = node->child[c];
        }
        return node->cnt;
    }
    
};


// 数组版本（记得在堆区创建对象，每次使用前clear()）
struct Trie {
    static constexpr int N = 1000010, M = 26;

    int tot;
    int tr[N][M];
    bool flag[N];
    int cnt[N]; // 以当前节点字符为前缀的字符串个数

    void clear() {
        for(int i = 0; i <= tot; i++)
            memset(tr[i], 0, sizeof tr[i]);

        for(int i = 0; i <= tot; i++)
            flag[i] = cnt[i] = 0;

        tot = 0;
    }

    Trie(): tot(0) {}

    void insert(string &s) { // 插入一个字符串
        int rt = 0;
        for(auto &&ch : s) {
            int id = ch - 'a';
            if(!tr[rt][id]) tr[rt][id] = ++tot;
            rt = tr[rt][id];
            cnt[rt] ++;
        }
        flag[rt] ++;
    }

    int query(string &s) {
        int rt = 0, res = 0;
        for(auto &&ch : s) {
            int id = ch - 'a';
            if (!tr[rt][id]) return 0;
            rt = tr[rt][id];
        }
        return cnt[rt];
    }
}trie;

字符串哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 字符串哈希，查询时下标从 1 开始
struct StrHash{
    using ull = unsigned long long;
    static constexpr int P = 13331;
    static constexpr int N = 1e5+5;
    ull h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

    StrHash(const string &s){
        int n = s.size();
        p[0] = 1;
        for (int i = 1; i <= n; ++ i ){
            h[i] = h[i - 1] * P + s[i - 1];
            p[i] = p[i - 1] * P;
        }
    }

    // 计算子串 str[l ~ r] 的哈希值
    ull get(const int &l, const int &r){
        return h[r] - h[l - 1] * p[r - l + 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
/*
    欧拉筛 求 素数(√）、欧拉函数(√)、莫比乌斯函数(todo)
    time complexity: O(N)
*/
constexpr int N = 1e5;
vector<int> prime, f(N+5), phi(N+5);
static auto init_euler = [] {
    phi[1] = 1;       //欧拉函数：小于等于n的与n互质的正整数个数
    f[0] = f[1] = 1;  // 0：素数，1：合数
    for (int i = 2; i <= N; i++) {
        if (!f[i]) {
            prime.emplace_back(i);
            phi[i] = i - 1;
        }
        for (int j = 0; j < (int)prime.size() && i * prime[j] <= N; ++j) {
            f[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else
                phi[i * prime[j]] = phi[i] * phi[prime[j]];  //积性函数
        }
    }
    return 0;
}();

// get phi[n]: O(sqrt(n))
inline int getphi(int n) {
    int res = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0)
            res = res / i * (i - 1);
        while (n % i == 0)
            n /= i;
    }
    if (n > 1)
        res = res / n * (n - 1);
    return res;
}

扩展欧几里得算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
	扩展欧几里得算法(exgcd)
	用途：
		- 用于求解二元一次不定方程
			a * x + b * y = 1 中的 x, y
		- 用于求解乘法逆元
			a * x ≡ 1 (mod b) <==> a * x + b * y = 1
			解得x即为a的逆元（前提是gcd(a,b)=1)
*/

ll exgcd(ll a,ll b,ll &x,ll &y){ //返回gcd
	if(b == 0) { x = 1; y = 0; return a;}
	ll res = exgcd(b, a % b, x,y);
	ll tx = x; x = y; y = tx - a / b *y ;
	return res;
}

矩阵快速幂

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
/*
    矩阵快速幂
    (a1, a2, ...) * A = (a2, a3, ...)
    or
    A * B^y
*/
template <class T>
struct Matrix {
    vector<vector<T>> mat;
    int sz;
    Matrix(int n): sz(n) {
        mat.resize(n, vector<T>(n));
    }

    Matrix& operator*=(const Matrix& rhs) {
        Matrix<T> res(sz);
        for (int i = 0; i < sz; ++i) {
            for (int j = 0; j < sz; ++j) {
                for (int k = 0; k < sz; ++k) {
                    res.mat[i][j] += mat[i][k] * rhs.mat[k][j];
                }
            }
        }
        *this = std::move(res);
        return *this;
    }
};

template <class T>
Matrix<T> Mqpow(Matrix<T> a, Matrix<T> A, long long y) {
    while (y) {
        if (y & 1) a *= A;
        A *= A;
        y >>= 1;
    }
    return a;
}

图论

链式前向星

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Edge{
	int u,v,w,next;
}e[maxn<<1];
int gcnt,head[maxn];
inline void init_graph(){
	gcnt=0;
	memset(head,-1,sizeof(head));
}
inline void addedge(int u,int v,int w=0){
	e[gcnt]=Edge{u,v,w,head[u]};
	head[u]=gcnt++;
}

并査集

1
2
3
4
5
vector<int> fa(n+1), sz(n+1);
iota(fa.begin(), fa.end(), 0);
function<int(int)> find = [&](int u){
    return x == fa[x] ? fa[x] = find(fa[x]);
};

二分图匹配（匈牙利算法）

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

// 匈牙利算法
int idx = 0;
vector<int> have(n+1), used(n+1);
function<bool(int)> Hungary = [&](int u) {
    for (auto &&v: e[u]) {
        if (used[v] != idx) {
            used[v] = idx;
            if (!have[v] || Hungary(have[v])) {
                have[v] = u;
                return true;
            }
        }
    }
    return false;
};

// 二分图判定
vector<int> colr(n+1);
function<bool(int,int)> isbg = [&](int u, int col) {
    colr[u] = col;
    for (auto &&v: e[u]) {
        if (colr[u] == colr[v]) return false;
        else if (!colr[v] && !isbg(v, 3 - col)) return false;
    }
    return true;
};

二分图最大权匹配（KM算法）

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
const int mxn=411;

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void write(LL x){
    if(x>9)write(x/10);
    putchar(x%10+'0');
    return;
}

inline int mini(int a,int b){return a<b?a:b;}
inline int maxi(int a,int b){return a>b?a:b;}
int nL,nR,bl,br,m;
int visL[mxn],visR[mxn];
int exL[mxn],exR[mxn];
int link[mxn],pre[mxn],lx[mxn];
int slack[mxn];
int mp[mxn][mxn];
//
LL ans=0;
int a[mxn];
int dtime=0;
int q[mxn<<1],hd,tl;
void Aug(int rt){
    if(!rt)return;
    link[rt]=pre[rt];
    Aug(lx[pre[rt]]);
    lx[pre[rt]]=rt;
    return;
}
void BFS(int S){
    int i,j,tmp;++dtime;
    memset(slack,0x3f,sizeof slack);
    hd=tl=1;q[tl]=S;
    while(1){
        while(hd<=tl){
            int u=q[hd];++hd;
            visL[u]=dtime;
            for(int i=1;i<=nR;i++){
                if(visR[i]^dtime){
                    tmp=exL[u]+exR[i]-mp[u][i];
                    if(!tmp){
                        visR[i]=dtime;pre[i]=u;
                        if(!link[i]){
                            Aug(i);
                            return;
                        }
                        q[++tl]=link[i];
                        //
                    }
                    else if(tmp<slack[i])slack[i]=tmp,pre[i]=u;
                }
            }
        }
        tmp=INF;
        for(i=1;i<=nR;i++)if(visR[i]^dtime)tmp=mini(tmp,slack[i]);
        for(i=1;i<=nL;i++){
            if(visL[i]==dtime)exL[i]-=tmp;
            if(visR[i]==dtime)exR[i]+=tmp;
            else slack[i]-=tmp;
        }
        for(i=1;i<=nR;i++){
            if(visR[i]^dtime && !slack[i]){
                visR[i]=dtime;
                if(!link[i]){
//                    link[i]=pre[i];
                    Aug(i);
                    return;
                }
                q[++tl]=link[i];
            }
        }
    }
    return;
}
void KM(){
    for(int i=1;i<=nL;i++){
        exL[i]=0;
        for(int j=1;j<=nR;j++)
            exL[i]=max(exL[i],mp[i][j]);
    }
    for(int i=1;i<=nL;i++) BFS(i);
    ans=0;
    nL=bl;nR=br;
    
    for(int i=1;i<=nR;i++){
        if(mp[link[i]][i]){
            a[link[i]]=i;
            ans+=mp[link[i]][i];
        }
    }
    printf("%lld\n",ans);
    for(int i=1;i<=nL;i++){
        write(a[i]);
        putchar(' ');
    }
    printf("\n");
    return;
}
int main(){
    int i,j;
    nL=read();
    nR=read();
    bl=nL;br=nR;
    nL=max(nL,nR);
    nR=nL;
    m=read();
    int u,v,w;
    for(i=1;i<=m;i++){
        u=read();v=read();w=read();
        mp[u][v]=w;
    }
    KM();
    return 0;
}

树论

倍增LCA

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
/*
        倍增LCA
*/
vector<array<int, 22>> bfa(n + 1);
// vector<array<int,22>> bsum(n+1), bmax(n+1);
vector<int> deep(n + 1);
auto init_beizeng = [&](int root) {
    // init dfs
    auto dfs = [&](auto&& self, int u, int fa, int dep) -> void {
        deep[u] = dep;
        bfa[u][0] = fa;
        for (auto&& v : e[u]) {
            if (v == fa) continue;
            // bsum[v][0]=e[i].w;
            // bmax[v][0]=e[i].w;
            self(self, v, u, dep + 1);
        }
    };
    dfs(dfs, root, 0, 0);

    // dp
    for (int i = 1; (1 << i) <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            bfa[j][i] = bfa[bfa[j][i - 1]][i - 1];
            // bsum[j][i]=bsum[j][i-1]+bsum[bfa[j][i-1]][i-1];
            // bmax[j][i]=max(bmax[j][i-1],bmax[bfa[j][i-1]][i-1]);
        }
    }
};

init_beizeng(s);

// LCA
auto LCA = [&](int x, int y) {
    if (deep[x] < deep[y]) swap(x, y);
    // int Sum = 0, Max = -1;
    while (deep[x] > deep[y]) {
        // Sum += bsum[x][int(log2(deep[x]-deep[y]))];
        // Max = max(Max, bmax[x][int(log2(deep[x]-deep[y]))]);
        x = bfa[x][int(log2(deep[x] - deep[y]))];
    }
    if (x == y) return x;
    for (int i = log2(deep[x]); i >= 0; i--) {
        if (bfa[x][i] != bfa[y][i]) {
            x = bfa[x][i], y = bfa[y][i];
        }
    }
    return bfa[x][0];
};

树链剖分

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
/*

    重链剖分
        - 用处：维护树上操作，通常结合线段树等
        - 原理：一棵树被完全剖分成若干重链，任意两点间的链个数小于等于 log2(两点间距离)

    trick:
        1. 边权转点权：
            - 构造时 U = pii
            - 需要修改csdfs1中的遍历参数 v->[w, v], 以及 添加 边权转点权操作（用csw维护）
            - 对树上route操作时，在最后 x,y 处在同一条重链上时，需要判x,y是否重合
            如果是则不做操作(因为LCA的权值代表其父节点边权)
            否则只处理[csid[x]+1, csid[y]]这个区间

                 x(y)              x
                /   \             / \
              ...   ...         ...  .
                                      \
                                       y
                                        \
                                        ...

    注：
        - 此代码默认所有下标从 1 开始

*/

// 重链剖分模板 <权值类型, 树边类型>
template <class T, class U>
class TreeChain {
public:

    int n, root;          // 树节点个数, 根节点
    vector<vector<U>> e;  // 树边
    int dfsx = 0;         // dfs序总数

    // 每个节点对应的dfs序、深度、子树大小、父节点、重儿子、重链顶
    vector<int> csid, csdep, cssize, csfa, csson, cstop;
    
    // 需要维护的值(以节点为下标，动态开点不需要)
    vector<T> a;

    // 需要维护的值(以dfs序为下标，动态开点不需要)
    vector<T> csw;

    // 线段树(多棵请使用vector包装)
    // 若动态开点，则自行在外部实现初始化逻辑
    SegTree<T> Seg;

    // 第一次dfs：处理出 深度、父亲、子树大小、重儿子
    void csdfs1(int u, int fath, int depth) {
        csdep[u] = depth;
        csfa[u] = fath;
        cssize[u] = 1;
        for (auto&& v : e[u]) {
            if (v == fath)
                continue;

            /* 边权转点权 */
            // csw[v] = w;

            csdfs1(v, u, depth + 1);
            cssize[u] += cssize[v];
            if (cssize[v] > cssize[csson[u]])
                csson[u] = v;
        }
    }

    // 第二次dfs：求出 dfs序、dfs序对应初始值、节点所在链的顶端
    void csdfs2(int u, int topf) {
        csid[u] = ++dfsx;

        /* 需要维护的值(动态开点不需要) */
        csw[dfsx] = a[u];

        cstop[u] = topf;
        if (!csson[u])
            return;
        csdfs2(csson[u], topf);  // 先搞重儿子所在链
        for (auto&& v : e[u]) {
            if (v == csfa[u] || v == csson[u])
                continue;
            csdfs2(v, v);  // 再搞轻儿子所在链
        }
    }

    // 构造函数 + 初始化
    // 节点数、根节点、边、需要维护的权值
    TreeChain(int _n, int _root, const vector<vector<U>> &_e, const vector<T> &_a)
        : n(_n), root(_root), e(_e), a(_a) {

        csid.resize(n+1);
        csdep.resize(n+1);
        cssize.resize(n+1);
        csfa.resize(n+1);
        csson.resize(n+1);
        cstop.resize(n+1);

        a.resize(n+1);
        csw.resize(n+1);

        csdfs1(root, -1, 1);
        csdfs2(root, root);

        Seg.RESIZE(n);
        Seg.build(1, 1, n, csw);
    }

    // get LCA
    int LCA(int x, int y) {
        while (cstop[x] != cstop[y]) {
            if (csdep[cstop[x]] < csdep[cstop[y]])
                swap(x, y);
            x = csfa[cstop[x]];
        }
        return csdep[x] < csdep[y] ? x : y;
    };


    // 把节点x权值改为k
    void changepoint(int x, T k){
        Seg.change_point(1, 1, n, csid[x], k);
    }

    // [x,y] 路径上点权值 + k
    void addroute(int x, int y, T k) {
        while (cstop[x] != cstop[y]) {              // 如果不属于同一条重链
            if (csdep[cstop[x]] < csdep[cstop[y]])  // 设x所在链头部较深
                swap(x, y);
            Seg.add_range(1, 1, n, csid[cstop[x]], csid[x], k);
            x = csfa[cstop[x]];  // x跳到所在链头部的父节点上，继续下去
        }
        // 直到x、y在同一重链上
        if (csdep[x] > csdep[y])
            swap(x, y);                             // 设x较浅
        Seg.add_range(1, 1, n, csid[x], csid[y], k);  // 对重链对应区间更新
    }

    // 求 [x, y] 路径上点最大权值
    T getroutemax(int x,int y){
        T res = LLONG_MIN;
        while (cstop[x] != cstop[y]) {
            if (csdep[cstop[x]] < csdep[cstop[y]])
                swap(x, y);
            res = max(res, Seg.getmax(1, 1, n, csid[cstop[x]], csid[x]));
            x = csfa[cstop[x]];
        }
        if (csdep[x] > csdep[y])
            swap(x, y);
        res = max(res, Seg.getmax(1, 1, n, csid[x], csid[y]));
        return res;
    }

    // 求 [x, y] 路径上点权值和
    T getroutesum(int x, int y) {
        T res = 0;
        while (cstop[x] != cstop[y]) {
            if (csdep[cstop[x]] < csdep[cstop[y]])
                swap(x, y);
            res += Seg.getsum(1, 1, n, csid[cstop[x]], csid[x]);
            x = csfa[cstop[x]];
        }
        if (csdep[x] > csdep[y])
            swap(x, y);
        res += Seg.getsum(1, 1, n, csid[x], csid[y]);
        return res;
    }

    // 以x为根的子树权值 + k
    void addroot(int x, T k){
        Seg.add_range(1, 1, n, csid[x], csid[x] + cssize[x] - 1, k);
    }

    // 求以x为根的子树权值和
    T getrootsum(int x){
        return Seg.getsum(1, 1, n, csid[x], csid[x] + cssize[x] - 1);
    }

};

/*----------------------------------------------------------*/

区间操作&RMQ

ST表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// ST表 O(nlogn)预处理，O(1)查询静态区间最值
vector<vector<int>> ST(n+2, vector<int>(23, 0));
auto init_st = [&]() -> void{ //st init
	for(int i=1;i<=n;i++) ST[i][0]=a[i];
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<(j-1))-1<=n;i++){
			ST[i][j]=max(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
		}
	}
};
init_st();
auto query = [&](int l,int r) -> int{ //查询l,r最值
	int len=log2(r-l+1);
	return max(ST[l][len],ST[r-(1<<len)+1][len]);
};

树状数组

1
2
3
4
5
6
7
8
9
10
ll c[maxn];
inline int lowbit(int x){return x&-x;}
inline void add(int i,ll k){
    while(i<=n) c[i]+=k,i+=lowbit(i);
}
inline ll getsum(int i){
    ll res=0;
    while(i>0) res+=c[pos],i-=lowbit(i);
    return res;
}

线段树

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
/*
    线段树 Segment Tree（支持动态开点）
    
    支持常规操作：
        1. 单点修改
        2. 区间加
        3. 区间求和
        4. 区间最值（最大/最小）
        5. 区间查找 <= k 的第一个数的下标（树上二分）
    
    根节点：均为 1
    使用方式：
        - 非动态开点：
            SegTree<int> Seg(n); // 开1个普通线段树
            Seg.build(1, 1, n, a); // 以vector a为初值建树，表示[1,n]区间
        - 动态开点：
            开启 #define DYNAMIC
            SegTree<int> Seg; // 开一个动态开点线段树
            SegTree<int> Seg(n); // 开n个动态开点线段树，下标 1 ~ n（用同一个vector<Node>表示，线段树合并时使用）
            SegTree<int> Seg[n]; // 开n个动态开点线段树（不需要合并时也可以这么用）
*/


// #define DYNAMIC // 是否开启动态开点
template<class T>
class SegTree {
public:
    static constexpr T T_MIN = numeric_limits<T>::lowest();
    static constexpr T T_MAX = numeric_limits<T>::max();

    struct Node {
        T val, maxh, tg;
        #ifdef DYNAMIC
            int ls, rs;
        #endif
        Node(): val(0), maxh(0), tg(0) {
            #ifdef DYNAMIC
                ls = 0, rs = 0;
            #endif
        }
    };

    #ifdef DYNAMIC
        #define ls (tr[i].ls)
        #define rs (tr[i].rs)
        int tcnt; // 动态节点数
    #else
        #define ls (i<<1)
        #define rs (i<<1|1)
    #endif

    vector<Node> tr;

    void push_down(int i, int l, int r) {
        #ifdef DYNAMIC
            if(!ls) ls = ++tcnt, tr.emplace_back(Node{});
            if(!rs) rs = ++tcnt, tr.emplace_back(Node{});
        #endif
        if (!tr[i].tg) return;
        T k = tr[i].tg;
        int mid = (l + r) >> 1;
        tr[ls].val += k * (mid - l + 1);
        tr[rs].val += k * (r - mid);
        tr[ls].maxh += k;
        tr[rs].maxh += k;
        tr[ls].tg += k;
        tr[rs].tg += k;
        tr[i].tg = 0;
    }
    void push_up(int i) {
        tr[i].val = tr[ls].val + tr[rs].val;
        tr[i].maxh = max(tr[ls].maxh, tr[rs].maxh);
    }


    /* 构造与初始化 */
    #ifdef DYNAMIC
        SegTree(): tcnt(1), tr(2) {}
        // 开N棵动态开点线段树，根节点分别为 1 ~ N（用于线段树合并）
        SegTree(const int &N): tcnt(N), tr(N+1) {}

        // 线段树合并：将b为根的树合并到a为根的树上
        int merge(int a, int b, int l, int r){
            if(!a) return b;
            if(!b) return a;
            if(l == r){
                /* 合并信息操作 */
                return a;
            }
            int mid = (l + r) >> 1;
            tr[a].LS = merge(tr[a].LS, tr[b].LS, l, mid);
            tr[a].RS = merge(tr[a].RS, tr[b].RS, mid + 1, r);
            push_up(a);
            return a;
        }
    #else
        // 初值初始化
        void build(int i,int l,int r,const vector<T> &a){
            if(l==r){
                tr[i].val = a[l];
                tr[i].maxh = a[l];
                return;
            }
            int mid = (l + r) >> 1;
            build(ls, l, mid, a);
            build(rs, mid+1, r, a);
            push_up(i);
        }

        void RESIZE(const int &N) { tr.resize(N<<2); }
        SegTree() = default;
        SegTree(const int &N): tr(N<<2) {}
        SegTree(const int &N, const vector<T> &a): tr(N<<2) { build(1, 1, N, a); }
    #endif
    /* 构造与初始化 */


    // 单点修改
    void change_point(int i, int l, int r, int pos, T k) {
        if (l == r) {
            tr[i].val = k;
            tr[i].maxh = k;
            return;
        }
        push_down(i, l, r);
        int mid = (l + r) >> 1;
        if (pos <= mid) change_point(ls, l, mid, pos, k);
        else change_point(rs, mid+1, r, pos, k);
        push_up(i);
    }

    // 区间加
    void add_range(int i, int l, int r, int L, int R, T k) {
        if (l >= L && r <= R) {
            tr[i].tg += k;
            tr[i].maxh += k;
            tr[i].val += k * (r - l + 1);
            return;
        }
        push_down(i, l, r);
        int mid = (l + r) >> 1;
        if (mid >= L) add_range(ls, l, mid, L, R, k);
        if (mid+1 <= R) add_range(rs, mid+1, r, L, R, k);
        push_up(i);
    }

    // 区间求max/min
    T getmax(int i, int l, int r, int L, int R){
        if(l >= L && r <= R) return tr[i].maxh;
        push_down(i, l, r);
        int mid = (l + r) >> 1;
        T ret = T_MIN;
        if(mid >= L) ret = max(ret, getmax(ls, l, mid, L, R));
        if(mid + 1 <= R) ret = max(ret, getmax(rs, mid+1, r, L, R));
        return ret;
    }

    // 区间求和
    T getsum(int i, int l, int r, int L, int R) {
        if (l >= L && r <= R) return tr[i].val;
        push_down(i, l, r);
        int mid = (l + r) >> 1;
        T ret = 0;
        if (mid >= L) ret += getsum(ls, l, mid, L, R);
        if (mid+1 <= R) ret += getsum(rs, mid+1, r, L, R);
        return ret;
    }
    
    // 在[L,R]内查找小于等于k的第一个数的下标（不存在返回-1）
    int getleft_idx(int i, int l, int r, int L, int R, T k){
        if(tr[i].maxh < k) return -1;
        if(l == r) return l;
        push_down(i, l, r);
        int mid = (l + r) >> 1;
        if(mid >= R) return getleft_idx(ls, l, mid, L, R, k);
        else if(mid+1 <= L) return getleft_idx(rs, mid+1, r, L, R , k);
        else{
            int left = getleft_idx(ls, l, mid, L, R, k);
            if(left != -1) return left;
            int right = getleft_idx(rs, mid+1, r, L, R, k);
            if(right != -1) return right;
            return -1;
        }
    }

};
////////////////////////////////////////////////////////

珂朵莉树ODT

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
/*
	珂朵莉树

	重点：在数据随机时复杂度才有效

	用处：用于 包含 给一段区间赋相同值 在内的 区间操作
	原理：std::set 暴力分块处理

	模板题：https://www.luogu.com.cn/problem/CF896C
*/


#define IT set<odtnode>::iterator
struct odtnode
{
	int l,r;
	mutable ll v;
	odtnode(int L,int R=-1,ll V=0):l(L),r(R),v(V){}
	bool operator <(const odtnode& rhs)const{
		return l<rhs.l;
	}
};
set<odtnode> odt;

inline IT split(int pos){
	IT it=odt.lower_bound(odtnode(pos));
	if(it!=odt.end()&&it->l==pos) return it;
	it--;
	int l=it->l,r=it->r;
	ll v=it->v;
	odt.erase(it);
	odt.insert(odtnode(l,pos-1,v));
	return odt.insert(odtnode(pos,r,v)).first;
}

// Assign to same value
inline void assign(int l,int r,ll k){
	IT itr=split(r+1),itl=split(l);
	odt.erase(itl,itr);
	odt.insert(odtnode(l,r,k));
}


// [l,r] + k
inline void add(int l,int r,ll k){
	IT itr=split(r+1),itl=split(l);
	for(;itl!=itr;itl++) itl->v+=k;
}

// kth small
inline ll kths(int l,int r,int k){
	IT itr=split(r+1),itl=split(l);
	vector<pair<ll,int>> vec;
	vec.clear();
	for(;itl!=itr;itl++){
		vec.push_back(pair<ll,int>(itl->v,itl->r-itl->l+1));
	}
	sort(vec.begin(),vec.end());
	for(vector<pair<ll,int>>::iterator it=vec.begin();it!=vec.end();it++){
		k-=it->second;
		if(k<=0) return it->first;
	}
	return -1ll;
}

// x pow sum mod y
inline ll xpowsum(int l,int r,ll x,ll y){
	IT itr=split(r+1),itl=split(l);
	ll res=0;
	for(;itl!=itr;itl++){
		res=((res+(itl->r-itl->l+1)*qpow(itl->v,x,y)%y)%y+y)%y;
	}
	return res;
}

计算几何

判断两线段是否相交

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
// 点结构体
struct Point
{
    double x,y;
};
// 线段结构体
struct Line
{
    Point ps,pe;
};

// 求叉积：CA x CB
inline double mult(Point c,Point a,Point b){return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);}

// 判断 AB和CD 是否有交点
inline bool intersect(Point a,Point b,Point c,Point d){
    //判投影
    if(max(a.x,b.x)<min(c.x,d.x)) return false;
    if(max(a.y,b.y)<min(c.y,d.y)) return false;
    if(max(c.x,d.x)<min(a.x,b.x)) return false;
    if(max(c.y,d.y)<min(a.y,b.y)) return false;
    //判叉积
    if(mult(a,c,b)*mult(a,b,d)<0) return false;
    if(mult(c,a,d)*mult(c,d,b)<0) return false;
    return true;
}
算法
代码模板

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！