首页 algorithm 算法汇总

# 数据结构

# ST 表

一般用于解决 RMQ 问题。基于倍增和动态规划的思想，预处理的时间复杂度为 O(Nlog2N)O(Nlog2N)，根据查询数据性质的不同，可以在 O(log2N)O(log2N) 甚至 O(1)O(1) 的时间复杂度内回答每个询问。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
29
30
31
class ST
{
private:
	vector<vector<int>> st;
	vector<int> log;//用于预处理log2 
public:	
	ST(const vector<int>& v)
	{
		int n = v.size();
		
		//预处理log2 
		log.resize(n + 1);
		log[1] = 0;
		for(int i = 2; i <= n; i++) log[i] = log[i / 2] + 1;
		int maxlog = log[n] + 1;
		
		//初始化st 
		st.resize(n, vector<int>(maxlog));
		for(int i = 0; i < n; i++) st[i][0] = v[i];//最大值是自己
		for(int j = 1; j < maxlog; j++)
			for(int i = 0; i + (1 << j) - 1 < n; i++)
				st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);	
	}
		
	//询问 
	int query(int l, int r)
	{
		int j = log[r - l + 1];
		return max(st[l][j], st[r - (1 << j) + 1][j]);
	}
};

# 树状数组

主要用于前缀和查询和单点更新

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
class FenwickTree//树状数组，tree的索引从1开始 
{
private:
	 vector<int> tree;
	 int n;
public:
	FenwickTree(int size) : n(size), tree(size + 2, 0) {}
	void add(int x, int k = 1)
	{
		while(x <= n)
		{
			tree[x] += k;
			x += x & -x;
		}
	}	
	int ask(int x)
	{
		int sum = 0;
		while(x)
		{
			sum += tree[x];
			x -= x & -x;
		}
		return sum;
	}
}; 
//初始化
FenwickTree ft(N);//N表示a[i]的最大取值

# 线段树

# 区间求最大值

区间修改，区间查询（有懒标记）

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
class SegmentTree//数组下标从0开始 
{
private:
	vector<int> tree;
	vector<int> lazy;
	int n;
	
	void build(const vector<int>& nums, int u, int s, int e)
	{
		if(s == e) tree[u] = nums[s];
		else
		{
			int mid = (s + e) >> 1;
			build(nums, u * 2 + 1, s, mid);
			build(nums, u * 2 + 2, mid + 1, e);
			tree[u] = max(tree[u * 2 + 1], tree[u * 2 + 2]);
		}
	}
	
	void pushdown(int u)
	{
		if(lazy[u] != INT_MIN)
		{
			tree[2 * u + 1] = lazy[u];
			lazy[2 * u + 1] = lazy[u];
			tree[2 * u + 2] = lazy[u];
			lazy[2 * u + 2] = lazy[u];
			lazy[u] = INT_MIN;
		}
	}
	
	void updateRange(int u, int s, int e, int l, int r, int val)
	{
		if(l > e || r < s) return;
		if(l <= s && r >= e)
		{
			tree[u] = val;
			lazy[u] = val;
			return;
		}
		pushdown(u);
		int mid = (s + e) >> 1;
		updateRange(2 * u + 1, s, mid, l, r, val);
		updateRange(2 * u + 2, mid + 1, e, l, r, val);
		tree[u] = max(tree[2 * u + 1], tree[2 * u + 2]);
	}
	
	int queryRange(int u, int s, int e, int l, int r)
	{
		if(l > e || r < s) return INT_MIN;
		if(l <= s && r >= e) return tree[u];
		pushdown(u);
		int mid = (s + e) >> 1;
		int left = queryRange(2 * u + 1, s, mid, l, r);
		int right = queryRange(2 * u + 2, mid + 1, e, l, r);
		return max(left, right); 
	}
public:
	SegmentTree(const vector<int>& nums)
	{
		n = nums.size();
		tree.resize(4 * n, INT_MIN);
		lazy.resize(4 * n, INT_MIN);
		build(nums, 0, 0, n - 1);
	}
	void update(int l, int r, int val)
	{
		updateRange(0, 0, n - 1, l, r, val);
	}
	int query(int l, int r)
	{
		return queryRange(0, 0, n - 1, 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
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
class SegmentTree
{
private:
	struct Node
	{
		int sum, tmax, lmax, rmax;	
	};
	vector<Node> tree;
	int n;
	
	Node merge(const Node& l, const Node& r)
	{
		Node t;
		t.sum = l.sum + r.sum;
		t.lmax = max(l.lmax, l.sum + r.lmax);
		t.rmax = max(r.rmax, r.sum + l.rmax);
		t.tmax = max({l.tmax, r.tmax, l.rmax + r.lmax});
		return t;
	}
	
	void build(const vector<int>& nums, int u, int s, int e)
	{
		if(s == e) tree[u] = {nums[s], nums[s], nums[s], nums[s]};
		else
		{
			int mid = (s + e) >> 1;
			build(nums, u * 2 + 1, s, mid);
			build(nums, u * 2 + 2, mid + 1, e);
			tree[u] = merge(tree[u * 2 + 1], tree[u * 2 + 2]);
		}
	}
	
	//单点修改 
	void updateRange(int u, int s, int e, int idx, int val)
	{
		if(s == e) tree[u] = {val, val, val, val};
		else
		{
			int mid = (s + e) >> 1;
			if(idx <= mid)
				updateRange(u * 2 + 1, s, mid, idx, val);
			else 
				updateRange(u * 2 + 2, mid + 1, e, idx, val);
			tree[u] = merge(tree[u * 2 + 1], tree[u * 2 + 2]);
		}
	}
	
	Node queryRange(int u, int s, int e, int l, int r)
	{
		if(l > e || r < s) return {0, INT_MIN, INT_MIN, INT_MIN};
		if(l <= s && r >= e) return tree[u];
		int mid = (s + e) >> 1;
		Node left = queryRange(u * 2 + 1, s, mid, l, r);
		Node right = queryRange(u * 2 + 2, mid + 1, e, l, r);
		return merge(left, right);
	}
public:
	SegmentTree(const vector<int>& nums)
	{
		n = nums.size();
		tree.resize(4 * n);
		build(nums, 0, 0, n - 1);
	}	
	
	void update(int idx, int val)
	{
		updateRange(0, 0, n - 1, idx, val);
	}
	
	int query(int l, int r)
	{
		return queryRange(0, 0, n - 1, l, r).tmax;
	}
};

# 区间最大公约数

区间修改，区间查询

利用差分数组将区间修改改成单点修改

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
class SegmentTree
{
private:
	struct Node
	{
		int gcd, sum;
	};
	vector<Node> tree;
	int n;
	
	Node merge(const Node& l, const Node& r)
	{
		Node t;
		t.sum = l.sum + r.sum;
		t.gcd = __gcd(abs(l.gcd), abs(r.gcd));
        //因为差分数组可能是负数，但是gcd应该是正数，所以需要取abs
        //因为要对数组进行区间修改，所以不能直接对差分数组取abs
		return t;
	}
	
	void build(const vector<int>& nums, int u, int s, int e)
	{
		if(s == e) tree[u] = {nums[s], nums[s]};
		else
		{
			int mid = (s + e) >> 1;
			build(nums, u * 2 + 1, s, mid);
			build(nums, u * 2 + 2, mid + 1, e);
			tree[u] = merge(tree[u * 2 + 1], tree[u * 2 + 2]);
		}
	}
	
	//单点修改 
	void updateRange(int u, int s, int e, int idx, int val)
	{
		if(s == e)
		{
			tree[u].sum += val;
			tree[u].gcd += val;
		}
		else
		{
			int mid = (s + e) >> 1;
			if(idx <= mid)
				updateRange(u * 2 + 1, s, mid, idx, val);
			else 
				updateRange(u * 2 + 2, mid + 1, e, idx, val);
			tree[u] = merge(tree[u * 2 + 1], tree[u * 2 + 2]);
		}
	}
	
	Node queryRange(int u, int s, int e, int l, int r)
	{
		if(l > e || r < s) return {0, 0};//gcd返回0，因为0与任何数的gcd都是任何数
		if(l <= s && r >= e) return tree[u];
		int mid = (s + e) >> 1;
		Node left = queryRange(u * 2 + 1, s, mid, l, r);
		Node right = queryRange(u * 2 + 2, mid + 1, e, l, r);
		return merge(left, right);
	}
public:
	SegmentTree(const vector<int>& nums)
	{
		n = nums.size();
		tree.resize(4 * n);
		build(nums, 0, 0, n - 1);
	}	
	
	void update(int idx, int val)
	{
		updateRange(0, 0, n - 1, idx, val);
	}
	
	int query(int l, int r)
	{
		return __gcd(queryRange(0, 0, n - 1, l + 1, r).gcd, queryRange(0, 0, n - 1, 0, l).sum);
	}
};

# 区间和（区间加）

区间修改，区间查询（有懒标记）

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
class SegmentTree
{
private:
	struct Node
	{
		int sum;
	};
	struct Node2
	{
		int sum;
	};
	vector<Node> tree;
	vector<Node2> lazy;
	int n;
	
	Node merge(const Node& l, const Node& r)
	{
		Node t;
		t.sum = l.sum + r.sum;
		return t;
	}
	
	void build(const vector<int>& nums, int u, int s, int e)
	{
		if(s == e) tree[u] = {nums[s]};
		else
		{
			int mid = (s + e) >> 1;
			build(nums, u * 2 + 1, s, mid);
			build(nums, u * 2 + 2, mid + 1, e);
			tree[u] = merge(tree[u * 2 + 1], tree[u * 2 + 2]);
		}
	}
	
	void pushdown(int u, int s, int e, int mid)
	{
		if(lazy[u].sum != 0)
		{
			tree[2 * u + 1].sum += lazy[u].sum * (mid - s + 1);
			lazy[2 * u + 1].sum += lazy[u].sum;
			tree[2 * u + 2].sum += lazy[u].sum * (e - mid);
			lazy[2 * u + 2].sum += lazy[u].sum;
			lazy[u].sum = 0;
		}
	}
	
	void updateRange(int u, int s, int e, int l, int r, int val)
	{
		if(l > e || r < s) return;
		if(l <= s && r >= e)
		{
			tree[u].sum += val * (e - s + 1);
			lazy[u].sum += val;
			return;
		}
		int mid = (s + e) >> 1;
		pushdown(u, s, e, mid);
		updateRange(u * 2 + 1, s, mid, l, r, val);
		updateRange(u * 2 + 2, mid + 1, e, l, r, val);
		tree[u] = merge(tree[u * 2 + 1], tree[u * 2 + 2]);
	}
	
	int queryRange(int u, int s, int e, int l, int r)
	{
		if(l > e || r < s) return 0;
		if(l <= s && r >= e) return tree[u].sum;
		int mid = (s + e) >> 1;
		pushdown(u, s, e, mid);
		return queryRange(u * 2 + 1, s, mid, l, r) + queryRange(u * 2 + 2, mid + 1, e, l, r); 
	}
public:
	SegmentTree(const vector<int>& nums)
	{
		n = nums.size();
		tree.resize(4 * n);
		lazy.resize(4 * n);
		build(nums, 0, 0, n - 1);
	}
	
	void update(int l, int r, int val)
	{
		updateRange(0, 0, n - 1, l, r, val);
	}
	int query(int l, int r)
	{
		return queryRange(0, 0, n - 1, l, r);
	}
};

# 区间和（区间加乘）

  1. pushdown 中需要先乘后加，即先处理 lazy[u].mul 后处理 lazy[u].add
  2. 在 update 中 lazy[u].add = (lazy[u].add * mul + add) % mod; 加法的懒标记也需要乘 mul
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
class SegmentTree
{
private:
    struct Node
    {
        int sum;
    };
    struct LazyNode
    {
        int add, mul;
    };
    vector<Node> tree;
    vector<LazyNode> lazy;
    int n;
    int mod;

    Node merge(const Node& l, const Node& r)
    {
        Node t;
        t.sum = (l.sum + r.sum) % mod;
        return t;
    }

    void build(const vector<int>& nums, int u, int s, int e)
    {
        lazy[u].mul = 1;
        lazy[u].add = 0;
        if(s == e) tree[u] = {nums[s] % mod};
        else
        {
            int mid = (s + e) >> 1;
            build(nums, u * 2 + 1, s, mid);
            build(nums, u * 2 + 2, mid + 1, e);
            tree[u] = merge(tree[u * 2 + 1], tree[u * 2 + 2]);
        }
    }

    void pushdown(int u, int s, int e, int mid)
    {
        if(lazy[u].mul != 1 || lazy[u].add != 0)
        {
            // 处理左子树
            tree[u * 2 + 1].sum = (tree[u * 2 + 1].sum * lazy[u].mul + lazy[u].add * (mid - s + 1)) % mod;
            lazy[u * 2 + 1].mul = (lazy[u * 2 + 1].mul * lazy[u].mul) % mod;
            lazy[u * 2 + 1].add = (lazy[u * 2 + 1].add * lazy[u].mul + lazy[u].add) % mod;

            // 处理右子树
            tree[u * 2 + 2].sum = (tree[u * 2 + 2].sum * lazy[u].mul + lazy[u].add * (e - mid)) % mod;
            lazy[u * 2 + 2].mul = (lazy[u * 2 + 2].mul * lazy[u].mul) % mod;
            lazy[u * 2 + 2].add = (lazy[u * 2 + 2].add * lazy[u].mul + lazy[u].add) % mod;

            // 重置当前节点的懒标记
            lazy[u].mul = 1;
            lazy[u].add = 0;
        }
    }

    void updateRange(int u, int s, int e, int l, int r, int add, int mul)
    {
        if(l > e || r < s) return;
        if(l <= s && r >= e)
        {
            tree[u].sum = (tree[u].sum * mul + add * (e - s + 1)) % mod;
            lazy[u].mul = (lazy[u].mul * mul) % mod;
            lazy[u].add = (lazy[u].add * mul + add) % mod;
            return;
        }
        int mid = (s + e) >> 1;
        pushdown(u, s, e, mid);
        updateRange(u * 2 + 1, s, mid, l, r, add, mul);
        updateRange(u * 2 + 2, mid + 1, e, l, r, add, mul);
        tree[u] = merge(tree[u * 2 + 1], tree[u * 2 + 2]);
    }

    int queryRange(int u, int s, int e, int l, int r)
    {
        if(l > e || r < s) return 0;
        if(l <= s && r >= e) return tree[u].sum % mod;
        int mid = (s + e) >> 1;
        pushdown(u, s, e, mid);
        return (queryRange(u * 2 + 1, s, mid, l, r) + queryRange(u * 2 + 2, mid + 1, e, l, r)) % mod;
    }

public:
    SegmentTree(const vector<int>& nums, int p)
    {
        n = nums.size();
        mod = p;
        tree.resize(4 * n);
        lazy.resize(4 * n);
        build(nums, 0, 0, n - 1);
    }

    void updateadd(int l, int r, int val)
    {
        updateRange(0, 0, n - 1, l, r, val, 1);
    }

    void updatemul(int l, int r, int val)
    {
        updateRange(0, 0, n - 1, l, r, 0, val);
    }

    int query(int l, int r)
    {
        return queryRange(0, 0, n - 1, l, r);
    }
};

# 并查集

# 普通版

1
2
3
4
5
6
7
8
//初始化
for(int i = 1; i <= n; i++) fa[i] = i;
//路径压缩
int find(int x)
{
	if(fa[x] != x) fa[x] = find(fa[x]);
	return fa[x];	
}

# 带权并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int find(int x)
{
	if(x != f[x])
	{
		int t = f[x];
		f[x] = find(f[x]);
		d[x] ^= d[t];
	}
	return f[x];
}
void merge(int x, int y, int z)
{
	int fx = find(x), fy = find(y);
	if(fx != fy) 
	{
		f[fy] = fx;
		d[fy] = d[x] ^ d[y] ^ 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
const int N = 1e5 + 10;
int son[N][26], cnt[N], idx;
void Insert(string s)
{
    int p = 0;
    for(int i = 0;s[i]; i++)
    {
        int u = s[i] - 'a';
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}
int Query(string s)
{
    int p = 0;
    for(int i = 0; s[i]; i++)
    {
        int u = s[i] - 'a';
        if(son[p][u]) p = son[p][u];
        else return 0;
    }
    return cnt[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
const int N = 1e5 + 10, M = 31 * N;
int son[M][2], idx;
int a[N];
void Insert(int a)
{
    int p = 0;
    for(int i = 30; i >= 0; i--)
    {
        int u = a >> i & 1;
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
}
int search(int a)
{
    int p = 0, res = 0;
    for(int i = 30; i >= 0; i--)
    {
        int u = a >> i & 1;
        if(son[p][!u])
        {
            p = son[p][!u];
            res = res * 2 + 1;
        }
        else
        {
            p = son[p][u];
            res = res * 2 + 0;
        }
    }
    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
class bigint
{
private:
	string value;
	
	int cmp(const bigint& other) const
	{
		if(value.length() != other.value.length()) return value.length() < other.value.length() ? -1 : 1;
		return value.compare(other.value);
	}
public:
	bigint(const string& s = "0")
	{
		value = s;
	}
	//加法 
	bigint operator+(const bigint& other) const
	{
		string result;
		int carry = 0;
		int i = value.size() - 1, j = other.value.size() - 1;
		while(i >= 0 || j >= 0 || carry > 0)
		{
			int sum = carry;
			if(i >= 0) sum += value[i--] - '0';
			if(j >= 0) sum += other.value[j--] - '0';
			carry = sum / 10;
			result.push_back(sum % 10 + '0');
		}
		reverse(result.begin(), result.end());
		return bigint(result);
	}
	//减法
	bigint operator-(const bigint& other) const
	{
		string result;
		int borrow = 0;
		int i = value.length() - 1, j = other.value.length() - 1;
		while(i >= 0 || j >= 0)
		{
			int diff = borrow;
			if(i >= 0) diff += value[i--] - '0';
			if(j >= 0) diff -= other.value[j--] - '0';
			if(diff < 0)
			{
				diff += 10;
				borrow = -1; 
			}
			else borrow = 0;
			result.push_back(diff + '0');
 		}
 		reverse(result.begin(), result.end());
 		result.erase(0, result.find_first_not_of('0'));
 		if(result.empty()) result = "0";
 		return bigint(result);
	}
	//乘法
	bigint operator*(const bigint& other) const
	{
		string result(value.length() + other.value.length(), '0');
		for(int i = value.length() - 1; i >= 0; i--)
		{
			int carry = 0;
			for(int j = other.value.length() - 1; j >= 0; j--)
			{
				int temp = (value[i] - '0') * (other.value[j] - '0') + carry + (result[i + j + 1] - '0');
				carry = temp / 10;
				result[i + j + 1] = temp % 10 + '0';//得到的数从1开始 
			}
			result[i] += carry;//进位 
		}
		result.erase(0, result.find_first_not_of('0'));
		if(result.empty()) result = "0";
		return bigint(result);
	} 
	//除法
	bigint operator/(const bigint& other)const
	{
		if(other.value == "0")  throw runtime_error("Division by zero");
		if(cmp(other) < 0) return bigint("0");
		string result;
		bigint temp("0");
		for(char digit: value)
		{
			temp = temp * bigint("10") + bigint(string(1, digit));
			int count = 0;
			while(temp.cmp(other) >= 0)
			{
				temp = temp - other;
				count++;
			}
			result.push_back(count + '0');
		}
		result.erase(0, result.find_first_not_of('0'));
		if(result.empty()) result = "0";
		return bigint(result);
 	} 
 	friend ostream& operator<<(ostream& os, const bigint& num)
 	{
 		os << num.value;
 		return os;
	 }
};

# 大数 × 小数

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
string multiplyBigInt(const string& num, int multiplier) 
{
    if (multiplier == 0) return "0";
    
    string result;
    int carry = 0;
    
    // 从最低位开始处理
    for (int i = num.size() - 1; i >= 0; --i) 
    {
        int digit = num[i] - '0';
        int product = digit * multiplier + carry;
        carry = product / 10;
        result.push_back((product % 10) + '0');
    }
    
    // 处理剩余的进位
    while (carry != 0) 
    {
        result.push_back((carry % 10) + '0');
        carry /= 10;
    }
    
    // 反转得到正确顺序
    reverse(result.begin(), result.end());
    
    // 去除前导零
    size_t nonZero = result.find_first_not_of('0');
    if (nonZero != string::npos) 
    {
        return result.substr(nonZero);
    }
    
    return "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
#include<bits/stdc++.h>
using namespace std;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(l, r);

void generate(){
    ofstream fout("input.txt");
    //需要输出的数据
    /*
    eg:
    uniform_int_distribution<> dis(1, 1e5);
    int n = dis(gen), q = dis(gen);
    fout << n << ' ' << q << '\n'; 
    */
    fout.close();
}

int main(){    
    for(int i = 1; i <= 1000; i++)
    {
        cout << "iteration: " << i << '\n';
        generate();
        system("right.exe < input.txt > right.txt");
        system("error.exe < input.txt > error.txt");
        system("fc right.txt error.txt");
        char ch = getchar();
        if(ch == ' ') break;
    }
    return 0;
}

# 图论

# LCA

# Tarjan 离线算法

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 500010; // 最大节点数
int n, m, s;
// 存边
int to[N * 2], ne[N * 2], head[N], idx; // 无向图，边数需要乘以 2
void add(int u, int v)
{
    to[idx] = v;
    ne[idx] = head[u];
    head[u] = idx++;
}
vector<vector<PII>> query; // 查询列表
int st[N], result[N], fa[N];
// 并查集
int find(int x)
{
    if (x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
void merge(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx != fy) fa[fx] = fy;
}
void Tarjan(int u)
{
    st[u] = 1; // 标记当前节点为正在访问
    for (int i = head[u]; i != -1; i = ne[i])
    {
        int v = to[i];
        if (st[v]) continue; // 如果子节点已经访问过，跳过
        Tarjan(v);
        merge(v, u); // 合并子节点和当前节点，注意子节点和父节点是谁合并到谁！！！ 
    }
    st[u] = 2; // 标记当前节点为已访问完毕
    // 处理与当前节点相关的查询
    for (auto t : query[u])
    {
        int v = t.first, i = t.second;
        if (st[v] == 2) // 如果查询的另一个节点已经访问完毕
        {
            result[i] = find(v); // LCA 为另一个节点所在集合的根
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(head, -1, sizeof head);
    // n 是节点个数，m 是询问个数，s 是根节点序号
    cin >> n >> m >> s;
    // 初始化 query 和 result
    query.resize(n + 1);
    fill(result, result + m + 1, -1);
    // 存图（无向图）
    for (int i = 1; i <= n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    // 添加询问，离线处理
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        query[x].push_back({y, i});
        query[y].push_back({x, i});
    }
    // 预处理并查集
    for (int i = 1; i <= n; i++) fa[i] = i;
    // 调用 Tarjan 算法
    Tarjan(s);
    // 输出查询结果
    for (int i = 1; i <= m; i++)
    {
        cout << result[i] << '\n';
    }
    return 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
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500010, LOG = 20;
int n, m, s;
vector<int> tree[N];
int dp[N][LOG], dep[N];
//查找深度
void dfs(int u, int p)
{
	dp[u][0] = p;
	for(int i = 1; i < LOG; i++)
		dp[u][i] = dp[dp[u][i - 1]][i - 1];//u的第2^i个父节点等于u的第2^(i-1)个父节点的第2^(i-1)个父节点
	for(auto child: tree[u])
	{
		if(child != p)
		{
			dep[child] = dep[u] + 1;
			dfs(child, u);
		}
	}
} 
int lca(int x, int y)
{
	//让x更深 
	if(dep[x] < dep[y]) swap(x, y);
	int d = dep[x] - dep[y];
	for(int i = 0; i < LOG; i++)
		if((1 << i) & d) x = dp[x][i];
    //说明x和y的公共祖先是x
	if(x == y) return x;
	//向上倍增
	for(int i = LOG - 1; i >= 0; i--)
	{
		if(dp[x][i] != dp[y][i])
		{
			x = dp[x][i];
			y = dp[y][i];	
		}	
	}
	return dp[x][0]; 
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> s;
	//建树 
	for(int i = 1; i < n; i++) 
	{
		int x, y;
		cin >> x >> y;
		tree[x].push_back(y);
		tree[y].push_back(x);
	}
	//遍历得到深度
	dfs(s, 0); 
	//LCA
	for(int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		cout << lca(x, y) << '\n'; 
	}
	return 0;
}

# 最小生成树

# Kruskal

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 +10;
int n, m, num = 0, ans = 0;
struct Edge
{
	int w;
	int to, pre;
}edge[N];
bool cmp(Edge &x, Edge &y)
{
	return x.w < y.w;
}
int fa[N];
int find(int x)
{
	if(x != fa[x]) fa[x] = find(fa[x]);
	return fa[x];
}
void merge(int i, int fx, int fy)
{
	fa[fx] = fy;
	num++;
	ans += edge[i].w;
}
void kruskal()
{
	for(int i = 1; i <= m; i++)//依次选权值最小的边
	{
		if(num == n - 1) break;
		int fx = find(edge[i].pre), fy = find(edge[i].to);
		if(fx != fy)
		{
			merge(i, fx, fy);//合并
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		edge[i].w = w, edge[i].pre = u, edge[i].to = v;
	}
	sort(edge + 1, edge + m + 1, cmp);//排序
	for(int i = 1; i <= n; i++) fa[i] = i;
	kruskal();
	int flag = 0;
	for(int i = 1; i <= n; i++)
	{
	    if(fa[i] == i) flag++;
	}
	if(flag == 1) cout << ans;
	else cout << "impossible";
	return 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
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10, M = 3e5 + 10, LOG = 30, INF = 1ll << 62;
int f[N], st[M];
int dp[N][LOG], g[N][LOG], h[N][LOG]; 
// dp[u][i]: u节点向上2^i层的      祖先节点
// g[u][i]: u节点向上2^i层路径上的 最大边权
// h[u][i]: u节点向上2^i层路径上的 次大边权
int dep[N];
int n, m, cnt, sum; 
struct edge
{
    int u, v, w;
}e[M * 2]; 
struct edge2
{
    int ne, to, w;    
}ke[M * 2];
int head[M * 2], idx;

void add(int x, int y, int z)
{
    ke[idx].ne = head[x], ke[idx].to = y, ke[idx].w = z, head[x] = idx++;
}
int find(int x)
{
    if(x != f[x]) f[x] = find(f[x]);
    return f[x];
}

void kruskal()
{
    sort(e + 1, e + m + 1, [&](edge a, edge b){
        return a.w < b.w;
    });
    int res = 0;
    for(int i = 1; i <= m; i++)
    {
        int fx = find(e[i].u), fy = find(e[i].v);
        if(fx != fy) 
        {
            f[fx] = fy;
            st[i] = 1;//i边被加入最小生成树 
            add(e[i].u, e[i].v, e[i].w);
            add(e[i].v, e[i].u, e[i].w);
            sum += e[i].w;
            res++;    
        }
        if(res == n - 1) return;
    }
}
void dfs(int u, int fa, int w)
{
    dep[u] = dep[fa] + 1, dp[u][0] = fa;
    g[u][0] = w, h[u][0] = -INF;
    
    for(int i = 1; i < LOG; i++)
    {
        dp[u][i] = dp[dp[u][i - 1]][i - 1];
        g[u][i] = max(g[u][i - 1], g[dp[u][i - 1]][i - 1]);
        h[u][i] = max(h[u][i - 1], h[dp[u][i - 1]][i - 1]);
        if (g[u][i - 1] != g[dp[u][i - 1]][i - 1])
            h[u][i] = max(h[u][i], min(g[dp[u][i - 1]][i - 1], g[u][i - 1]));
    }
    for(int i = head[u]; ~i; i = ke[i].ne)
    {
        int v = ke[i].to;
        if(v == fa) continue;
        dfs(v, u, ke[i].w);
    }
} 
int LCA(int x, int y)
{
    if(dep[x] < dep[y]) swap(x, y);
    int d = dep[x] - dep[y];
    //到同一深度 
    for(int i = 0; i < LOG; i++)
    {
        if((d >> i) & 1) x = dp[x][i];
    }
    if(x == y) return x;
    for(int i = LOG - 1; i >= 0; i--)
    {
        if(dp[x][i] != dp[y][i])
        {
            x = dp[x][i], y = dp[y][i];
        }
    }
    return dp[x][0]; 
}
//找到路径上不等于z的最大边 
int getmax(int x, int y, int z)
{
    int ans = -INF;
    for(int i = LOG - 1; i >= 0; i--)
    {
        if(dep[dp[x][i]] >= dep[y])//如果没有超过lca 
        {
            if(g[x][i] != z) ans = max(ans, g[x][i]);
            else ans = max(ans, h[x][i]);
            x = dp[x][i];
        }
    } 
    return ans;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    memset(head, -1, sizeof head);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
    for(int i = 1; i <= n; i++) f[i] = i;
    //计算最小生成树 
    kruskal();
    //预处理
    dfs(1, 0, 0); 
    int ans = INF;
    //遍历不在最小生成树的边
    for(int i = 1; i <= m; i++)
    {
        if(st[i]) continue;
        int lca = LCA(e[i].u, e[i].v);
        
        int maxu = getmax(e[i].u, lca, e[i].w);
        int maxv = getmax(e[i].v, lca, e[i].w);
        
        ans = min(ans, sum - max(maxu, maxv) + e[i].w);
    } 
    cout << ans;
    return 0;
}

# 数论

# 快速幂

ab(modp)=(a20×a21×...×a2logb)(modp)a^b\pmod p = (a^{2^0} \times a ^{2 ^ 1} \times...\times a ^{2 ^{logb}}) \pmod p 

1
2
3
4
5
6
7
8
9
10
11
12
#define int long long
int qmi(int a, int b, int p)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res;
}

# 求逆元

# 乘法逆元的定义

若整数b，mb，m 互质，并且对于任意的整数 aa，如果满足b∣ab|a，则存在一个整数 xx，使得

ab≡a×x(modm)\frac{a}{b} \equiv a\times x \pmod m

则称 xx 为 bb 的模 mm 乘法逆元，记为 b−1(modm)b^{−1}\pmod m。bb 存在乘法逆元的充要条件是 bb 与模数 mm 互质。当模数 mm 为质数时，bm−2b^{m−2} 即为 bb 的乘法逆元。

1
res = qmi(b, m - 2, m);//res是b的乘法逆元

# 取模类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//其中inv是求乘法逆元
//取模类 
struct mod
{	
	int val;
	mod(int x = 0) : val(x % MOD) {}
	mod operator+(const mod& other) const {return mod(val + other.val);}
	mod operator-(const mod& other) const {return mod(val - other.val + MOD);}
	mod operator*(const mod& other) const {return mod(val * other.val);};
	mod operator/(const mod& other) const {return mod(val * inv(other.val));}
	mod operator +=(const mod& other) {val = (val + other.val) % MOD; return *this;}
	mod operator -=(const mod& other) {val = (val - other.val + MOD) % MOD; return *this;}
	mod operator *=(const mod& other) {val = (val * other.val) % MOD; return *this;}
	mod operator /=(const mod& other) {val = (val * inv(other.val)) % MOD; return *this;}
	friend ostream& operator<<(ostream& os, const mod& m) {return os << m.val;}
};

# 求组合数

# Lucas 定理

解决

Cnm(modp)=C⌊np⌋⌊mp⌋Cn%pm%p(modp)C_n^m \pmod p=C_{\lfloor \frac{n}{p}\rfloor}^{\lfloor \frac{m}{p}\rfloor}C_{n\% p}^{m\%p}\pmod 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
int qmi(int a, int b, int p)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = res * a % p;
        b >>= 1;
        a = a * a % p; 
    }
    return res;
}
int C(int a, int b, int p)
{
    if(b > a) return 0;
    int res = 1;
    for(int i = 1, j = a; i <= b; i++, j--)
    {
        res = res * j % p;
        res = res * qmi(i, p - 2, p) % p;
    }
    return res;
}
int lucas(int a, int b, int p)
{
    if(a < p && b < p) return C(a, b, p);
    return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

# 线性筛质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int N = 1e6 + 10;
int prime[N], st[N], cnt;
int getprime(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) prime[++cnt] = i;
        for(int j = 1; prime[j] <= n / i; j++)
        {
            st[prime[j] * i] = 1;
            if(!(i % prime[j])) break;
        }
    }
    return cnt;
}

# 筛法求欧拉函数

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
const int N = 1e6 + 10;
int phi[N], prime[N], st[N], cnt;
void Eular()
{
	phi[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) 
        {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1; prime[j] <= n / i; j++)
        {
            st[prime[j] * i] = 1;
            if(i % prime[j] == 0)
            {
                phi[prime[j] * i] = phi[i] * prime[j];
                break;
            }
            else
            {
                phi[prime[j] * i] = phi[i] * (prime[j] - 1);   
            }
        }
    }
}

# 扩展欧几里得

1
2
3
4
5
6
7
8
9
10
11
int exgcd(int a, int b, int& x, int& y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

# 中国剩余定理

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
int exgcd(int a, int b, int& x, int& y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    int a1, m1;
    cin >> a1 >> m1;
    n--;
    int flag = 1;
    while(n--)
    {
        int a2, m2;
        cin >> a2 >> m2;
        int k1, k2;
        int d = exgcd(a1, -a2, k1, k2);
        if((m2 - m1) % d)
        {
            flag = 0;
            break;
        }
        k1 = k1 * (m2 - m1) / d;
        //限制，变成最小非负根
        int t = abs(a2 / d);
        k1 = (k1 % t + t) % t;
        //更新新的m1和a1
        m1 = k1 * a1 + m1;
        a1 = abs(a1 / d * a2);//计算最小公倍数
    }
    if(!flag) cout << -1;
    else cout << (m1 % a1 + a1) % a1;
    return 0;
}