algorithm

发表于 更新于 分类于 阅读次数： 本文字数： 33k 阅读时长 ≈ 2:02

算法板子

算法汇总

算法

建图

三种建图方式

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
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 11; // 最大点数
const int MAXM = 21; // 最大边数（无向图需 2 倍）
// 邻接矩阵
int graph1[MAXN][MAXN];
// 邻接表
vector<vector<pair<int, int>>> graph2;
// 链式前向星
int head[MAXN], nxt[MAXM], to[MAXM], weight[MAXM], cnt;
void build(int n) {
    // 清空邻接矩阵
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            graph1[i][j] = 0;
    // 清空邻接表
    graph2.clear();
    graph2.resize(n + 1);
    // 清空链式前向星
    cnt = 0;
    memset(head, 0, sizeof(head));
}
void addEdge(int u, int v, int w) {
    nxt[ ++cnt] = head[u];
    to[cnt] = v;
    weight[cnt] = w;
    head[u] = cnt;
}
//有向
void directGraph(const vector<vector<int>>& edges) {
    for (const auto& edge : edges) {
        graph1[edge[0]][edge[1]] = edge[2];
        graph2[edge[0]].emplace_back(edge[1], edge[2]);
        addEdge(edge[0], edge[1], edge[2]);
    }
}
// 无向
void undirectGraph(const vector<vector<int>>& edges) {
    for (const auto& edge : edges) {
        graph1[edge[0]][edge[1]] = edge[2];
        graph1[edge[1]][edge[0]] = edge[2];
        
        graph2[edge[0]].emplace_back(edge[1], edge[2]);
        graph2[edge[1]].emplace_back(edge[0], edge[2]);
        
        addEdge(edge[0], edge[1], edge[2]);
        addEdge(edge[1], edge[0], edge[2]);
    }
}
void traversal(int n) {
    cout << "邻接矩阵遍历:" << endl;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cout << graph1[i][j] << " ";
        }
        cout << endl;
    }
    cout << "邻接表遍历:" << endl;
    for (int i = 1; i <= n; ++i) {
        cout << i << " (邻居,边权): ";
        for (auto& edge : graph2[i]) {
            cout << "(" << edge.first << "," << edge.second << ") ";
        }
        cout << endl;
    }
    cout << "链式前向星遍历:" << endl;
    for (int i = 1; i <= n; ++i) {
        cout << i << " (邻居,边权): ";
        for (int ei = head[i]; ei > 0; ei = nxt[ei]) {
            cout << "(" << to[ei] << "," << weight[ei] << ") ";
        }
        cout << endl;
    }
}
int main() {
    int n1 = 4;
    vector<vector<int>> edges1 = {{1, 3, 6}, {4, 3, 4}, {2, 4, 2}, {1, 2, 7}, {2, 3, 5}, {3, 1, 1}};
    build(n1);
    directGraph(edges1);
    traversal(n1);
    cout << "==============================" << endl;
    int n2 = 5;
    vector<vector<int>> edges2 = {{3, 5, 4}, {4, 1, 1}, {3, 4, 2}, {5, 2, 4}, {2, 3, 7}, {1, 5, 5}, {4, 2, 6}};
    build(n2);
    undirectGraph(edges2);
    traversal(n2);
    return 0;
}

图最短路

从某一基点到其他点的最短路径

Dijkstra算法

普通堆
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
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, m, st;
    cin >> n >> m >> st;
    vector<int> distance(n + 1, INT_MAX);
    vector<int> visited(n + 1, false);
    vector<vector<pair<int,int>>> g(n + 1);
    for(int i = 0, u, v, w; i < m; i ++){
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }
 	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> q1;
    for(auto it : g[st]){
        q1.push({it.second,it.first});  
    }
    distance[st] = 0;
    pair<int,int> temp;
    int u, w, v;
    while(!q1.empty()){
        temp = q1.top();
        q1.pop();
        u = temp.second;
        w = temp.first;
        if(visited[u]) continue;
        visited[u] = true;
        distance[u] = w;
        for(auto it : g[u]){
            v = it.first;
            if(!visited[v] && it.second + distance[u] < distance[v]){
                q1.push({it.second + distance[u], v});
            }
        }
    }
    for(int i = 1; i <= n; i ++){
        cout << distance[i] << " ";
    }
    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
#include<bits/stdc++.h>
using namespace std;
//heap
int MAXN = 100001;
int MAXM = 200001;
vector<int> head(MAXN);
vector<int> next1(MAXM);
vector<int> to(MAXM);
vector<int> weight(MAXM);
int cnt = 1;
vector<int> heap(MAXN);
int sizeh = 0;
vector<int> where(MAXN,-1);
vector<int> distance1(MAXN,INT_MAX);
void swap1(int i, int j) {
    swap(heap[i], heap[j]);
    where[heap[i]] = i;
    where[heap[j]] = j;
}
void heapInsert(int i) {
    while (i > 0 && distance1[heap[i]] < distance1[heap[(i - 1) / 2]]){
        swap1(i, (i - 1) / 2);
        i = (i - 1) / 2;
    }
}
void heapify(int i) {
    int l = i * 2 + 1;
    int max_mark;
    int mark;
    while (l < sizeh) {
        max_mark = l + 1 < sizeh && distance1[heap[l + 1]] < distance1[heap[l]] ? l + 1 : l;
        mark =distance1[ heap[i]] <distance1[ heap[max_mark]] ? i : max_mark;
        if (mark == i) break;
        else {
            swap1(i, mark);
            i = mark;
            l = i * 2 + 1;
        }
    }
}
void solve2() {
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 0, x, y, w; i < m; i++) {
        cin >> x >> y >> w;
        next1[cnt] = head[x];
        to[cnt] = y;
        weight[cnt] = w;
        head[x] = cnt++;
    }
    heap[sizeh++] = s;
    distance1[s] = 0;
    while (sizeh) {
        int u = heap[0];
        swap1(0, --sizeh);
        heapify(0);
        where[u] = -2;
        for (int ei = head[u]; ei > 0; ei = next1[ei]) {
            int v = to[ei];
            int w = weight[ei];
            if (where[v] == -1) {
                distance1[v] = w + distance1[u];
                where[v] = sizeh;
                heap[sizeh++] = v;
                heapInsert(where[v]);
            } else if (where[v] >= 0){
                distance1[v] = min(distance1[v], distance1[u] + w);
                heapInsert(where[v]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << distance1[i];
        if (i != n) cout << " ";
    }
    cout << endl;
}
求最短奇偶路径

该思想可拓展为某一个节点有n种状态，故每条边增加一个变量为路的数量，一般设置为t = 1,而跑DJ算法时，可以在优先队列后面再加一个属性表示状态type，type = (type + t) % n。

当再增加一个属性表示节点的类别，相同节点间可以以某个代价相互传送时，则可以抽象为新增了一个祖先节点，该祖先与所有该类别的节点相互联通，节点到祖先的t=1，祖先到节点的t=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
// 假设边权为1,若不为1则w+1变成w+weight[ei]
// 初始化奇数和偶数路径长度的距离数组
vector<int> dis_o(n + 1, 1e18), dis_e(n + 1, 1e18); // dis_o: 最短奇数路径，dis_e: 最短偶数路径
dis_e[1] = 0; // 起点（节点1）的偶数路径长度为0
// 使用最小堆优先队列存储 {距离, 节点} 对
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> q1;
q1.push({0, 1}); // 从节点1开始，距离为0
// Dijkstra算法
while (!q1.empty()) {
    auto [w, u] = q1.top(); // w: 当前距离，u: 当前节点
    q1.pop();
    // 遍历节点u的所有邻居
    for (int ei = head[u]; ei; ei = next[ei]) {
        int v = to[ei]; // 邻居节点
        if (w & 1) { // 如果到u的路径长度为奇数
            if (dis_e[v] > w + 1) { // 尝试更新v的偶数路径
                dis_e[v] = w + 1;
                q1.push({w + 1, v});
            }
        } else { // 如果到u的路径长度为偶数
            if (dis_o[v] > w + 1) { // 尝试更新v的奇数路径
                dis_o[v] = w + 1;
                q1.push({w + 1, v});
            }
        }
    }
}
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
/*迷宫有n个房间，通过m条单向道路连接，迷宫的起点是1号房间，终点是n号房间。每条道路都有一个守路人，需要支付对应数量的金币才能通过，这个迷宫还存在着两个神秘的规则：
1.只有当走到终点时经过的路的数量是3的倍数时她才能顺利逃离迷宫。
2.每个房间都有一个类别属性，她可以花费x个金币在相同类别的属性之间瞬移（注意每次瞬移也算作走过了一条路），特殊地她可以在同个房间内进行瞬移
如果怎样都不能走出迷宫的话输出“-1”*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
constexpr int inf = 1e18;
signed main(){
    cin.tie(0)->ios::sync_with_stdio(0);
    int t = 1;
    cin >> t;
    while(t --){
		int n, m, k;
		cin >> n >> m >> k;
		vector adj(n << 1 | 1, vector<array<int, 3>>());
		vector<int> sta(n + 1);
		for(int i = 1; i <= n; i ++){
			cin >> sta[i];
			adj[i].push_back({sta[i] + n, k, 1});
			adj[sta[i] + n].push_back({i, 0, 0});
		}
		for(int i = 1, u, v, w; i <= m; i ++){
			cin >> u >> v >> w;
			adj[u].push_back({v, w, 1});
		}
		vector<array<int, 3>> dis(n << 1 | 1, {inf, inf, inf});
		priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> q1;
		array<int, 3> t1;
		int u, val, in, in1;
		dis[1][0] = 0;
		q1.push({0, 1, 0});
		while(!q1.empty()){
			t1 = q1.top();
			q1.pop();
			val = t1[0], u = t1[1], in = t1[2];
			for(auto [v, w, gap] : adj[u]){
				in1 = (in + gap) % 3;
				if(dis[v][in1] > val + w){
					dis[v][in1] = val + w;
					q1.push({dis[v][in1], v, in1});
				}
			}
		}
		if(dis[n][0] == inf){
			cout << "-1\n";
		}else{
			cout << dis[n][0] << "\n";
		}
    }   
    return 0;
}

Floyd算法

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
#include <bits/stdc++.h>
using namespace std;
const int INF = numeric_limits<int>::max();
void floydWarshallTemplate() {
    int n, m;
    cin >> n >> m;
    // 初始化邻接矩阵，默认不可达时权值为 INF
    vector<vector<int>> dist(n, vector<int>(n, INF));
    // 自己到自己距离为 0
    for (int i = 0; i < n; i++) {
        dist[i][i] = 0;
    }
    // 读入边，假设输入为无向图，若为有向图则只更新一边
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--; // 若输入顶点编号从 1 开始则转换为从 0 开始
        // 对于多重边取权值最小的一条
        dist[u][v] = min(dist[u][v], w);
        dist[v][u] = min(dist[v][u], w);
    }
    // Floyd–Warshall 算法：枚举中转点 k、起点 i 和终点 j
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            // 如果 i->k 不可达则无需更新
            if (dist[i][k] == INF) continue;
            for (int j = 0; j < n; j++) {
                // 若路径 i->k 和 k->j 均可达，更新 i->j 的最短路径
                if (dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    // 输出结果：若两点不可达则输出 0，否则输出最短路径长度
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << (dist[i][j] == INF ? 0 : dist[i][j]) << " ";
        }
        cout << "\n";
    }
}

SPFA（Shortest Path Faster Algorithm）算法

SPFA 算法是对 Bellman-Ford 算法的一种改进，主要用于在含有负权边的图中求最短路径。它利用队列来维护“待更新”的节点，从而提高更新效率。

根据最短路径理论，在没有负权回路的图中，从起点到任一节点的最短路径最多只需要经过 n-1 条边。所以若某节点的路径更新次数超过 n-1，就能确定有负权回路存在。

visited：标记当前节点是否在队列中，防止重复入队

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>
using namespace std;
#define int long long
#define pb push_back
#define sc second
#define fr first
const int M = 6001;
vector<int> head(M/2);
vector<int> next1(M);
vector<int> to(M);
vector<int> weight(M);
int cnt;
void addedge(int x,int y,int w){
    next1[cnt] = head[x];
    to[cnt] = y;
    weight[cnt] = w;
    head[x] = cnt++;
}
void solve(void) {
    int n, m;
    cin >> n >> m;
    cnt=1;
    fill(head.begin(),head.end(),0);
    for (int i = 0, x, y, w; i < m; i++) {
        cin >> x >> y >> w;
        addedge(x,y,w);
        if (w >= 0) {
            addedge(y,x,w);
        }
    }
    queue<int> heap;
    vector<int> distance(n + 1, INT_MAX);
    vector<int> upcnt(n + 1, 0);
    vector<int> visited(n + 1, 0);
    heap.push(1);
    distance[1] = 0;
    upcnt[1]++;
    visited[1] = 1;
    while (!heap.empty()) {
        int u = heap.front();
        heap.pop();
        visited[u] = 0;
        for (int ei = head[u];ei > 0;ei = next1[ei]) {
            int v = to[ei];
            int w = weight[ei];
            if (w + distance[u] < distance[v]) {
                distance[v] = w + distance[u];
                if (visited[v]==0) {
                    if ((++upcnt[v])  > n-1) {
                        //存在负权回路
                        cout << "YES" << endl;
                        return;
                    }
                    visited[v] = 1;
                    heap.push(v);
                }
            }
        }
    }
    cout << "NO" << endl;
}

最小生成树

树上的一条无回路的连通所有节点的一条权值最小的路径

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
// Kruskal 算法：利用并查集求最小生成树
int kruskal() {
    int n, m;
    cin >> n >> m;
    vector<tuple<int,int,int>> edges; // (权值, 点u, 点v)
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({w, u, v});
    }
    sort(edges.begin(), edges.end());
    vector<int> parent(n + 1);
    for (int i = 1; i <= n; i++) parent[i] = i;
	auto find = [&](auto && f, int x) -> int{
		if(parent[x] != x){
			parent[x] = f(f,parent[x]);
		}
		return parent[x];
	};
    int sum = 0;
    for (auto [w, u, v] : edges) {
        int pu = find(find, u), pv = find(find, v);
        if (pu != pv) {
            parent[pu] = pv;
            sum += w;
        }
    }
    return sum;
}

Prim算法

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
// Prim 算法
int prim() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> graph(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    vector<bool> visited(n + 1, false);
    // 优先队列：pair(权值, 节点)
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    visited[1] = true;
    for (auto edge : graph[1]) pq.push({edge.second, edge.first});
    int sum = 0;
    while (!pq.empty()) {
        auto [w, u] = pq.top();
        pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        sum += w;
        for (auto edge : graph[u])
            if (!visited[edge.first])
                pq.push({edge.second, edge.first});
    }
    return 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
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;
struct TreeNode{
    int val;
    TreeNode * left, * right;
    TreeNode (int x){
        val = x;
    }
};
//先序的序列化与反序列化
class Codec {
public:
    string serialize(TreeNode* root) {
        string r;
        serialize_h(root,r);
        return r;
    }
    TreeNode* deserialize(string data) {
        vector<string> vals = split(data,',');
        int cnt=0;
        return deserialize_h(vals,cnt);
    }
private:
    void serialize_h(TreeNode* root,string& r){
        if(root==nullptr){
            r+="#,";
        }else{
            r+=to_string(root->val)+",";
            serialize_h(root->left,r);
            serialize_h(root->right,r);
        }
    }
    TreeNode* deserialize_h(const vector<string>& vals,int& cnt){
        if(cnt >= vals.size() || vals[cnt]=="#" ){
            cnt++;
            return nullptr;
        }
        TreeNode* node = new TreeNode(stoi(vals[cnt++]));
        node->left=deserialize_h(vals,cnt);
        node->right=deserialize_h(vals,cnt);
        return node;
    }
    vector<string> split(const string&s,char delimiter){
        vector<string> tokens;
        string token;
        istringstream tokenStream(s);
        while(getline(tokenStream,token,delimiter)){
            tokens.push_back(token);
        }
        return tokens;
    }
    //按层的序列化与反序列化
    string serialize1(TreeNode* root) {
        if(root==nullptr) return "";
        string result;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* node = q.front();
            q.pop();
            if(node!=nullptr){
                result += to_string(node->val)+",";
                q.push(node->left);
                q.push(node->right);
            }else result+="#,";
        }return result;
    }
    TreeNode* deserialize1(string data) {
        if(data.empty()) return nullptr;
        stringstream ss(data);
        string item;
        getline(ss,item,',');
        TreeNode* root = new TreeNode(stoi(item));
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* node = q.front();
            q.pop();
            if(getline(ss,item,',')){
                if(item=="#"){
                    node->left=nullptr;
                }else{
                    node->left = new TreeNode(stoi(item));
                    q.push(node->left);
                }
            }
            if(getline(ss,item,',')){
                if(item=="#"){
                    node->right=nullptr;
                }else{
                    node->right=new TreeNode(stoi(item));
                    q.push(node->right);
                }
            }
        }return root;
    }
};

利用先序和中序构造二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//先序和中序构造二叉树
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty() || inorder.empty() || preorder.size() != inorder.size()) return nullptr;
        unordered_map<int,int> map;
        for(int i=0;i<inorder.size();i++) map[inorder[i]]=i;
        return build(preorder,0,inorder.size()-1,inorder,0,inorder.size()-1,map);
    }
private:
    TreeNode* build(const vector<int>& preorder,int l1,int r1,const vector<int>& inorder,int l2,int r2,
    unordered_map<int,int>& map){
        if(l1>r1) return nullptr;
        TreeNode* root = new TreeNode(preorder[l1]);
        if(l1==r1) return root;
        int k=map[preorder[l1]];
        root->left = build(preorder,l1+1,l1+k-l2,inorder,l2,k-1,map);
        root->right = build(preorder,l1+k-l2+1,r1,inorder,k+1,r2,map);
        return root;
    }    
};

二叉树中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
//LCA问题
//求二叉树两个节点的最近公共祖先
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr || root==p || root==q){
        	return root;
		}
        TreeNode* l = lowestCommonAncestor(root->left,p,q);
        TreeNode* r = lowestCommonAncestor(root->right,p,q);
        if(l!=nullptr && r!=nullptr){
        	//左右两边都已经找到
        	return root;
        }
        if(l==nullptr && r==nullptr){
        	//左右两边都没有找到
        	return nullptr;
        }
        //只有一边找到了，返回找到的一边
        return l==nullptr?r:l;
    }
};
//求线索二叉树两个节点的最近公共祖先
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // root从上到下
		// 如果先遇到了p，说明p是答案
		// 如果先遇到了q，说明q是答案
		// 如果root在p~q的值之间，不用管p和q谁大谁小，只要root在中间，那么此时的root就是答案
		// 如果root在p~q的值的左侧，那么root往右移动
		// 如果root在p~q的值的右侧，那么root往左移动
        while(root->val!=p->val && root->val!=q->val){
            if(root->val < max(p->val,q->val) && root->val > min(p->val,q->val)){
                break;
            }
            root = root->val < min(q->val,p->val)?root->right:root->left;
        }return root;
    }
};

树状数组

一维

单点修改区间查询
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
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 1;
vector<int> v1(N);
int n, m;
int low(int x){
    return x & -x;
}
void add(int i, int x){
    while(i <= n){
        v1[i] += x;
        i += low(i);
    }
}
int get(int i){
    int ans = 0;
    while(i){
        ans += v1[i];
        i -= low(i);
    }
    return ans;
}
int range(int i, int j){
    return get(j) - get(i - 1);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for(int i = 1, x; i <= n; i ++){
        cin >> x;
        add(i, x);
    }
    for(int i = 0, op, x, y; i < m; i ++){
        cin >> op >> x >> y;
        if(op == 1){
            add(x, y);
        }else{
            cout << range(x, y) << "\n";
        }
    }
    return 0;
}
区间修改单点查询

在单点基础上，利用一维差分，最后求从0到i的累加和即为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
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 1;
vector<long long> v1(N, 0);
int n, m;
int low(int x){
    return x & -x;
}
void add(int i, int x){
    while(i <= n){
        v1[i] += x;
        i += low(i);
    }
}
long long get(int i){
    long long ans = 0;
    while(i){
        ans += v1[i];
        i -= low(i);
    }
    return ans;
}
long long range(int i, int j){
    return get(j) - get(i - 1);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for(int i = 1, x; i <= n; i ++){
        cin >> x;
        add(i, x);
        add(i + 1, -x);
    }
    for(int i = 0, op, x, y, z; i < m; i ++){
        cin >> op;
        if(op == 1){
            cin >> x >> y >> z;
            add(x, z);
            add(y + 1, -z);
        }else{
            cin >> x;
            cout << range(1, x) << "\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
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 1;
vector<long long> v1(N);
vector<long long> v2(N);
int n, m;
int low(int x){
    return x & -x;
}
void add(int i, int x, vector<long long> & v){
    while(i <= n){
        v[i] += x;
        i += low(i);
    }
}
long long get(int i, vector<long long> & v){
    long long ans = 0;
    while(i){
        ans += v[i];
        i -= low(i);
    }
    return ans;
}
long long range(int i, int j){
    return j * get(j, v1) - get(j, v2) - ((i - 1) * get(i - 1, v1) - get(i -1, v2));
}
void add(int x, int y, long long w){
    add(x, w, v1);
    add(y + 1, -w, v1);
    add(x, (x - 1) * w, v2);
    add(y + 1, - y * w, v2);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for(int i = 1, x; i <= n; i ++){
        cin >> x;
        add(i, i, x);
    }
    for(int i = 0, op, x, y, z; i < m; i ++){
        cin >> op;
        if(op == 1){
            cin >> x >> y >> z;
            add(x, y, z);
        }else{
            cin >> x >> y;
            cout << range(x,  y) << "\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
#include <bits/stdc++.h>
using namespace std;
int low(int i) {
    return i & -i;
}
void add(vector<vector<int>> & bit, int x, int y, int w, int n, int m) {
    for (int i = x; i <= n; i += low(i)) {
        for (int j = y; j <= m; j += low(j)) {
            bit[i][j] += w;
        }
    }
}
int query(vector<vector<int>> &bit, int x, int y) {
    int ans = 0;
    for (int i = x; i > 0; i -= low(i)) {
        for (int j = y; j > 0; j -= low(j)) {
            ans += bit[i][j];
        }
    }
    return ans;
}
int get(vector<vector<int>> &bit, int x1, int y1, int x2, int y2) {
    if (x1 > x2 || y1 > y2) return 0;
    return query(bit, x2, y2) - query(bit, x1 - 1, y2) - query(bit, x2, y1 - 1) + query(bit, x1 - 1, y1 - 1);
}
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> v1(n + 1, vector<int>(m + 1, 0)); // 原始数组
    vector<vector<int>> bit(n + 1, vector<int>(m + 1, 0)); // 树状数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> v1[i][j];
            add(bit, i, j, v1[i][j], n, m);
        }
    }
    int q;
    cin >> q;
    int type;
    int x, y, w;
    int diff;
    int x1, y1, x2, y2;
    while (q--) {
        cin >> type;
        if (type == 1) { 
            cin >> x >> y >> w;
            diff = w - v1[x][y];
            v1[x][y] = w;
            add(bit, x, y, diff, n, m);
        } else if (type == 2) {
            cin >> x1 >> y1 >> x2 >> y2;
            cout << get(bit, x1, y1, x2, y2) << "\n";
        }
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    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
#include <bits/stdc++.h>
using namespace std;
const int N = 2050;
int bit1[N][N];
int bit2[N][N];
int bit3[N][N];
int bit4[N][N];
int n, m;
int a, b, c, d, w;
int v1, v2, v3, v4;
int low(int x){
    return x & -x;
}
void add(int x, int y, int v){
    v1 = v;
    v2 = x * v;
    v3 = y * v;
    v4 = x * y * v;
    for(int i = x; i <= n; i += low(i)){
        for(int j = y; j <= m; j += low(j)){
            bit1[i][j] += v1;
            bit2[i][j] += v2;
            bit3[i][j] += v3;
            bit4[i][j] += v4;
        }   
    }
}
int get(int x, int y){
    int ans = 0;
    for(int i = x; i; i -= low(i)){
        for(int j = y; j; j -= low(j)){
            ans += (x + 1) * (y + 1) * bit1[i][j] - (y + 1) * bit2[i][j] - (x + 1) * bit3[i][j] + bit4[i][j];
        }
    }
    return ans;
}
void add(int x1, int y1, int x2, int y2, int v){
    add(x1, y1, v);
    add(x2 + 1, y2 + 1, v);
    add(x1, y2 + 1, - v);
    add(x2 + 1, y1, - v);
}
int get(int x1, int y1, int x2, int y2){
    return get(x2, y2) + get(x1 - 1, y1 - 1) - get(x1 - 1, y2) - get(x2, y1 - 1);
}
void solve(char C) {
    if(C == 'L'){
        cin >> a >> b >> c >> d >> w;
        add(a, b, c, d, w);
    }else if(C != 'X'){
        cin >> a >> b >> c >> d;
        cout << get(a, b, c, d) << "\n";
    }else{
        cin >> n >> m;
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    char C;
    while (cin >> C) {
        solve(C);
    }
    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
// https://www.luogu.com.cn/problem/P3372
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
signed main(){
	cin.tie(0) -> ios::sync_with_stdio(0);
	int t = 1;
    // cin >> t;
    while (t--){
		int n, q;
		cin >> n >> q;
		vector<int> v1(n + 1), sum((n << 2) + 1), add((n << 2) + 1);
		for(int i = 1; i <= n; i ++){
			cin >> v1[i];
		}
		auto build = [&](auto && f, int i, int l, int r) -> void{
			if(l == r){
				sum[i] = v1[l];
			}else{
				int mid = (l + r) >> 1;
				f(f, i << 1, l, mid);
				f(f, i << 1 | 1, mid + 1, r);
				sum[i] = sum[i << 1] + sum[i << 1 | 1];
			}
			add[i] = 0;
		};
		auto up = [&](int i){
			sum[i] = sum[i << 1] + sum[i << 1 | 1];
		};
		auto lazy = [&](int i, int val, int len){
			sum[i] += val * len;
			add[i] += val;
		};
		auto down = [&](int i, int lenl, int lenr){
			if(add[i] == 0){
				return ;
			}
			lazy(i << 1, add[i], lenl);
			lazy(i << 1 | 1, add[i], lenr);
			add[i] = 0;
		};
		auto add1 = [&](auto && f,int i, int val, int basel, int baser, int l, int r) -> void{
			if(basel <= l && baser >= r){
				lazy(i, val, r - l + 1);
			}else{
				int mid = (l + r) >> 1;
				down(i, mid - l + 1, r - mid);
				if(basel <= mid){
					f(f, i << 1, val, basel, baser, l, mid);
				}
				if(baser >= mid + 1){
					f(f, i << 1 | 1, val, basel ,baser, mid + 1, r);
				}
				up(i);
			}
		};
		build(build, 1, 1, n);
		auto query = [&](auto && f, int i, int basel, int baser, int l, int r) -> int {
			if(basel <= l && baser >= r){
				return sum[i];
			}else{
				int mid = (l + r) >> 1;
				down(i, mid - l + 1, r - mid);
				int ans = 0;
				if(basel <= mid){
					ans += f(f, i << 1, basel, baser, l, mid);
				}
				if(baser >= mid + 1){
					ans += f(f, i << 1 | 1, basel, baser, mid + 1, r);
				}
				return ans;
			}
		};
		for(int i = 0; i < q; i ++){
			int op;
			cin >> op;
			if(op == 1){
				int l, r, val;
				cin >> l >> r >> val;
				add1(add1, 1, val, l , r, 1, n);
			}else{
				int l, r;
				cin >> l >> r;
				cout << query(query, 1, l, r, 1, n) << "\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
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
// https://www.luogu.com.cn/problem/P1253
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
signed main(){
	cin.tie(0) -> ios::sync_with_stdio(0);
	int t = 1;
    // cin >> t;
    while (t--){
		 int n, q;
		 cin >> n >> q;
		 vector<int> v1(n + 1), change((n << 2)), max1((n << 2)), add((n << 2));
		 vector<bool> has((n << 2));
		 for(int i = 1; i <= n; i ++){
		 	cin >> v1[i];
		 }
		 auto biuld = [&](auto && f, int i, int l, int r) -> void {
		 	if(l == r){
			 	 max1[i] = v1[l];
		 	}else{
		 		int mid = (l + r) >> 1;
		 		f(f, i << 1, l, mid);
		 		f(f, i << 1 | 1, mid + 1, r);
		 		max1[i] = max(max1[i << 1], max1[i << 1 | 1]);
		 	}
		 	has[i] = false;
		 	add[i] = 0;
		 };
		 biuld(biuld, 1, 1, n);
		 auto up = [&](int i) {
		 	max1[i] = max(max1[i << 1], max1[i << 1 | 1]);
		 };
		 auto lazyadd = [&](int i, int val) {
		 	max1[i] += val;
		 	add[i] += val;
		 };
		 auto lazyset = [&](int i, int val) {
		 	max1[i] = val;
		 	change[i] = val;
		 	add[i] = 0;
		 	has[i] = true;
		 };
		 auto down = [&](int i) {
			if(has[i]){
				lazyset(i << 1, change[i]);
				lazyset(i << 1 | 1, change[i]);
				has[i] = false;
			}
			if(add[i]){
				lazyadd(i << 1, add[i]);
				lazyadd(i << 1 | 1, add[i]);
				add[i] = 0;
			}
		 };
		 auto add1 = [&](auto && f, int i, int val, int basel, int baser, int l, int r) -> void {
		 	if(basel <= l && baser >= r){
		 		lazyadd(i, val);
			}else{
				int mid = (l + r) >> 1;
				down(i);
				if(basel <= mid){
					f(f, i << 1, val, basel, baser, l, mid);
				}
				if(baser > mid){
					f(f, i << 1 | 1, val, basel, baser, mid + 1, r);
				}
				up(i);
			}
		};
		auto set = [&](auto && f, int i, int val, int basel, int baser, int l, int r) -> void {
			if(basel <= l && baser >= r){
				lazyset(i, val);
			}else{
				int mid = (l + r) >> 1;
				down(i);
				if(basel <= mid){
					f(f, i << 1, val, basel, baser, l, mid);
				}
				if(baser > mid){
					f(f, i << 1 | 1, val, basel, baser, mid + 1, r);
				}
				up(i);
			}
		};
		auto query = [&](auto && f, int i, int basel, int baser, int l, int r) -> int{
			if(basel <= l && baser >= r){
				return max1[i];
			}else{
				int mid = (l + r) >> 1;
				down(i);
				int ans = -1e18;
				if(basel <= mid){
					ans = max(ans, f(f, i << 1, basel, baser, l, mid));
				}
				if(baser > mid){
					ans = max(ans, f(f, i << 1 | 1, basel, baser, mid + 1, r));
				}
				return ans;
			}
		};
		for(int i = 0; i < q; i ++){
			int op;
			cin >> op;
			int l, r;
			cin >> l >> r;
			if(op == 2){
				int x;
				cin >> x;
				add1(add1, 1, x, l, r, 1, n);
			}else if(op == 1){
				int x;
				cin >> x;
				set(set, 1, x, l, r, 1, n);
			}else{
				cout << query(query, 1, l, r, 1, n) << "\n";
			}
		}
	}
	return 0;
}

离散化

离散化之后要注意间隙，如覆盖问题，要在离散化之后的两个差值不为一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
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
188
// https://www.luogu.com.cn/problem/P6242
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;
        vector<int> max1(n<<2),    // 区间当前最大值
                    sec(n<<2),     // 区间严格次大值
                    cnt(n<<2),     // 区间等于最大值的元素个数
                    sum(n<<2),     // 区间元素和
                    his(n<<2),     // 区间历史最大值（曾经出现过的最大值）
                    add1(n<<2),    // 懒标记 A：对“当前最大值元素”做加法
                    add2(n<<2),    // 懒标记 B：对“非最大值元素”做加法
                    adds1(n<<2),   // 历史最大值懒标记 A
                    adds2(n<<2);   // 历史最大值懒标记 B
        auto up = [&](int i){
            sum[i] = sum[i<<1] + sum[i<<1|1];
            his[i] = max(his[i<<1], his[i<<1|1]);
            max1[i] = max(max1[i<<1], max1[i<<1|1]);
            // 合并 cnt 与 sec
            if(max1[i<<1] == max1[i<<1|1]){
                cnt[i] = cnt[i<<1] + cnt[i<<1|1];
                sec[i] = max(sec[i<<1], sec[i<<1|1]);
            } else if(max1[i<<1] > max1[i<<1|1]){
                cnt[i] = cnt[i<<1];
                sec[i] = max(sec[i<<1], max1[i<<1|1]);
            } else {
                cnt[i] = cnt[i<<1|1];
                sec[i] = max(sec[i<<1|1], max1[i<<1]);
            }
        };
        auto build = [&](auto&& self, int i, int l, int r) -> void {
            if(l == r){
                int x;
                cin >> x;
                max1[i] = sum[i] = his[i] = x;  // 当前值、区间和值、历史最大均为 x
                cnt[i] = 1;                     // 只有一个元素
                sec[i] = LLONG_MIN / 2;         // 次大值设为 -INF（用很小的数）
            } else {
                int mid = (l + r) >> 1;
                self(self, i<<1, l, mid);
                self(self, i<<1|1, mid+1, r);
                up(i);
            }
            // 懒标记初始为 0
            add1[i] = add2[i] = adds1[i] = adds2[i] = 0;
        };
        build(build, 1, 1, n);
        // 核心懒标记下发函数
        // val1: 加到“当前最大值元素”上的增量
        // val2: 加到“非最大值元素”上的增量
        // val3/val4: 用于更新历史最大值的增量
        // len: 本区间长度
        auto lazy = [&](int i, int val1, int val2, int val3, int val4, int len){
            // 更新历史最大值
            his[i] = max(his[i], max1[i] + val3);
            // 更新子树的历史懒标记
            adds1[i] = max(adds1[i], add1[i] + val3);
            adds2[i] = max(adds2[i], add2[i] + val4);
            // 区间和更新
            sum[i] += val1 * cnt[i] + val2 * (len - cnt[i]);
            // 更新“当前最大值”与“非最大值”懒标记
            add1[i] += val1;
            add2[i] += val2;
            // 更新当前最大值
            max1[i] += val1;
            // 次大值也需加 val2（若不存在则保持 -INF）
            if(sec[i] > LLONG_MIN/2) sec[i] += val2;
        };
        // 下推函数：将 i 节点的懒标记传递给左右子节点
        auto down = [&](int i, int lenL, int lenR){
            // 左右子节点新的“当前最大”值
            int tL = max1[i<<1], tR = max1[i<<1|1];
            // 父节点最高值
            int mx = max(max1[i<<1], max1[i<<1|1]);
            // 左子树
            if(tL == mx){
                // 左子树中有父区间最大值元素
                lazy(i<<1, add1[i], add2[i], adds1[i], adds2[i], lenL);
            } else {
                // 左子树中只有“非最大值”元素
                lazy(i<<1, add2[i], add2[i], adds2[i], adds2[i], lenL);
            }
            // 右子树（同理）
            if(tR == mx){
                lazy(i<<1|1, add1[i], add2[i], adds1[i], adds2[i], lenR);
            } else {
                lazy(i<<1|1, add2[i], add2[i], adds2[i], adds2[i], lenR);
            }
            // 清空父节点懒标记
            add1[i] = add2[i] = adds1[i] = adds2[i] = 0;
        };
        // 区间加法 [bl,br] 全加 val
        auto addRange = [&](auto&& self, int i, int bl, int br, int val, int l, int r) -> void {
            if(bl <= l && r <= br){
                // 统一打懒标记，val1=val2=val3=val4=val
                lazy(i, val, val, val, val, r-l+1);
            } else {
                int mid = (l + r) >> 1;
                down(i, mid-l+1, r-mid);
                if(bl <= mid)      self(self, i<<1, bl, br, val, l, mid);
                if(br > mid)       self(self, i<<1|1, bl, br, val, mid+1, r);
                up(i);
            }
        };
        // 区间 chmin：把区间内所有大于 val 的值降到 val
        auto chminRange = [&](auto&& self, int i, int bl, int br, int val, int l, int r) -> void {
            if(max1[i] <= val) return;  // 本区间最大值已 ≤ val，无需操作
            if(bl <= l && r <= br && sec[i] < val){
                // 全区间最大值都大于 val，且次大值 < val
                // 只需把“最大值元素”降到 val
                lazy(i, val-max1[i], 0, val-max1[i], 0, r-l+1);
            } else {
                int mid = (l + r) >> 1;
                down(i, mid-l+1, r-mid);
                if(bl <= mid)      self(self, i<<1, bl, br, val, l, mid);
                if(br > mid)       self(self, i<<1|1, bl, br, val, mid+1, r);
                up(i);
            }
        };
        // 区间求和
        auto querySum = [&](auto&& self, int i, int bl, int br, int l, int r) -> int {
            if(bl <= l && r <= br){
                return sum[i];
            } else {
                int mid = (l + r) >> 1;
                down(i, mid-l+1, r-mid);
                int res = 0;
                if(bl <= mid)    res += self(self, i<<1, bl, br, l, mid);
                if(br > mid)     res += self(self, i<<1|1, bl, br, mid+1, r);
                return res;
            }
        };
        // 区间最大值
        auto queryMax = [&](auto&& self, int i, int bl, int br, int l, int r) -> int {
            if(bl <= l && r <= br){
                return max1[i];
            } else {
                int mid = (l + r) >> 1;
                down(i, mid-l+1, r-mid);
                int res = LLONG_MIN/2;
                if(bl <= mid)    res = max(res, self(self, i<<1, bl, br, l, mid));
                if(br > mid)     res = max(res, self(self, i<<1|1, bl, br, mid+1, r));
                return res;
            }
        };
        // 区间历史最大值
        auto queryHis = [&](auto&& self, int i, int bl, int br, int l, int r) -> int {
            if(bl <= l && r <= br){
                return his[i];
            } else {
                int mid = (l + r) >> 1;
                down(i, mid-l+1, r-mid);
                int res = LLONG_MIN/2;
                if(bl <= mid)    res = max(res, self(self, i<<1, bl, br, l, mid));
                if(br > mid)     res = max(res, self(self, i<<1|1, bl, br, mid+1, r));
                return res;
            }
        };
        // 处理 m 次操作
        while(m--){
            int op, l, r;
            cin >> op >> l >> r;
            if(op == 1){
                int x; cin >> x;
                addRange(addRange, 1, l, r, x, 1, n);
            } else if(op == 2){
                int x; cin >> x;
                chminRange(chminRange, 1, l, r, x, 1, n);
            } else if(op == 3){
                cout << querySum(querySum, 1, l, r, 1, n) << "\n";
            } else if(op == 4){
                cout << queryMax(queryMax, 1, l, r, 1, n) << "\n";
            } else if(op == 5){
                cout << queryHis(queryHis, 1, l, r, 1, n) << "\n";
            }
        }
    }
    return 0;
}

结合摩尔投票

经典摩尔投票，求数组中出现次数大于$\frac{n}{2}$d 数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int majorityElement(vector<int>& nums) {
  		int now = -1, cnt = 0;
  		for(auto x : nums){
  			if(!cnt){
  				now = x;
  				cnt = 1;
  			}else{
  				if(now == x){
  					cnt ++;
  				}else{
  					cnt --;
  				}
  			}
  		}
  		return now;
    }
};
结合线段树求区间海王数
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
// https://leetcode.cn/problems/online-majority-element-in-subarray/
#define fr first
#define sc second
class MajorityChecker {
public:
	vector<int> val, cnt, v1;
	vector<pair<int,int>> v2;
	int n;
	void up(int i) {
		if(!cnt[i << 1] && !cnt[i << 1 | 1]){
			cnt[i] = 0;
		}else if(!cnt[i << 1]){
			cnt[i] = cnt[i << 1 | 1];
			val[i] = val[i << 1 | 1];
		}else if(!cnt[i << 1 | 1]){
			cnt[i] = cnt[i << 1];
			val[i] = val[i << 1];
		}else{
			if(val[i << 1] == val[i << 1 | 1]){
				val[i] = val[i << 1];
				cnt[i] = cnt[i << 1] + cnt[i << 1 | 1];
			}else{
				if(cnt[i << 1] >= cnt[i << 1| 1]){
					val[i] = val[i << 1];
					cnt[i] = cnt[i << 1] - cnt[i << 1 | 1];
				}else{
					val[i] = val[i << 1 | 1];
					cnt[i] = cnt[i << 1 | 1] - cnt[i << 1];
				}
			}
		}
	}
	void build(int i, int l, int r) {
		if(l == r){
			cnt[i] = 1;
			val[i] = v1[l];
		}else{
			int mid = (l + r) >> 1;
			build(i << 1, l, mid);
			build(i << 1 | 1, mid + 1, r);
			up(i);
		}
	}
	pair<int,int> get(int i, int bl, int br, int l, int r){
		if(bl <= l && br >= r){
			return {val[i], cnt[i]};
		}else{
			int mid = (l + r) >> 1;
			pair<int,int> left = {0, 0}, right = {0, 0}, ans;
			if(bl <= mid){
				left = get(i << 1, bl, br, l, mid);
			}
			if(br > mid){
				right = get(i << 1 | 1, bl, br, mid + 1, r);
			}
			if(!left.sc && !right.sc){
				ans.sc = 0;
			}else if(!left.sc){
				ans.fr = right.fr;
				ans.sc = right.sc;
			}else if(!right.sc){
				ans.fr = left.fr;
				ans.sc = left.sc;
			}else{
				if(left.fr == right.fr){
					ans.fr = left.fr;
					ans.sc = left.sc + right.sc;
				}else{
					if(left.sc >= right.sc){
						ans.fr = left.fr;
						ans.sc = left.sc - right.sc;
					}else{
						ans.fr = right.fr;
						ans.sc = right.sc - left.sc;
					}
				}
			}
			return ans;
		}
	}
	int find(int x, int in) {
		int l = 0, r = n - 1;
		int mid, ans = -1;
		while(l <= r){
			mid = (l + r) >> 1;
			if(v2[mid].fr > x){
				r = mid - 1;
			}else if(v2[mid].fr < x){
				l = mid + 1;
			}else{

				if(v2[mid].sc >= in){
                    				ans = mid;
					r = mid - 1;
				}else{
					l = mid + 1;
				}
			}
		}
		return ans;
	};
    int find2(int x, int in) {
		int l = 0, r = n - 1;
		int mid, ans = -1;
		while(l <= r){
			mid = (l + r) >> 1;
			if(v2[mid].fr > x){
				r = mid - 1;
			}else if(v2[mid].fr < x){
				l = mid + 1;
			}else{

				if(v2[mid].sc <= in){
                    				ans = mid;
					l = mid + 1;
				}else{
					r = mid - 1;
				}
			}
		}
		return ans;
	};
    MajorityChecker(vector<int>& arr) {
    	v1.push_back(0);
    	for(auto x : arr){
    		v1.push_back(x);
    	}
     	n = arr.size();
     	val.resize(n << 2);
     	cnt.resize(n << 2); 
     	build(1, 1, n);
     	for(int i = 1; i <= n; i ++){
     		v2.push_back({v1[i], i});
     	}
     	sort(v2.begin(), v2.end(), [](pair<int,int> a, pair<int,int> b){
     		if(a.fr == b.fr){
     			return a.sc < b.sc;
     		}else{
     			return a.fr < b.fr;
     		}
     	});
        // for(int i = 0; i < n; i ++){
        //     cout << v2[i].fr << " " << v2[i].sc << "\n";
        // }
    }
    int query(int left, int right, int threshold) {
    	left ++, right ++;
    	pair<int,int> temp = get(1, left, right, 1, n);
    	if(temp.sc == 0){
    		return -1;
    	}
        // cout << temp.fr << " " <<  temp.sc << " ";
    	int l = find(temp.fr, left), r = find2(temp.fr, right);
        // cout << "L; " <<  left << " R: " << right << " l1: " << l << " r1: " << r << "\n"; 
    	return (r - l + 1) >= threshold ? temp.fr : -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
// https://ac.nowcoder.com/acm/contest/108307/F
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
constexpr int N = 1e6;
vector<int> v1(N + 1), r(N + 1), p(N + 1);
vector<int> W(N << 2 | 1), add1(N << 2 | 1), P(N << 2 | 1), L(N + 1);
signed main(){
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int t = 1;
    cin >> t;
    auto build = [&](auto && f, int i, int l, int r) -> void {
    	add1[i] = W[i] = 0;
    	P[i] = r;
    	if(l != r) {
    		int mid = (l + r) >> 1;
    		f(f, i << 1, l, mid);
    		f(f, i << 1 | 1, mid + 1, r);
    	}
    };
	auto up = [&](int i) -> void {
		if(W[i << 1] >= W[i << 1 | 1]) W[i] = W[i << 1], P[i] = P[i << 1];
		else W[i] = W[i << 1 | 1], P[i] = P[i << 1 | 1];
	};
    auto lazy = [&](int i, int w) -> void {
    	W[i] += w, add1[i] += w;
    };
    auto down = [&](int i) -> void {
    	lazy(i << 1, add1[i]), lazy(i << 1 | 1, add1[i]);
    	add1[i] = 0;
    };
    auto add = [&](auto && f, int i, int l, int r, int L, int R, int w) -> void {
    	if(l >= L && r <= R) return lazy(i, w);
    	down(i);
    	int mid = (l + r) >> 1;
    	if(L <= mid) f(f, i << 1, l, mid, L, R, w);
    	if(R > mid) f(f, i << 1 | 1, mid + 1, r, L, R, w);
    	up(i);
    };
   	while(t --){
		int n;
		cin >> n;
		build(build, 1, 1, n);
    	fill(r.begin(), r.begin() + 1 + n, n + 1);
		for(int i = 1 ; i <= n; i ++) {
			cin >> v1[i];
			if(p[v1[i]]) r[p[v1[i]]] = i;
			p[v1[i]] = i;
		}
		// for(int i = 1; i <= n; i ++) cout << r[i] << " " << p[v1[i]] << "\n";
		int ans = 0, ans_l = 2, ans_r = 3; 
		for(int i = 1; i <= n; i ++) {
			// cout << i << " ";
			if(L[v1[i]]) add(add, 1, 1, n, L[v1[i]], p[v1[i]], -1);
			L[v1[i]] = r[i] + 1;
			// cout << L[v1[i]] << " " << p[v1[i]] << " ";
			add(add, 1, 1, n, L[v1[i]], p[v1[i]], 1);
			// cout << W[1] << "\n";
			if(ans < W[1]) ans = W[1], ans_l = i + 1, ans_r = P[1];
		}
		cout << ans << "\n" << ans_l << " " << ans_r << "\n";
		for(int i = 1; i <= n; i ++) p[v1[i]] = L[v1[i]] = 0;
    }
    return 0;
}

稀疏表ST

**Sparse Table（稀疏表）**是一种高效的数据结构，主要用于 静态数组的区间最值查询（RMQ）。

  • 适用于：查询频繁，修改不需要或很少
  • 查询时间复杂度：O(1)
  • 预处理时间复杂度：O(n log n)

支持的运算

Sparse Table 支持 幂等操作（idempotent operations）：

可以求min() 、max() 、gcd()

不可求lcm() （不满足幂等性）、sum() （不满足幂等性）

核心构建流程（以最大值为例）

  1. 定义
  • st[i][j] 表示从 下标 i 开始，长度为 2^j 的区间最大值
  1. 初始化
1
2
3
for (int i = 1; i <= n; i++) {
    st[i][0] = arr[i];
}
  1. 状态转移
1
2
3
4
5
for (int j = 1; (1 << j) <= n; j++) {
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
        st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    }
}

预处理 log2 表

为什么要提前预处理 log2[]？

查询时需计算区间长度对应的 log2(r - l + 1)，预处理可避免浮点误差和时间浪费

1
2
3
4
log2[0] = -1;
for (int i = 1; i <= n; i++) {
    log2[i] = log2[i >> 1] + 1;
}

区间查询（以最大值为例）

1
2
int k = log2[r - l + 1];
int res = max(st[l][k], st[r - (1 << k) + 1][k]);

这个查询方式的核心是使用两个长度为 2^k 的区间覆盖整个 [l, r] 区间。

Luogu P4155：环形区间覆盖跳跃优化

**目标：**给定一系列区间，在环上查找覆盖长度为 m 所需的最少跳跃次数（倍增思想）

关键用法：

  • st[i][j] 表示从第 i 个区间开始，跳 2^j 步可覆盖到的位置

构建：

1
2
st[i][0] = rightmost reachable from i
st[i][j] = st[st[i][j - 1]][j - 1];

查询：

1
2
3
4
5
6
for (int j = logn; j >= 0; j--) {
    if (v1[st[cur][j]][2] < goal) {
        cur = st[cur][j];
        ans += 1 << j;
    }
}

利用 Sparse Table 进行跳跃优化（倍增思想）

每次跳跃代表一段区间，用于计算覆盖长度最少的路径

模板封装（最值查询）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N = 1e5 + 5, LOG = 20;
int st[N][LOG], log2[N];

void build_st(const vector<int>& a) {
    int n = a.size() - 1;
    log2[0] = -1;
    for (int i = 1; i <= n; i++) {
        st[i][0] = a[i];
        log2[i] = log2[i >> 1] + 1;
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query_max(int l, int r) {
    int k = log2[r - l + 1];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

LCA

最近祖先问题，用于快速查询树中两个节点的最近公共祖先。

采用deep数组和st表

deep数组用于记录深度，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
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
// https://www.luogu.com.cn/problem/P3379
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t = 1;
	// cin >> t;
	while(t --){
		int n, m, root;
		cin >> n >> m >> root;
		vector adj(n + 1, vector<int>());
		for(int i = 1;  i < n; i ++){
			int u, v;
			cin >> u >> v;
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
        // 构建LCA结构
		int n1 = log2(n);
		vector<int> deep(n + 1);
		vector st(n + 1, vector<int>(n1 + 1));
		auto dfs = [&](auto && f, int u, int last, int d) -> void{
			deep[u] = d;
			st[u][0] = last;
			for(int i = 1; i <= n1; i ++){
				st[u][i] = st[st[u][i - 1]][i - 1];
			}
			for(auto v : adj[u]){
				if(v != last){
					f(f, v, u, d + 1);
				}
			}
		};
		dfs(dfs, root, root, 1);
        
		for(int i = 0; i < m; i ++){
			int u, v;
			cin >> u >> v;
			// 查询公共祖先部分部分
            // 先统一高度
			if(deep[u] < deep[v]){
				swap(u, v);
			}
			for(int j = n1; j >= 0; j --){
				if(deep[st[u][j]] >= deep[v]){
					u = st[u][j];
				}
			}
            // 特判
			if(u == v){
				cout << v << "\n";
			}else{
				for(int j = n1; j >= 0; j --){
					if(st[u][j] != st[v][j]){
						u = st[u][j];
						v = st[v][j];
					}
				}
				cout << st[u][0] << "\n";
			}
            //
		}
	}
	return 0;
}

Tarjan

利用并查集来一次dfs就构建好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
50
51
52
53
54
55
56
57
58
// https://www.luogu.com.cn/problem/P3379
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t = 1;
	// cin >> t;
	while(t --){
		int n, m, root;
		cin >> n >> m >> root;
		vector adj(n + 1, vector<int>());
		for(int i = 1, u, v; i < n; i ++){
			cin >> u >> v;
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		vector adj2(m + 1, vector<pair<int, int>>());
		for(int i = 1, u, v; i <= m; i ++){
			cin >> u >> v;
			adj2[u].push_back({v, i});
			adj2[v].push_back({u, i});
		}
		vector<int> fa(n + 1), ans(m + 1);
		vector<bool> vi(n + 1, false);
		for(int i = 0; i <= n; i ++){
			fa[i] = i;
		}
		auto find = [&](auto && f, int x) -> int {
			if(x != fa[x]){
				fa[x] = f(f, fa[x]);
			}
			return fa[x];
		};
		auto tarjin = [&](auto && f, int u, int last) -> void {
			vi[u] = true;
			for(auto v : adj[u]){
				if(v != last){
					f(f, v, u);
				}
			}
			for(auto [v, n1] : adj2[u]){
				if(vi[v]){
					ans[n1] = find(find, v);
				}
			}
			fa[u] = last;
		};
		tarjin(tarjin, root, -1);
		for(int i = 1; i <= m; i ++){
			cout << ans[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
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 5e4 + 1;
int head[N] ,next1[N << 1], to[N << 1];
int size1[N], max1[N];
int cnt1 = 1;
void add (int u, int v){
	next1[cnt1] = head[u];
	to[cnt1] = v;
	head[u] = cnt1 ++;
};
void dfs(int u, int last){
	size1[u] = 1;
	max1[u] = 0;
	for(int ei = head[u], v; ei; ei = next1[ei]){
		v = to[ei];
		if(v != last){
			dfs(v, u);
			max1[u] = max(max1[u], size1[v]);
			size1[u] += size1[v];
		}
	}
	max1[u] = max(max1[u], n - size1[u]);;
};
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	while(t --){
		cin >> n;
		fill(head, head + 1 + n, 0);
		for(int i = 0; i < n - 1; i ++){
			int u, v;
			cin >> u >> v;
			add(u, v);
			add(v, u);
		}
		dfs(1, -1);
		int ans[2];
		int m = 0;
		for(int i = 1; i <= n; i ++){
            // 依照树的重心的定义
			if(max1[i] <= n >> 1){
				ans[m ++] = i;
			}
		}
		for(int i = 0; i < m; i ++){
			cout << ans[i] << " ";
		}
	}
	return 0;
}

当节点有值时，重心的依据是节点权而不是边权。

树的直径

树上任意两点之间最常的简单路径为树的直径，一棵树可以有多条直径，长度相等

两次DFS

适用与无负边树

首先从任意节点 y 开始进行第一次 DFS，到达距离其最远的节点，记为 z，然后再从z 开始做第二次 DFS，到达距离z最远的节点，记为z’，则 $\delta(z,z’)$ 即为树的直径。

显然，如果第一次 DFS 到达的节点z是直径的一端，那么第二次 DFS 到达的节点z’一定是直径的一端。我们只需证明在任意情况下，z必为直径的一端。

定理：在一棵树上，从任意节点y开始进行一次 DFS，到达的距离其最远的节点z必为直径的一端。

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
int n;
cin >> n;
vector<int> head(n + 1, 0), next(n << 1 | 1), to(n << 1 | 1), weight(n << 1 | 1);
int cnt1 = 1;
// 两次DFS
vector<int> dis(n + 1, 0), fa(n + 1), len(n + 1, 0);
int st, en;
auto dfs = [&](auto && f, int u, int last, int val) -> void {
    dis[u] = val;
    fa[u] = last;
    for(int ei = head[u], v, w; ei; ei = next[ei]){
        v = to[ei];
        w = weight[ei];
        if(v != last){
            len[v] = w;
            f(f, v, u, val + w);
        }
    }
};
dfs(dfs, 1, -1, 0);
for(int i = 1, max1 = 0; i <= n; i ++){
    if(max1 < dis[i]){
        max1 = dis[i];
        dis[i] = len[i] = 0;
        st = i;
    }
}
dfs(dfs, st, -1, 0);
for(int i = 1, max1 = 0; i <= n; i ++){
    if(max1 < dis[i]){
        max1 = dis[i];
        en = i;
    }
}
int sum1 = dis[en]; // 直径

树形DP

可用于有负边树

我们记录当1为树的根时，每个节点作为子树的根向下，所能延伸的最长路径长度$d_{1}$与次长路径（与最长路径无公共边）$d_{2}$，那么直径就是对于每一个点，该点的$d_{1}+d_{2}$能取到的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> head1(n + 1, 0), next1(n << 1 | 1), to1(n << 1 | 1), weight(n << 1 | 1);
cnt1 = 1;
vector<int> ans(n + 1)，v1(n + 1);
auto dfs3 = [&](auto && f, int u, int last) -> void {
    ans[u] = 0, v1[u] = 0;
    for(int ei = head1[u], v, w; ei; ei = next1[ei]){
        v = to1[ei], w = weight[ei];
        if(v != last){
            f(f, v, u);
            ans[u] = max(ans[u], v1[u] + v1[v] + w);
            v1[u] = max(v1[u], v1[v] + w);
        }
    }
};
dfs3(dfs3, 1, 0);
int max2 = 0;
for(int i = 1; i <= n; i ++){
    max2 = max(max2, ans[i]);
}

树上差分

在树上对多条路径上的点或者边进行修改时，不能直接便利操作，而是利用差分思想积累信息，最后累加

  • 对于点，路径两端++,两端LCA和LCA的父亲–
  • 对于边，路径两端++,其值可理解为该点到其父亲的边，两端LCA-=2

点差分

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
// https://www.luogu.com.cn/problem/P3128
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
constexpr int N = 5e4, K = 1e5;
vector<int> head(N + 1, 0), next1(N << 1 | 1), to(N << 1 | 1);
vector<int> head2(K + 1, 0), next2(K << 1 | 1), to2(K << 1 | 1), in(K << 1 | 1); 
vector<int> fa_lca(K + 1), lca(K + 1), has(N + 1), fa(N + 1);
int cnt1 = 1, cnt2 = 1;
signed main(){
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int t = 1;
   	 // cin >> t;
	while(t --){ 
		int n, q;
		cin >> n >> q;
		auto add = [&](int u, int v, int i, int f) -> void {
			if(!f) {
				next1[cnt1] = head[u];
				to[cnt1] = v;
				head[u] = cnt1 ++;
			} else {
				next2[cnt2] = head2[u];
				to2[cnt2] = v;
				in[cnt2] = i;
				head2[u] = cnt2 ++;
			}
		};
		for(int i = 1, u, v; i < n; i ++) {
			cin >> u >> v;
			add(u, v, 0, 0);
			add(v, u, 0, 0);
		}
		iota(fa_lca.begin() + 1, fa_lca.begin() + 1 + q, 1);
		auto find = [&](auto && f, int x) -> int {
			if(x != fa_lca[x]) fa_lca[x] = f(f, fa_lca[x]);
			return fa_lca[x];
		};
		vector<pair<int,int>> edges(q);
		for(int i = 0, u, v; i < q; i ++) {
			cin >> u >> v;
			edges[i] = {u, v};
			add(u, v, i, 1);
			add(v, u, i, 1);
		}
		auto tarjan = [&](auto && f, int u, int last) -> void {
			has[u] = 1;
			for(int ei = head[u], v; ei; ei = next1[ei]) {
				v = to[ei];
				if(v != last) f(f, v, u);
			}
			for(int ei = head2[u], v; ei; ei = next2[ei]) {
				v = to2[ei];
				// 注意lca的编号是in[ei]而不是v或者ei
				if(has[v]) lca[in[ei]] = find(find, v);
			}
			fa[u] = last;
			fa_lca[u] = last;
		};
        // 跑lca
		tarjan(tarjan, 1, 0);
		// 差分
		vector<int> ans(n + 1, 0);
		for(int i = 0; i < q; i ++) {
			ans[edges[i].fr] ++, ans[edges[i].sc] ++;
			ans[lca[i]] --, ans[fa[lca[i]]] --;
		}
		auto dfs = [&](auto && f, int u, int last) -> void {
			for(int ei = head[u], v; ei; ei = next1[ei]) {
				v = to[ei];
				if(v != last) {
					f(f, v, u);
					ans[u] += ans[v];
				}
			}
		};
        // 跑差分
		dfs(dfs, 1, 0);
		int max1 = 0;
		for(int i = 1; i <= n; i ++) {
			// cout << i << " " << ans[i] << "\n";
			max1 = max(max1, ans[i]);
		}
		cout << max1 << "\n";
    }
    return 0;
}

边差分

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
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
// https://www.luogu.com.cn/problem/P2680
#include <bits/stdc++.h>
using namespace std;

#define fr first
#define sc second

signed main() {
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int t = 1; // 题目只有一组数据
    while (t--) { 
        int n, m;
        cin >> n >> m;

        // 树的邻接表存储
        vector<int> head(n + 1, 0), next1(n << 1 | 1), to(n << 1 | 1), wei(n << 1 | 1);
        // 查询图（用于 Tarjan 离线 LCA）
        vector<int> head2(n + 1, 0), next2(m << 1 | 1), to2(m << 1 | 1), in(m << 1 | 1);

        // 各种辅助数组
        vector<int> len(n + 1), has(n + 1, 0), fa_lca(n + 1), lca(m), cost(m);
        int cnt1 = 1, cnt2 = 1;

        // 加边（树边）
        auto add = [&](int u, int v, int w) {
            next1[cnt1] = head[u];
            to[cnt1] = v;
            wei[cnt1] = w;
            head[u] = cnt1++;
        };

        // 加边（查询边）
        auto add2 = [&](int u, int v, int i) {
            next2[cnt2] = head2[u];
            to2[cnt2] = v;
            in[cnt2] = i;
            head2[u] = cnt2++;
        };

        // 读入树
        for (int i = 1, u, v, w; i < n; i++) {
            cin >> u >> v >> w;
            add(u, v, w);
            add(v, u, w);
        }

        int max1 = 0; // 最大路径长度
        vector<array<int, 2>> edges(m);
        
        // 读入运输任务
        for (int i = 0; i < m; i++) {
            cin >> edges[i][0] >> edges[i][1];
            add2(edges[i][0], edges[i][1], i);
            add2(edges[i][1], edges[i][0], i);
        }

        // 并查集 find
        auto find = [&](auto &&f, int x) -> int {
            if (x != fa_lca[x]) fa_lca[x] = f(f, fa_lca[x]);
            return fa_lca[x];
        };

        iota(fa_lca.begin(), fa_lca.end(), 0); // 初始化并查集

        // Tarjan 离线 LCA
        auto tarjan = [&](auto &&f, int u, int last, int w) -> void {
            len[u] = w;    // 从根到 u 的距离
            has[u] = 1;    // 标记已访问

            // 遍历树的子节点
            for (int ei = head[u], v; ei; ei = next1[ei]) {
                v = to[ei];
                if (v != last) f(f, v, u, w + wei[ei]);
            }

            // 遍历与 u 有关的查询
            for (int ei = head2[u], v; ei; ei = next2[ei]) {
                v = to2[ei];
                if (has[v]) {
                    lca[in[ei]] = find(find, v); // 找到 LCA
                    // 路径长度 = len[u] + len[v] - 2 * len[lca]
                    cost[in[ei]] = len[v] + len[u] - 2 * len[lca[in[ei]]];
                    max1 = max(max1, cost[in[ei]]);
                }
            }

            fa_lca[u] = last; // 回溯并查集父节点
        };

        tarjan(tarjan, 1, 0, 0); // 从根节点 1 开始

        // 二分答案
        int l = 0, r = max1, ans = 0, mid;
        vector<int> num(n + 1);
        int cnt, need;

        // 检查函数（判断是否能在限制 x 下完成任务）
        auto cf = [&](auto &&f, int u, int last, int w) -> bool {
            for (int ei = head[u], v; ei; ei = next1[ei]) {
                v = to[ei];
                if (v != last) {
                    if (f(f, v, u, wei[ei])) return 1;
                    num[u] += num[v];
                }
            }
            return num[u] == cnt && w >= need; // 判断是否找到关键边
        };

        auto F = [&](int x) -> bool {
            cnt = 0;
            need = max1 - x;
            fill(num.begin(), num.end(), 0);

            // 标记需要减少的路径
            for (int i = 0; i < m; i++) {
                if (cost[i] > x) {
                    num[edges[i][0]]++;
                    num[edges[i][1]]++;
                    num[lca[i]] -= 2;
                    cnt++;
                }
            }
            return !cnt || cf(cf, 1, 0, 0);
        };

        while (l <= r) {
            mid = (l + r) >> 1;
            if (F(mid)) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        cout << ans << "\n";
    }
    return 0;
}

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
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
// https://www.luogu.com.cn/problem/P2680
#include <bits/stdc++.h>
using namespace std;

#define fr first
#define sc second

signed main() {
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int t = 1;
    while (t--) {
        int n, m;
        cin >> n >> m;

        // 树的邻接表
        vector<int> head(n + 1, 0), next1(n << 1 | 1), to(n << 1 | 1), wei(n << 1 | 1);
        int cnt1 = 1;

        auto add = [&](int u, int v, int w) -> void {
            next1[cnt1] = head[u];
            to[cnt1] = v;
            wei[cnt1] = w;
            head[u] = cnt1++;
        };

        // 读入树
        for (int i = 1, u, v, w; i < n; i++) {
            cin >> u >> v >> w;
            add(u, v, w);
            add(v, u, w);
        }

        int n1 = log2(n);
        vector<int> deep(n + 1, 0); // 深度
        vector st_lca(n + 1, vector<int>(n1 + 1)); // 倍增父节点表
        vector st_len(n + 1, vector<int>(n1 + 1)); // 对应的边权和

        // 预处理 DFS
        auto dfs = [&](auto &&f, int u, int last, int d, int w) -> void {
            deep[u] = d;
            st_lca[u][0] = last;
            st_len[u][0] = w;

            // 倍增表更新
            for (int i = 1; i <= n1; i++) {
                st_lca[u][i] = st_lca[st_lca[u][i - 1]][i - 1];
                st_len[u][i] = st_len[u][i - 1] + st_len[st_lca[u][i - 1]][i - 1];
            }

            for (int ei = head[u], v; ei; ei = next1[ei]) {
                v = to[ei];
                if (v != last) f(f, v, u, d + 1, wei[ei]);
            }
        };

        dfs(dfs, 1, 0, 1, 0);

        vector<array<int, 4>> edges(m);
        int max1 = 0;

        // LCA 查询
        auto lca = [&](int u, int v, int i1) -> void {
            if (deep[u] < deep[v]) swap(u, v);
            int len = 0;

            // 先让 u 和 v 到同一深度
            for (int i = n1; i >= 0; i--)
                if (deep[st_lca[u][i]] >= deep[v])
                    len += st_len[u][i], u = st_lca[u][i];

            if (u == v) goto t1;

            // 同时向上跳
            for (int i = n1; i >= 0; i--) {
                if (st_lca[u][i] != st_lca[v][i]) {
                    len += st_len[u][i] + st_len[v][i];
                    u = st_lca[u][i];
                    v = st_lca[v][i];
                }
            }

            // 最后一步
            len += st_len[u][0] + st_len[v][0];
            u = st_lca[u][0];

            t1:;
            max1 = max(max1, len);
            edges[i1][2] = len;
            edges[i1][3] = u; // 存储 LCA
        };

        // 读入任务并计算路径长度
        for (int i = 0; i < m; i++) {
            cin >> edges[i][0] >> edges[i][1];
            lca(edges[i][0], edges[i][1], i);
        }

        // 二分答案
        int l = 0, r = max1, ans = 0, mid;
        vector<int> num(n + 1);
        int cnt, need;

        auto cf = [&](auto &&f, int u, int last, int w) -> bool {
            for (int ei = head[u], v; ei; ei = next1[ei]) {
                v = to[ei];
                if (v != last) {
                    if (f(f, v, u, wei[ei])) return 1;
                    num[u] += num[v];
                }
            }
            return num[u] == cnt && w >= need;
        };

        auto F = [&](int x) -> bool {
            cnt = 0;
            need = max1 - x;
            fill(num.begin(), num.end(), 0);

            for (int i = 0; i < m; i++) {
                if (edges[i][2] > x) {
                    num[edges[i][0]]++;
                    num[edges[i][1]]++;
                    num[edges[i][3]] -= 2;
                    cnt++;
                }
            }
            return !cnt || cf(cf, 1, 0, 0);
        };

        while (l <= r) {
            mid = (l + r) >> 1;
            if (F(mid)) ans = mid, r = mid - 1;
            else l = mid + 1;
        }

        cout << ans << "\n";
    }
    return 0;
}

树上换根

在树上做DP时，很多时候与根有关，如果把根从父亲换到儿子，答案可能按照同样的计算方法通过可推导公式进行变换，通常是dfs一次先算出某一个节点的值并且同时构造出必要信息，第二次dfs分为直接计算答案和构造前后缀信息。通常的时间复杂度为O(n)

增量换根公式（轻量）

仅根据第一次dfs时构造的变量，通过第二次遍历按节点传递答案并利用变量进行计算

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
// https://codeforces.com/problemset/problem/1187/E
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 2e5;
vector<int> head(N + 1), next1(N << 1 | 1), to(N << 1 | 1), S(N + 1);
int cnt1;
signed main() {
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int t = 1;
    // 建图函数（链式前向星存储）
    auto add = [&](int u, int v) {
        next1[cnt1] = head[u];
        to[cnt1] = v;
        head[u] = cnt1++;
    };
    while (t--) {
        int n;
        cin >> n;
        cnt1 = 1;
        fill(head.begin(), head.begin() + 1 + n, 0);
        // 输入边
        for (int i = 1, u, v; i < n; i++) cin >> u >> v, add(u, v), add(v, u);
        int val1 = 0; // 以 1 为根时所有子树大小之和
        // 第一次 DFS：计算子树大小和 val1
        auto dfs = [&](auto&& f, int u, int fa) -> void {
            S[u] = 1;
            for (int ei = head[u], v = to[ei]; ei; ei = next1[ei], v = to[ei]) {
                if (v != fa) f(f, v, u), S[u] += S[v];
            }
            val1 += S[u];
        };
        dfs(dfs, 1, 0);
        // 第二次 DFS：换根，动态维护答案
        auto dfs2 = [&](auto&& f, int u, int fa, int val) -> int {
            int val2 = val; // 当前答案
            for (int ei = head[u], v = to[ei]; ei; ei = next1[ei], v = to[ei]) {
                if (v != fa) {
                    // 换根公式：val + n - 2 * S[v]
                    val2 = max(val2, f(f, v, u, val + n - (S[v] << 1)));
                }
            }
            return val2;
        };

        cout << dfs2(dfs2, 1, 0, val1) << "\n";
    }
    return 0;
}

前后缀合并

当每个点的 DP 来自“合并所有子树的贡献”，且这个合并满足结合律（如 max/sum/min 的组合），就可以用前缀/后缀把“除某个儿子外的其余贡献”在 O(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
// https://www.luogu.com.cn/problem/P6419
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 5e5;
// 链式前向星存图
vector<int> head(N + 1), next1(N << 1 | 1), to(N << 1 | 1), wei(N << 1 | 1);
int cnt1;
// DP 数组
vector<int> sum_in(N + 1), sum_out(N + 1);
vector<int> max_in(N + 1), max_in2(N + 1), cho(N + 1), max_out(N + 1), has(N + 1);
signed main() {
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    auto add = [&](int u, int v, int w) -> void {
        next1[cnt1] = head[u];
        to[cnt1] = v;
        wei[cnt1] = w;
        head[u] = cnt1++;
    };
    while (t--) {
        int n, k;
        cin >> n >> k;
        cnt1 = 1;
        fill(head.begin(), head.begin() + 1 + n, 0);
        // 输入边
        for (int i = 1, u, v, w; i < n; i++) cin >> u >> v >> w, add(u, v, w), add(v, u, w);
        // 输入特殊节点
        for (int i = 0, x; i < k; i++) cin >> x, has[x] = 1;
        // 第一次 DFS：自底向上
        auto dfs = [&](auto&& f, int u, int fa) -> void {
            max_in[u] = max_in2[u] = sum_in[u] = 0;
            for (int ei = head[u], v = to[ei]; ei; ei = next1[ei], v = to[ei]) {
                if (v != fa) {
                    f(f, v, u);
                    // 累计子树代价
                    sum_in[u] += sum_in[v] + (has[v] || sum_in[v]) * (wei[ei] << 1);
                    // 更新最长路径
                    int w = max_in[v] + (has[v] || sum_in[v]) * wei[ei];
                    if (w > max_in[u]) {
                        cho[u] = v;
                        max_in2[u] = max_in[u];
                        max_in[u] = w;
                    } else if (w > max_in2[u]) max_in2[u] = w;
                }
            }
        };
        dfs(dfs, 1, 0);
        // 第二次 DFS：自顶向下
        auto dfs2 = [&](auto&& f, int u, int fa) -> void {
            for (int ei = head[u], v = to[ei]; ei; ei = next1[ei], v = to[ei]) {
                if (v != fa) {
                    max_out[v] = max_out[u];
                    if (cho[u] == v) // 如果走的是重儿子，用次优的 max_in2
                        max_out[v] = max(max_out[v] + wei[ei], max_in2[u] + wei[ei]);
                    else
                        max_out[v] = max(max_out[v] + wei[ei], max_in[u] + wei[ei]);
                    // sum_out 的计算
                    sum_out[v] = (sum_in[u] - sum_in[v] + sum_out[u]) 
                               + (sum_in[v] == 0 && !has[v]) * wei[ei] * 2;
                    // 特殊情况：该边唯一连接所有特殊点时，去掉重复
                    if (sum_in[u] == sum_in[v] + (wei[ei] << 1) && !sum_out[u])
                        max_out[v] = sum_out[v] = 0;
                    f(f, v, u);
                }
            }
        };
        dfs2(dfs2, 1, 0);
        // 输出答案
        for (int i = 1; i <= n; i++) {
            cout << sum_in[i] + sum_out[i] - max(max_in[i], max_out[i]) << "\n";
        }
    }
    return 0;
}

AVL树

AVL树（英语：Adelson-Velsky and Landis tree）是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(log⁡n)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者格奥尔吉·阿杰尔松-韦利斯基和叶夫根尼·兰迪斯，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。

一种有序表数据结构

定义

  • 平衡二叉搜索树，左右子树高度差 ≤ 1
  • 插入、删除、查询操作复杂度：O(log n)

节点信息

  • key：值
  • count：重复值频次
  • height：子树高度
  • size：子树大小（统计排名、k-th）
  • left/right：左右子节点

核心函数

  • up(i)：更新 size & height
  • maintain(i)：检测平衡并旋转
  • rotateL / rotateR：左旋 / 右旋

插入

  1. 按 BST 规则递归
  2. 命中相等 → count++
  3. 回溯时 up + maintain

删除

  1. count > 1 → count–
  2. 无子 → 直接删
  3. 单子 → 用唯一子替代
  4. 双子 → 找右子树最左节点替代，删掉它
  5. 回溯 up + maintain

查询

  • rank(x)：小于 x 的元素数 + 1
  • index(k)：第 k 小，靠 size 判断走向
  • pre(x)：小于 x 的最大值
  • suf(x)：大于 x 的最小值

旋转类型

  • LL：右旋
  • RR：左旋
  • LR：先左旋子树，再右旋
  • RL：先右旋子树，再左旋
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
// https://www.luogu.com.cn/problem/P3369
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
constexpr int N = 1e5;
// 节点信息
vector<int> key(N + 1), height(N + 1), left1(N + 1), right1(N + 1), size1(N + 1), count1(N + 1);
int head, cnt1; // head: 根节点编号, cnt1: 节点总数
signed main(){
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int t = 1;
	// 更新节点信息：子树大小 + 高度
	auto up = [&](int i) {
		size1[i] = size1[left1[i]] + size1[right1[i]] + count1[i];
		height[i] = max(height[left1[i]], height[right1[i]]) + 1;
	};
	// 左旋
	auto rotate_l = [&](int i) -> int {
		int r = right1[i];
		right1[i] = left1[r];
		left1[r] = i;
		up(i);
		up(r);
		return r;
	};
	// 右旋
	auto rotate_r = [&](int i) -> int {
		int l = left1[i];
		left1[i] = right1[l];
		right1[l] = i;
		up(i);
		up(l);
		return l;
	};
	// 保持平衡：检查并旋转
	auto maintain = [&](int i) -> int {
		int ln = height[left1[i]], rn = height[right1[i]];
		if(ln - rn > 1) { // 左子树更高
			if(height[left1[left1[i]]] >= height[right1[left1[i]]]) 
				i = rotate_r(i); // LL
			else 
				left1[i] = rotate_l(left1[i]), i = rotate_r(i); // LR
		} else if(rn - ln > 1) { // 右子树更高
			if(height[right1[right1[i]]] >= height[left1[right1[i]]]) 
				i = rotate_l(i); // RR
			else 
				right1[i] = rotate_r(right1[i]), i = rotate_l(i); // RL
		}
		return i;
	};
	// 插入节点 x
	auto add = [&](auto && f, int i, int x) -> int {
		if(i == 0) { // 新建节点
			key[++cnt1] = x;
			count1[cnt1] = size1[cnt1] = height[cnt1] = 1;
			left1[cnt1] = right1[cnt1] = 0;
			return cnt1;
		}
		if(x == key[i]) count1[i] ++;
		else if(x < key[i]) left1[i] = f(f, left1[i], x);
		else right1[i] = f(f, right1[i], x);
		up(i);
		return maintain(i);
	};
	// 删除子树中的最左节点
	auto removel = [&](auto && f, int i, int x) -> int {
		if(i == x) return right1[i];
		else {
			left1[i] = f(f, left1[i], x);
			up(i);
			return maintain(i);
		}
	};
	// 删除值为 x 的节点（若存在）
	auto remove = [&](auto && f, int i, int x) -> int {
		if(x < key[i]) left1[i] = f(f, left1[i], x);
		else if(x > key[i]) right1[i] = f(f, right1[i], x);
		else {
			count1[i] --; // 多次出现，减频次
			if(!count1[i]) { // 频次为 0 -> 删除节点
				if(!left1[i] && !right1[i]) return 0;       // 无子
				else if(!left1[i] && right1[i]) i = right1[i]; // 只有右子
				else if(left1[i] && !right1[i]) i = left1[i]; // 只有左子
				else { // 两个子
					int l = right1[i];
					while(left1[l]) l = left1[l]; // 找右子树最左节点
					right1[i] = removel(removel, right1[i],  l);
					right1[l] = right1[i];
					left1[l] = left1[i];
					i = l;
				}
			}
		}
		up(i);
		return maintain(i);
	};
	// 统计小于 x 的元素个数
	auto small = [&](auto && f, int i, int x) -> int {
		if(i == 0) return 0;
		if(key[i] >= x) return f(f, left1[i], x);
		else return count1[i] + f(f, right1[i], x) + size1[left1[i]];
	};
	// 查询第 x 小的数
	auto index = [&](auto && f, int i, int x) -> int {
		if(size1[left1[i]] >= x) return f(f, left1[i], x);
		else if(size1[left1[i]] + count1[i] < x) 
			return f(f, right1[i], x - size1[left1[i]] - count1[i]);
		else return key[i];
	};
	// 查询前驱：小于 x 的最大值
	auto pre = [&](auto && f, int i, int x) -> int {
		if(i == 0) return INT_MIN;
		if(key[i] >= x) return f(f, left1[i], x);
		else return max(key[i], f(f, right1[i], x));
	};
	// 查询后继：大于 x 的最小值
	auto suf = [&](auto && f, int i, int x) -> int {
		if(i == 0) return INT_MAX;
		if(key[i] <= x) return f(f, right1[i], x);
		else return min(key[i], f(f, left1[i], x));
	};
	while(t --) { 
		int n;
		cin >> n;
		cnt1 = head = 0;
		for(int i = 0, op, x; i < n; i ++) {
			cin >> op >> x;
			if(op == 1) head = add(add, head, x);                // 插入 x
			else if(op == 2) {                                   // 删除 x
				if(small(small, head, x) != small(small, head, x + 1)) 
					head = remove(remove, head, x);
			}
			else if(op == 3) cout << small(small, head, x) + 1 << "\n"; // 查询排名
			else if(op == 4) cout << index(index, head, x) << "\n";     // 查询第 k 小
			else if(op == 5) cout << pre(pre, head, x) << "\n";         // 前驱
			else cout << suf(suf, head, x) << "\n";                     // 后继
		}
	}
    return 0;
}

笛卡尔树

笛卡尔树是一种二叉树，每一个节点由一个键值二元组 (k,w) 构成。要求 k 满足二叉搜索树的性质，而 w 满足堆的性质。如果笛卡尔树的 k,w 键值确定，且 k 互不相同，w 也互不相同，那么这棵笛卡尔树的结构是唯一的

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
// https://ac.nowcoder.com/acm/contest/108306/G
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
constexpr int mod = 998244353;
constexpr int N = 1e6;
// 单调栈建树相关
int head, tot;
vector<int> L(N + 1), R(N + 1), S(N + 1), H(N + 1), st(N + 1);
// 组合数预处理
vector<int> fac(N + 1), inv(N + 1);
signed main(){
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int t = 1;
    cin >> t;
    // 预处理阶乘与逆元：fac[i] = i!，inv[i] = (i!)^{-1}
    fac[0] = 1;
    for(int i = 1; i <= N; i ++) fac[i] = fac[i - 1] * i % mod;
    // 快速幂
    auto power = [&](int x, int n) -> int {
        int ans = 1;
        while(n) {
            if(n & 1) ans = ans * x % mod;
            x = x * x % mod;
            n >>= 1;
        }
        return ans;
    };
    // 费马小定理求逆阶乘
    inv[N] = power(fac[N], mod - 2);
    for(int i = N - 1; i >= 0; i --) inv[i] = inv[i + 1] * (i + 1) % mod;
    while(t --){
        int n;
        cin >> n;
        // 初始化左右儿子指针
        fill(L.begin(), L.begin() + 1 + n, 0);
        fill(R.begin(), R.begin() + 1 + n, 0);
        vector<int> v1(n + 1);
        int min1 = 1e18;
        // 读入并记录全局最小值位置（Cartesian Tree 的根）
        for(int i = 1; i <= n; i ++) {
            cin >> v1[i];
            if(v1[i] < min1) min1 = v1[i], head = i;
        }
        // 用单调递增栈构造“最小值 Cartesian Tree”
        // 规则（经典做法）：
        // - 弹出所有比当前值大的栈顶；
        // - 栈顶（若存在）作为当前结点的左/右关系的一端；
        // - 维护 L、R 为每个结点的左右儿子。
        tot = 0;
        for(int i = 1, now; i <= n; i ++) {
            now = tot;
            while(tot && v1[i] < v1[st[tot]]) tot --;   // 保持单调（严格递增）
            if(tot) R[st[tot]] = i;                     // 栈顶的右儿子是当前 i
            if(now > tot) L[i] = st[tot + 1];           // 被弹出的第一个成为 i 的左儿子
            st[++tot] = i;
        };
        // 组合数 C(k, n) = nCk，这里参数名是 (up, down)，实际返回的是 C(up, down)
        auto C = [&](int up, int down) -> int {
            return fac[down] * inv[up] % mod * inv[down - up] % mod;
        };
        // DFS：
        // - 先递归儿子，得到子树规模 S[*]
        // - 本结点贡献：C(d, d+S[i]-1)（等价于 C(d+S[i]-1, d)）
        // - 返回子树总答案之和
        auto dfs = [&](auto && f, int i, int d) -> int {
            int ans = 0;
            if(!L[i] && !R[i]) {
                S[i] = 1;                               // 叶子
            } else {
                if(L[i]) ans = (ans + f(f, L[i], d + 1)) % mod;
                if(R[i]) ans = (ans + f(f, R[i], d + 1)) % mod;
                S[i] = S[L[i]] + S[R[i]] + 1;           // 子树规模
            }
            ans = (ans + C(d, d + S[i] - 1)) % mod;     // 加上当前结点的组合贡献
            return ans;
        };
        // 最后 +1 一般用于把“空集/空方案”等计入答案（具体取决于题意）
        cout << (dfs(dfs, head, 1) + 1) % mod<< "\n";
    }
    return 0;
}

并查集

对数据进行分类

1
2
3
4
5
6
7
8
9
// 递归找祖先
int find(int x){
    if(x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
void U(int x, int y){
    fa[find(x)] = find(y);
    find(x);
}

最后使用前记得统一根，即便利一遍时操作find

常见二分

加速查询

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
#include<bits/stdc++.h>
using namespace std;
vector<int> v1 = {0, 1, 2, 3 ,4, 5};
// 最小大于等于
int F1(int x){
    int r = v1.size() - 1;
    int l = 0;
    int ans, mid;
    while(l <= r){
        mid = (l + r) >> 1;
        if(x >= v1[mid]){
            ans = mid;
            l = mid - 1;
        }
        else r = mid - 1;
    }
    return r;
}
// 最小大于
int F2(int x){
    int r = v1.size() - 1;
    int l = 0;
    int ans, mid;
    while(l <= r){
        mid = (l + r) >> 1;
        if(x > v1[mid]){
            ans = mid;
            l = mid - 1;
        }
        else r = mid - 1;
    }
    return r;
}
// 最长递增子序列
int F1(int x, vector<int> & v){
    int r = v1.size() - 1;
    int l = 0;
    int mid;
    int ans = -1;
    while(l <= r){
        mid = (l + r) >> 1;
        if(x > v[mid]) l = mid + 1;
        else{
            r = mid - 1;
            ans = mid;
        }
    }
    return ans;
}
// 最长递减子序列
int F2(int x, vector<int> & v){
    int r = v1.size() - 1;
    int l = 0;
    int mid;
    int ans = -1;
    while(l <= r){
        mid = (l + r) >> 1;
        if(x < v[mid]) l = mid + 1;
        else{
            r = mid - 1;
            ans = mid;
        }
    }
    return ans;
}

三分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// F视具体情况
ll ternary_search(ll l, ll r) {
    while (r - l > 3) {
        ll m1 = l + (r - l) / 3;
        ll m2 = r - (r - l) / 3;
        if (F(m1) <= F(m2)) {
            r = m2;
        } else {
            l = m1;
        }
    }
    ll best = 1e9;
    // 最后暴力求解
    for (ll i = l; i <= r; i++) {
        if (F(i) < F(best)) {
            best = i;
        }
    }
    return best;
}

博弈论（SG定理）

所有相同子游戏最终sg异或结果为0则先手必败，不为零则先手必胜，sg为从某一节点开始，到最大限度往前便利后的第一个没有出现的自然数。

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
#include<bits/stdc++.h>
using namespace std;
// 计算集合中缺失的最小非负整数（mex函数）
int mex(const set<int>& s) {
    int m = 0;
    while (s.count(m)) m++;
    return m;
}
int main(){
    int n;
    cout << "请输入石子堆的石子数量：";
    cin >> n;
    // 允许的操作：每次可以取 1、2 或 3 个石子
    vector<int> moves = {1, 2, 3};
    // 动态规划数组，sg[i] 表示当前石子数量为 i 时的 SG 值
    vector<int> sg(n+1, 0);
    sg[0] = 0; // 没有石子时，SG值为0
    // 计算每个状态的 SG 值
    for (int i = 1; i <= n; i++){
        set<int> nextSG;
        // 对每一种允许的走法，计算下一状态的 SG 值
        for (int move : moves) {
            if (i - move >= 0) {
                nextSG.insert(sg[i - move]);
            }
        }
        sg[i] = mex(nextSG);
    }
    cout << "状态 " << n << " 的 SG 值为：" << sg[n] << "\n";
    if(sg[n] != 0)
        cout << "先手必胜\n";
    else
        cout << "后手必胜\n";
    return 0;
}

乘积最大子数组

保留乘积最小的结果以准备触底反弹

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> v1;
int min1 = 1;
int max1 = 1;
int ans1 = INT_MIN;
int pre1 = 1;
int pre2 = 1;
for(int i = 0; i < v1.size(); i ++){
    max1 = max({v1[i], pre1 * v1[i], pre2 * v1[i]});
    min1 = min({v1[i], pre1 * v1[i], pre2 * v1[i]});
    pre1 = max1;
    pre2 = min1;
    ans1 = max(ans1, max1);
}
cout << ans1 << "\n";

栈

单调栈

求某一侧第一个 大于或者小于其的数

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;
#define ll long long
// 求右边第一个比其大的数
void solve(vector<int> & v1, int n){
    vector<int> ans(n + 1);
    int size=v1.size();
    stack<int> s1;
    for(int i=0;i<size;i++){
        while(!s1.empty() && v1[i] > v1[s1.top()]){
            ans[s1.top()] = i+1;
            s1.pop();
        }
        s1.push(i);
    }
    for(int i=0;i<size;i++){
        cout<<ans[i]<<' ';
    }cout<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    vector<int> v1;
    for(int i=0;i<n;i++){
        cin>>v1[i];
    }
    solve(v1, 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
#include <bits/stdc++.h>
using namespace std;
class FreqStack {
private:
    unordered_map<int,vector<int>> s1;
    unordered_map<int,int> t1;
    int max1;
public:
    FreqStack() {
        max1=0;
    }
    void push(int val) {
        t1[val]++;
        s1[t1[val]].push_back(val);
        max1=t1[val]>max1?t1[val]:max1;
    }
    /*
    int pop() 删除并返回堆栈中出现频率最高的元素。
	如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。
    */
    int pop() {
        int ans=s1[max1].back();
        s1[t1[ans]--].pop_back();
        if(t1[ans]==0){
            t1.erase(ans);
        }
        if(s1[max1].empty()){
            max1--;
            s1.erase(max1+1);
        }return ans;
    }
};

堆

动态堆寻找中位数

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
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5;
int n;               // 操作次数
string op;            // 输入的操作命令
int size1 = 0;        // 当前栈的大小
int minsize = 0;      // 小根堆中元素的数量
int maxsize = 0;      // 大根堆中元素的数量
vector<int> stack1(N);    // 用于模拟栈，存储所有插入的数字
priority_queue<int, vector<int>, greater<int>> minheap;  // 小根堆，用于存储大于等于中位数的数
priority_queue<int> maxheap;  // 大根堆，用于存储小于等于中位数的数
// 用于延迟删除的映射：记录需要从堆中删除但还未实际删除的数字及其次数
unordered_map<int, int> delayed;  
template <typename T>
void prune(T &heap) {
    // 当堆不为空时，检查堆顶元素是否在延迟删除映射中
    while (!heap.empty()) {
        int num = heap.top();
        if (delayed.count(num)) {  // 如果堆顶元素需要被删除
            delayed[num]--;        // 延迟删除计数减一
            if (delayed[num] == 0)
                delayed.erase(num);  // 如果次数为0则从映射中删除
            heap.pop();              // 弹出堆顶元素
        } else {
            break; // 堆顶元素未被延迟删除，退出循环
        }
    }
}
void balance() {
    // 如果大根堆的元素比小根堆多超过1个，则将大根堆的堆顶移动到小根堆中
    if (maxsize > minsize + 1) {
        minheap.push(maxheap.top());
        maxheap.pop();
        minsize++;
        maxsize--;
        prune(maxheap);  // 清理大根堆堆顶可能存在的延迟删除元素
    }
    // 如果大根堆的元素数目小于小根堆，则将小根堆的堆顶移动到大根堆中
    else if (maxsize < minsize) {
        maxheap.push(minheap.top());
        minheap.pop();
        maxsize++;
        minsize--;
        prune(minheap);  // 清理小根堆堆顶可能存在的延迟删除元素
    }
}
void erase(int num) {
    // 标记该数字需要延迟删除
    delayed[num]++;
    if (num <= maxheap.top()) {
        maxsize--;
        // 如果待删除数字恰好是大根堆堆顶，则立即清理
        if (num == maxheap.top()) {
            prune(maxheap);
        }   
    } else {
        minsize--;
        // 如果待删除数字恰好是小根堆堆顶，则立即清理
        if (num == minheap.top())
            prune(minheap);
    }
    balance();
}
void solve(void) {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> op;
        // peek
        if (op[1] == 'e') {
            if (size1 == 0)
                cout << "Invalid" << "\n";
            else
                // 中位数为大根堆的堆顶
                cout << maxheap.top() << "\n";
        } 
        // pop
        else if (op[1] == 'o') {
            if (size1 == 0)
                cout << "Invalid" << "\n";
            else {
                // 输出栈顶元素
                cout << stack1[size1 - 1] << "\n";
                // 删除栈顶元素，并在堆中延迟删除对应数字
                erase(stack1[--size1]);
            }
        } 
        // push
        else {
            cin >> stack1[size1++];
            // 如果大根堆为空，则直接插入到大根堆中
            if (maxsize == 0) {
                maxheap.push(stack1[size1 - 1]);
                maxsize++;
                continue;
            }
            // 根据新插入数字与当前中位数比较，决定放入哪个堆
            if (stack1[size1 - 1] > maxheap.top()) {
                minheap.push(stack1[size1 - 1]);
                minsize++;
            } else {
                maxheap.push(stack1[size1 - 1]);
                maxsize++;
            }
            // 保持两个堆的平衡
            balance();
        }
    }
}
int main() {
    cin.tie(0) -> ios::sync_with_stdio(0);
    int t; 
    while (t--) {
        solve();
    }
    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
#include <bits/stdc++.h>
using namespace std;
// 向堆中插入新元素，使其满足大顶堆性质
void heapInsert(int arr[], int i) {
    while(arr[i] > arr[(i-1)/2]) {
        swap(arr[i], arr[(i-1)/2]);
        i = (i-1)/2;
    }
}
// 堆化：从下标 i 开始向下调整，使子树满足大顶堆性质，size 为堆的大小
void heapify(int arr[], int i, int size) {
    int l = i * 2 + 1;
    int maxIdx;  // 保存左右孩子中较大值的下标
    int idx;     // 保存父节点与较大孩子中较大者的下标
    while(l < size) {
        // 在左右孩子中选择较大者
        maxIdx = (l + 1 < size && arr[l+1] > arr[l]) ? l + 1 : l;
        // 选择父节点与较大孩子中较大者
        idx = (arr[i] > arr[maxIdx]) ? i : maxIdx;
        if(idx == i) break;
        else {
            swap(arr[i], arr[idx]);
            i = idx;
            l = i * 2 + 1;
        }
    }
}
int heapPop(int arr[], int &size) {
    if(size <= 0) {
        return -1;
    }
    int top = arr[0];             // 保存堆顶元素
    swap(arr[0], arr[size - 1]);    // 将堆顶与最后一个元素交换
    size--;                       // 删除最后一个元素
    heapify(arr, 0, size);        // 从顶端重新调整堆
    return top;
}

扫描线

利用扫描思想平移某一个轴时，加工另一个轴的信息来一边扫过去就能解决问题

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
// https://www.luogu.com.cn/problem/P5490
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
signed main(){
	cin.tie(0) -> ios::sync_with_stdio(0);
	int t = 1;
	// cin >> t;
	while(t --){
		int n;
		cin >> n;
		vector<int> v2 = {-2};
		vector<array<int, 4>> v1;
		for(int i = 0; i < n; i ++){
			int x1, y1, x2, y2;
			cin >> x1 >> y1 >> x2 >> y2;
			v2.push_back(y1);
			v2.push_back(y2);
			v1.push_back({x1, y1, y2, 1});
			v1.push_back({x2, y1, y2, -1});
		}
		sort(v2.begin() + 1, v2.end());
		int m = 1;
		for(int i = 2; i < v2.size(); i ++){
			if(v2[i] != v2[m]){
				v2[++ m] = v2[i];
			}
		}
		v2.push_back(v2[m]);
		auto find = [&](int x) -> int {
			int l = 1, r = m;
			int mid, ans = -1;
			while(l <= r){
				mid = (l + r) >> 1;
				if(v2[mid] >= x){
					ans = mid;
					r = mid - 1;
				}else{
					l = mid + 1;
				}
			}
			return ans;
		};
		vector<int> sum1(m << 4), cnt1(m << 4), cover(m << 4);
		auto build = [&](auto && f, int i, int l, int r) -> void {
			if(l < r){
				int mid = (l + r) >> 1;
				f(f, i << 1, l, mid);
				f(f, i << 1 | 1, mid + 1, r);
			}
			cover[i] = v2[r + 1] - v2[l];
			sum1[i] = cnt1[i] = 0;
		};
		build(build, 1, 1, m);
		auto up = [&](int i) {
			if(cnt1[i] > 0){
				sum1[i] = cover[i]; 
			}else{
				sum1[i] = sum1[i << 1] + sum1[i << 1 | 1];
			}
		};
		auto set = [&](auto && f, int i, int bl, int br, int val, int l, int r) -> void {
			if(bl <= l && br >= r){
				cnt1[i] += val;
			}else{
				int mid = (l + r) >> 1;
				if(bl <= mid){
					f(f, i << 1, bl, br, val, l, mid);
				}
				if(br > mid){
					f(f, i << 1 | 1, bl, br, val, mid + 1, r);
				}     
			}
			up(i);
		};
		sort(v1.begin(), v1.end());
		int last = 0, ans = 0;
		for(int i = 0; i < n << 1; i ++){
			int now = v1[i][0];
			ans += sum1[1] * (now - last);
			// cout << sum1[1] << " " << now << " " << last << "\n";
			last = now;
			set(set, 1, find(v1[i][1]), find(v1[i][2]) - 1, v1[i][3], 1, m);
		}
		cout << ans << "\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
#include<bits/stdc++.h>
using namespace std;
#define M 500
int a1[M];
int temp[M];
void merge(int l,int m,int r){
    int i=l;
    int j=m+1;
    int mark=l;
    while(i<=m && j<=r) a1[mark++]=temp[i]<temp[j]?temp[i++]:temp[j++];
    while(i<=m) a1[mark++]=temp[i++];
    while(j<=r) a1[mark++]=temp[j++];
    for(int k=l;k<=r;k++) temp[k]=a1[k];
}
void guibing(int l,int r){
	if(l>=r) return ;
	int m=(l+r)/2;
	guibing(l,m);
	guibing(m+1,r);
	merge(l,m,r);
}
int main(){
    int n;
    cin>>n;
	for(int i=0;i<n;i++){
        cin>>a1[i];
        temp[i]=a1[i];
    }
    guibing(0,n-1);
	for(int i=0;i<n;i++) cout<<a1[i]<<" ";
	return 0;
}

随机快排 & 选择第 k 小/大 的数

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
#include<bits/stdc++.h>
using namespace std;
#define M 500
// 经典
int partition1(int a1[],int l,int mid,int r){
    int i=l;
    int j=r;
    int temp=a1[mid];
    swap(a1[mid],a1[l]);
    while(i<j){
        while(j>i && a1[j]>temp){
            j--;
        }
        a1[i]=a1[j];
        while(i<j && a1[i]<=temp){
            i++;
        }
        a1[j]=a1[i];
    }
    a1[i]=temp;
    return i;
}
void qs1(int a1[],int l,int r){
    if(l>=r) return ;
    int x=l+(rand()%(r-l+1));
    int mid=partition1(a1,l,x,r);
    qs1(a1,l,mid-1);
    qs1(a1,mid+1,r);
}
// 优化
int first;
int second;
void partition2(int a1[],int l,int mid,int r){
    first=l;
    second=r;
    int temp=a1[mid];
    int i=l;
    while(i<=second){
        if(a1[i]==temp){
            i++;
        }else if(a1[i]<temp){
            swap(a1[first++],a1[i++]);
        }else{
            swap(a1[i],a1[second--]);
        }
    }
}
void qs2(int a1[],int l,int r){
    if(l>=r) return ;
    int x=l+(rand()%(r-l+1));
    partition2(a1,l,x,r);
    int left=first;
    int right=second;
    qs2(a1,l,left-1);
    qs2(a1,right+1,r);
}
// 随机选择第 tar 小的元素（0-based）
// 要求第k大的元素等同于求n - k小的元素
int randomizedSelect(int a1[], int k, int n) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int x = l + rand() % (r - l + 1); // 随机选取枢纽值
        partition2(a1, l, x, r); // 三路划分，结果通过 first 和 second 表示
        if (k < first) {
            r = first - 1; // 目标在左侧
        } else if (k > second) {
            l = second + 1; // 目标在右侧
        } else {
            return a1[k]; // 命中：tar 位于等于区域内
        }
    }
    // 若未找到（理论上不会出现），返回 -1 表示错误
    return -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
#define int long long
constexpr int mod = 998244353;
auto power = [&](int x, int n) -> int {
    int ans = 1;
    while(n){
        if(n & 1){
            ans = ans * x % mod;
        }
        x = x * x % mod;
        n >>= 1;
    }
    return ans;
};
vector<int> fac(n + 1); // 阶乘
fac[0] = 1;
for(int i = 1; i <= n; i ++){
    fac[i] = fac[i - 1] * i % mod; 
}
vector<int> inv(n + 1); // 逆元
inv[n] = power(fac[n], mod - 2);
for(int i = n - 1; i >= 0; i --){
    inv[i] = inv[i + 1] * (i + 1) % mod;
}
auto C = [&](int n, int m) -> int { // 组合数
    if(m > n){
        return 0;
    }
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
};

线性递推逆元

1
2
3
4
5
// p 必须为质数
inv2[1] = 1;
for(int i = 2; i <= n; i ++){
	inv2[i] = (p - p / i) * inv2[p % i] % 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
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<vector<long long>> multiply(const vector<vector<long long>> &a,const vector<vector<long long>> &b) {
		int n = a.size(), p = a[0].size(), m = b[0].size();
		vector ans(n, vector<long long>(m, 0));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				for (int k = 0; k < p; k++) {
					ans[i][j] += a[i][k] * b[k][j];
				}
			}
		}
		return ans;
	}
	vector<vector<long long>> power(vector<vector<long long>> v, int cnt) {
		int n = v.size();
		vector<vector<long long>> ans(n, vector<long long>(n, 0));
		for (int i = 0; i < n; i++) {
			ans[i][i] = 1;
		}
		while (cnt) {
			if (cnt & 1) {
				ans = multiply(ans, v);
			}
			v = multiply(v, v);
			cnt >>= 1;
		}
		return ans;
	}
    int tribonacci(int n) {
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;
        vector<vector<long long>> start = {{1, 1, 0}};
        vector<vector<long long>> base = {{1, 1, 0}, {1, 0, 1}, {1, 0, 0}};
        return multiply(start, power(base, n - 2))[0][0];
    }
};

扩展欧几里得算法

得到某一个ax + by = d的各种参数，d为最大公约数，x和y为贝祖系数（裴蜀定理的算法实现）

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
#include<bits/stdc++.h>
using namespace std;
int x, y, px, py;
int d;
void gcd1(int a,int b){
    if(!b){
        x = 1;
        y = 0;
        d = a;
    }else{
        gcd1(b, a % b);
        px = x;
        py = y;
        x = py;
        y = px - py * (a / b);
    }
}
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int a, b;
    cin >> a >> b;
    gcd1(a, b);
    cout << (x % b + b) % b << "\n";
    return 0;
}

GCD

一个数组的GCD前缀不同种类是log级别的，可通过此题进行进一步了解和体会2024ICPCKunming.

对任意a >= b, 有gcd(a, b) = gcd(a - b, b);

GCD 本质

求$gcd(a^b, c^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
// https://ac.nowcoder.com/acm/contest/108304/J
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
constexpr int mod = 998244353;
signed main(){
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int t = 1;
	cin >> t;
	while(t --) { 
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		auto power = [&](int x, int n) -> int {
			int ans = 1;
			x %= mod;
			while(n) {
				if(n & 1) ans = ans * x % mod;
				x = x * x % mod;
				n >>= 1;
			}
			return ans;
		};
		int ans = 1;
		while(1) {
			if(b > d) swap(a, c), swap(b, d);
			int temp = gcd(a, c);
			ans = ans * power(temp, b) % mod;
			a = a / temp;
//             c = temp;
			d -= b;
			if(gcd(a, c) == 1) break;
		}
		cout << ans << "\n";
    }
    return 0;
}

Stein GCD算法

Stein算法是一种计算两个非负整数的最大公约数的算法。它比传统的欧几里得算法在某些情况下更高效，
因为它避免了使用除法操作。该算法利用了以下几条规则：
GCD(0, b) = b：如果一个数是0，另一个数就是最大公约数。
GCD(a, 0) = a：同上，如果一个数是0，另一个数就是最大公约数。
如果a和b都是偶数，那么GCD(a, b) = 2 * GCD(a/2, b/2)。
如果a是偶数且b是奇数，那么GCD(a, b) = GCD(a/2, b)。
如果a是奇数且b是偶数，那么GCD(a, b) = GCD(a, b/2)。
如果a和b都是奇数，并且a >= b，那么GCD(a, b) = GCD((a - b)/2, b)。
如果a和b都是奇数，并且a < b，那么GCD(a, b) = GCD((b - a)/2, a)。
通过不断应用这些规则，最终可以将两个数变为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
unsigned int steinGCD(unsigned int a, unsigned int b) {
    if (a == 0) return b;
    if (b == 0) return a;
    // 找到a和b的共同因子2的数量
    unsigned int shift = 0;
    while (((a | b) & 1) == 0) {
        a >>= 1;
        b >>= 1;
        shift++;
    }
    // 使a成为奇数
    while ((a & 1) == 0) {
        a >>= 1;
    }
    do {
        // 使b成为奇数
        while ((b & 1) == 0) {
            b >>= 1;
        }
        // 保证a <= b
        if (a > b) {
            swap(a, b);
        }
        // b - a是偶数，所以我们可以继续右移
        b = (b - a);
    } while (b != 0);
    // 恢复共同因子2的数量
    return a << shift;
}

Least Recently Used (LRU)算法

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define M 1010
// Least Recently Used (LRU) 缓存实现
class LRU {
public:
    // 定义双向链表节点
    class DoubleNode {
    public:
        int key;    // 节点对应的 key
        int val;    // 节点对应的 value
        DoubleNode* next; // 后继节点指针
        DoubleNode* last; // 前驱节点指针
        DoubleNode(int k, int v): key(k), val(v), last(nullptr), next(nullptr) {}
    };
    // 定义双向链表，用于维护访问顺序
    class DoubleList {
    private:
        DoubleNode* head; // 链表头部（最久未使用）
        DoubleNode* tail; // 链表尾部（最近使用）
    public:
        DoubleList(): head(nullptr), tail(nullptr) {}
        // 在链表尾部添加新节点（最新使用的节点）
        void addNode(DoubleNode* newNode) {
            if (!newNode) return;
            if (!head) {
                head = tail = newNode;
            } else {
                tail->next = newNode;
                newNode->last = tail;
                tail = newNode;
            }
        }
        // 将已有节点移动到链表尾部（表示最近使用）
        void moveNodeToTail(DoubleNode* node) {
            if (tail == node) return;  // 节点已在尾部，无需移动
            if (head == node) {        // 节点位于头部
                head = node->next;
                if (head) head->last = nullptr;
            } else {                   // 节点在中间
                node->last->next = node->next;
                if (node->next)
                    node->next->last = node->last;
            }
            // 将节点移动到尾部
            node->last = tail;
            node->next = nullptr;
            if (tail) tail->next = node;
            tail = node;
        }
        // 移除链表头部节点（最久未使用的节点）并返回该节点
        DoubleNode* removeHead() {
            if (!head) return nullptr;
            DoubleNode* ans = head;
            if (head == tail) {
                head = tail = nullptr;
            } else {
                head = head->next;
                if (head) head->last = nullptr;
            }
            return ans;
        }  
        // 辅助函数：清空链表，释放所有节点
        void clear() {
            DoubleNode* cur = head;
            while(cur) {
                DoubleNode* next = cur->next;
                delete cur;
                cur = next;
            }
            head = tail = nullptr;
        }    
        // 提供链表头部访问，用于析构时遍历
        DoubleNode* getHead() {
            return head;
        }
    };
private:
    unordered_map<int, DoubleNode*> keyNodeMap; // 快速定位 key 对应的节点
    DoubleList nodeList;                        // 维护节点顺序的双向链表
    int cap;                                    // 缓存容量
public:
    // 构造函数
    LRU(int c): cap(c) {}
    // 析构函数，释放所有申请的内存
    ~LRU() {
        // 遍历双向链表释放节点
        DoubleNode* cur = nodeList.getHead();
        while(cur) {
            DoubleNode* next = cur->next;
            delete cur;
            cur = next;
        }
        keyNodeMap.clear();
    }
    /**
     * @brief 获取 key 对应的值，并将该节点移到尾部表示最近使用
     * 
     * @param key 缓存中的键
     * @return int 若 key 存在则返回对应值，否则返回 -1
     */
    int get(int key) {
        if (keyNodeMap.count(key)) {
            DoubleNode* ans = keyNodeMap[key];
            nodeList.moveNodeToTail(ans);  // 更新最近使用
            return ans->val;
        }
        return -1;
    }
    /**
     * @brief 向缓存中插入或更新一个 key-value 对
     * 
     * 若 key 存在，则更新其值并将节点移到尾部；
     * 若 key 不存在，则插入新节点，若缓存已满，则移除最久未使用的节点。
     * 
     * @param key 缓存中的键
     * @param val1 缓存中的值
     */
    void put(int key, int val1) {
        if (keyNodeMap.count(key)) {
            // key 存在，更新值并移到尾部
            DoubleNode* node = keyNodeMap[key];
            node->val = val1;
            nodeList.moveNodeToTail(node);
        } else {
            // 如果缓存已满，删除最久未使用的节点
            if (keyNodeMap.size() == cap) {
                DoubleNode* removed = nodeList.removeHead();
                if(removed) {
                    keyNodeMap.erase(removed->key);
                    delete removed;  // 释放内存
                }
            }
            // 插入新节点
            DoubleNode* newNode = new DoubleNode(key, val1);
            keyNodeMap[key] = newNode;
            nodeList.addNode(newNode);
        }
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 测试用例：创建容量为3的LRU缓存
    LRU cache(3);
    // 插入数据
    cache.put(1, 100);
    cache.put(2, 200);
    cache.put(3, 300);
    // 访问 key 1，将其更新为最近使用
    cout << "get(1): " << cache.get(1) << "\n"; // 输出 100
    // 插入新数据，当缓存满时会淘汰最久未使用的 key（此时 key 2 被淘汰）
    cache.put(4, 400);
    // 尝试获取被淘汰的 key 2
    cout << "get(2): " << cache.get(2) << "\n"; // 输出 -1，表示不存在
    // 继续获取其他 key 的值
    cout << "get(3): " << cache.get(3) << "\n"; // 输出 300
    cout << "get(4): " << cache.get(4) << "\n"; // 输出 400
    return 0;
}

二进制位

位图

判断某一个数是否存在

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
void add(int arr[],int num){
	arr[num/32] |= 1<<(num%32);
}
void remove(int arr[],int num){
	arr[num/32] &= ~(1<<(num%32));
}
void reverse(int arr[],int num){
	arr[num/32] ^= 1<<(num%32);
}
bool contains(int arr[],int num){
	return arr[num/32] & (1<<(num%32));
}
int main(){
	int n;
	cin>>n;
	int set[(n + 32 - 1) / 32]; // 表示存储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
#include <bits/stdc++.h>
using namespace std;
int add(int n, int m) {
    int ans = n;
    while(m != 0) {
        // 无进位相加
        ans = n ^ m;
        // 计算进位，注意进位要左移一位
        m = (n & m) << 1;
        n = ans;
    }
    return ans;
}
int neg(int n) {
    // 对 n 取反后加 1 得到 -n
    return add(~n, 1);
}
int minus1(int n, int m) {
    return add(n, neg(m));
}
int mul(int n, int m) {
    int ans = 0;
    while(m != 0) {
        if((m & 1) == 1) {
            ans = add(ans, n);
        }
        n <<= 1;
        m >>= 1;
    }
    return ans;
}
int div1(int n, int m) {
    // 转为正数处理，保存符号信息
    int a = n < 0 ? neg(n) : n;
    int b = m < 0 ? neg(m) : m;
    int ans = 0;
    // 从最高位开始遍历
    for(int i = 30; i >= 0; i = minus1(i, 1)) {
        // 判断 a 右移 i 位后是否大于等于 b
        if((a >> i) >= b) {
            // 减去 b 左移 i 位
            a = minus1(a, (b << i));
            // 将结果对应位设为1
            ans |= (1 << i);
        }
    }
    // 如果 n 与 m 符号不同，则结果取负
    return (n < 0) ^ (m < 0) ? neg(ans) : ans;
}
// 完整版
int div2(int a, int b) {
    if(a == INT_MIN && b == INT_MIN) return 1;
    if(a != INT_MIN && b != INT_MIN) return div1(a, b);
    if(b == INT_MIN) return 0;  // 除数为 INT_MIN，其它数除以它的商为0
    if(b == neg(1)) return INT_MAX;  // 防止 INT_MIN / -1 溢出
    // 近似处理：调整 a 的值
    a = add(a, b > 0 ? b : neg(b));
    int ans = div1(a, b);
    // 根据除数的正负决定偏移
    int offset = b > 0 ? neg(1) : 1;
    return add(ans, offset);
}

位运算骚操作

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>
using namespace std;
//判断一个数是不是2的幂
int jurge1(int n){
	return n>0 && n == (n&(-n));
}
//判断一个数是不是3的幂
#define M 1162261467
int jurge2(int n){
	return n>0 && M%n==0;
}
//求大于等于n的最小2次幂
int F1(int n){
	if(n<=0) return 1;
	n--;
	n |= n>>1;
	n |= n>>2;
	n |= n>>4;
	n |= n>>8;
	n |= n>>16;;
	return n+1;
}
//逆序二进制状态
int F2(int n){
	n= ((n&0xaaaaaaaa)>>1) | ((n&0x55555555)<<1);
	n= ((n&0xcccccccc)>>2) | ((n&0x33333333)<<2);
	n= ((n&0xf0f0f0f0)>>4) | ((n&0x0f0f0f0f)<<4);
	n= ((n&0xff00ff00)>>8) | ((n&0x00ff00ff)<<8);
	n = (n>>16) | (n<<16);
	return n;
}
//返回n的二进制中有几个1
int F3(int n){
	n = (n&0x55555555)+((n>>1)&0x55555555);
	n = (n&0x33333333)+((n>>2)&0x33333333);
	n = (n&0x0f0f0f0f)+((n>>4)&0x0f0f0f0f);
	n = (n&0x00ff00ff)+((n>>8)&0x00ff00ff);
	n = (n&0x0000ffff)+((n>>18)&0x0000ffff);
	return n;
}
//求x到y的所有数&的结果
int F4(int x,int y){
	while(y>x){
		y -= y &(-y);
	}return y;
}

Brain Kernighan算法

异或技巧

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>
using namespace std;
#define M 500
int a1[M];
int n;
// 以下两个全局变量用于功能1：两个出现次数为奇数次的数字
int ero1 = 0;
int ero2 = 0;
void solve(int a[], int size) {
    ero1 = 0;
    ero2 = 0;
    // 计算所有数字的异或结果
    for (int i = 0; i < size; i++) {
        ero1 ^= a[i];
    }
    // 找到最右侧的1
    int rightone = ero1 & (-ero1);
    // 根据该位是否为1将数字分组，并对其中一组异或
    for (int i = 0; i < size; i++) {
        if ((a[i] & rightone) == 0) {
            ero2 ^= a[i];
        }
    }
    // 另一个奇数次数字
    ero1 = ero1 ^ ero2;
}
// 以下全局变量用于功能2：求数组中出现次数少于 cnt 次的数字
int ans = 0;
int bits[32];  // 用于统计各二进制位1的个数
void solve2(int size, int cnt, int a[]) {
    ans = 0;
    memset(bits, 0, sizeof(bits));
    // 统计每一位的1的个数
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < 32; j++) {
            // 等价于：if(a[i] & (1 << j)) bits[j]++;
            bits[j] += (a[i] >> j) & 1;
        }
    }
    // 对每一位判断是否为目标数字的1
    for (int j = 0; j < 32; j++) {
        if (bits[j] % cnt) {
            ans |= (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
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
struct LinkNode{
    int val;
    LinkNode *next;
    LinkNode(int _val) : val(_val), next(nullptr) {}
};
//返回两个无环链表相交的第一个节点
LinkNode *converge(LinkNode *&L1,LinkNode *&L2){
    LinkNode *p1=L1->next;
    LinkNode *p2=L2->next;
    int cnt=0;
    if(L1==nullptr || L2==nullptr) return nullptr;
    while(p1!=nullptr){
        cnt++;
        p1=p1->next;
    }
    while(p2!=nullptr){
        cnt--;
        p2=p2->next;
    }
    p1=L1;
    p2=L2;
    if(cnt>=0){
        while(cnt--) p1=p1->next;
    }
    else{
        cnt=abs(cnt);
        while(cnt--) p2=p2->next;
    }
    while(p1!=p2 && p1!=nullptr && p2!=nullptr){
        p1=p1->next;
        p2=p2->next;
    }
    return p1;
}

每k个节点一组翻转链表

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
//每k个节点一组翻转链表
void reverse(int k, LinkNode *&L){
    if(k<=1 || L==nullptr || L->next==nullptr) return;
    LinkNode *p1=L->next;
    int cnt=0;
    while(p1!=nullptr){
        cnt++;
        p1=p1->next;
    }
    if(cnt<k) return;
    p1=L;
    LinkNode *pre;
    LinkNode *p;
    LinkNode *pp;
    LinkNode *p0=L;
    LinkNode *last=p0->next;
    for(int i=0;i<k;i++) p1=p1->next;
    p=p0->next;
    pp=p->next;
    p->next=p1->next;
    pre=p;
    for(int i=1;i<k;i++){
        p=pp;
        pp=p->next;
        p->next=pre;
        pre=p;
    }
    p0->next=p1;
    for(int j=cnt-k;j>=k;j-=k){
        p0=last;
        p1=last;
        for(int i=0;i<k;i++) p1=p1->next;
        p=p0->next;
        last=p;
        pp=p->next;
        p->next=p1->next;
        pre=p;
        for(int i=1;i<k;i++){
            p=pp;
            pp=p->next;
            p->next=pre;
            pre=p;
        }
        p0->next=p1;
    }
}

复制带随机指针的链表

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
//复制带随机指针的链表
class NodeR{
public:
    int val;
    NodeR *next;
    NodeR *random;
    NodeR(int x){
        val=x;
        next=nullptr;
        random=nullptr;
    }
};
NodeR * copy(NodeR *&L1){
    if(L1==nullptr) return nullptr;
    NodeR* cur=L1->next;
    //复制节点并插入原节点之后
    while(cur!=nullptr){
        NodeR* next=new NodeR(cur->val);
        next->next=cur->next;
        cur->next=next;
        cur=next->next;
    }
    //更新节点的随机指针
    cur=L1->next;
    while(cur!=nullptr){
        if(cur->random!=nullptr){
            cur->next->random=cur->random;
        }
        cur=cur->next->next;
    }
    //分离链表
    cur=L1->next;
    NodeR* L2=new NodeR(0);
    NodeR* temp=L2;
    while(cur!=nullptr){
        temp->next=cur->next;
        cur->next=cur->next->next;
        cur=cur->next;
        temp=temp->next;
    }
    return L2;
}

判断是否是回文结构（快慢指针）

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
//判断链表是否是回文结构（快慢指针）
bool judge_HuiWen(LinkNode *L){
    if(L==nullptr || L->next==nullptr) return true;
    //快慢指针找中点
    LinkNode* f=L;
    LinkNode* s=L;
    while(f!=nullptr && f->next!=nullptr){
        f=f->next->next;
        s=s->next;
    }
    //翻转
    LinkNode* pre=s;
    LinkNode* cur=s->next;
    LinkNode* next=nullptr;
    pre->next=nullptr;
    while(cur!=nullptr){
        next=cur->next;
        cur->next=pre;
        pre=cur;
        cur=next;
    }
    //判断回文
    bool ans=true;
    LinkNode* sta1=L->next;
    LinkNode* sta2=pre;
    while(sta1!=nullptr && sta2!=nullptr){
        if(sta1->val!=sta2->val){
            ans=false;
            break;
        }
        sta1=sta1->next;
        sta2=sta2->next;
    }
    //还原
    cur=pre->next;
    pre->next=nullptr;
    next=nullptr;
    while(cur!=nullptr){
        next=cur->next;
        cur->next=pre;
        pre=cur;
        cur=next;
    }
    return ans;
}

返回第一个入环节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//返回链表的第一个入环节点
LinkNode* cycle(LinkNode *L){
    if (L == nullptr || L->next == nullptr) {
        return nullptr;
    }
    LinkNode* f=L;
    LinkNode* s=L;
    while(f!=nullptr && f->next!=nullptr){
        s=s->next;
        f=f->next->next;
        if(s==f){
            f=L;
            while(f!=s){
                f=f->next;
                s=s->next;
            }
            return f;
        }
    }return nullptr;
}

稳定排序

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
//在链表上排序，时间复杂度O（n*logn），额外空间复杂度（1），排序有稳定性
LinkNode* createNode(int data) {
    return new LinkNode(data);
}
// 在链表尾部添加节点
void appendNode(LinkNode*& head, int data) {
    LinkNode* newNode = createNode(data);
    LinkNode* temp = head;
    while (temp->next) {
        temp = temp->next;
    }
    temp->next = newNode;
}
LinkNode* start;
LinkNode* end1;
LinkNode* FindEnd(LinkNode* l,int len){
    while(l->next!=nullptr && --len!=0){
        l=l->next;
    }return l;
}
void merge(LinkNode* l1, LinkNode* r1, LinkNode* l2, LinkNode* r2) {
    LinkNode* pre;
    if (l1->val <= l2->val) {
        start = l1;
        pre = l1;
        l1 = l1->next;
    } else {
        start = l2;
        pre = l2;
        l2 = l2->next;
    }
    while (l1 != nullptr && l2 != nullptr) {
        if (l1->val <= l2->val) {
            pre->next = l1;
            pre = l1;
            l1 = l1->next;
        } else {
            pre->next = l2;
            pre = l2;
            l2 = l2->next;
        }
    }
    if (l1 != nullptr) {
        pre->next = l1;
        end1 = r1;
    } else {
        pre->next = l2;
        end1 = r2;
    }
}
void sort(LinkNode*& L){
    if (L == nullptr || L->next == nullptr) {
        return;
    }
    int len=0;
    LinkNode* temp=L;
    while(temp!=nullptr){
        len++;
        temp=temp->next;
    }
    LinkNode* l1;
    LinkNode* r1;
    LinkNode* l2;
    LinkNode* r2;
    LinkNode* lastTeamend;
    LinkNode* next;
    for(int i=1;i<len;i<<=1){
        l1=L;
        r1=FindEnd(l1,i);
        l2=r1->next;
        r2=FindEnd(l2,i);
        next = r2->next;
        r1->next = nullptr;
        r2->next = nullptr;
        merge(l1,r1,l2,r2);
        L=start;
        lastTeamend=end1;
        while(next!=nullptr){
            l1=next;
            r1=FindEnd(l1,i);
        	l2 = r1->next;
        	if(l2==nullptr){
        		lastTeamend->next = l1;
        		break;
        	}
            r2 = FindEnd(l2, i);
            next = r2->next;
            r1->next = nullptr;
            r2->next = nullptr;
            merge(l1,r1,l2,r2);
            lastTeamend->next=start;
            lastTeamend=end1;
        }
    }
}

合并n个有序链表

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
#include<bits/stdc++.h>
using namespace std;
#define M 500
struct ListNode{
    int val;
    ListNode * next;
};
void Create(ListNode *&q){
    q=(ListNode *)malloc(sizeof(ListNode));
    q->next=nullptr;
}
struct cmp{
    bool operator()(ListNode* a,ListNode* b){
        return a->val > b->val;
    }
};

ListNode *merge(vector<ListNode*>& v1){
    priority_queue<ListNode*,vector<ListNode*>,cmp> pq1;
    for(ListNode* it : v1) if(it) pq1.push(it);
    ListNode* ans;
    Create(ans);
    ListNode* temp;
    ListNode* pre=ans;
    while(!pq1.empty()){
        temp=pq1.top();
        pq1.pop();
        pre->next=temp;
        pre=temp;
        if(temp->next) pq1.push(temp->next);
    }pre->next=nullptr;
    return ans;
}

int main(){
    int n;
    cin>>n;
    int cnt;
    ListNode* pre;
    int temp1;
    vector<ListNode*> v1;
    while(n--){
        cin>>cnt;
        ListNode * l=(ListNode*)malloc(sizeof(ListNode));
        l->next=nullptr;
        pre=l;
        for(int i=0;i<cnt;i++){
            cin>>temp1;
            ListNode *temp=(ListNode*)malloc(sizeof(ListNode));
            temp->val=temp1;
            temp->next=pre->next;
            pre->next=temp;
            pre=temp;
        }v1.push_back(l->next);
    }
    ListNode * final;
    Create(final);
    final=merge(v1);
    pre=final->next;
    while(pre){
        cout<<pre->val<<" ";
        pre=pre->next;
    }cout<<endl;
    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
#include <bits/stdc++.h>
using namespace std;
struct Query {
    int l, r, id, blk;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> original(n + 1), ans(q);
    for (int i = 1; i <= n; i++){
    	cin >> original[i];
    }
	// 离散化
	vector<int> temp = original;
    sort(temp.begin()+1, temp.end());
    int m = 1;
    for(int i = 2; i <= n; i ++){
    	if(temp[m] != temp[i]){
    		temp[++ m] = temp[i];
    	}
    }
    auto find = [&](int x) -> int {
    	int l = 1, r = m;
    	int mid, ans;
    	while(l <= r){
    		mid = (l + r) >> 1;
    		if(temp[mid] <= x){
    			ans = mid;
    			l = mid + 1;
    		}else{
    			r = mid - 1;
    		}
    	}
    	return ans;
    };
    // 莫队函数
    int now_ans = 0;
    vector<int> fre(n + 1, 0);
    auto add = [&](int x) {
    	int & f = fre[find(x)];
    	if (f == 1) {
	        now_ans++;
	    } else if (f == 2) {
	        now_ans--;
	    }
        f++;
    };
    auto remove = [&](int x) {
    	int &f = fre[find(x)];
	    if (f == 2) {
	        now_ans--;
	    } else if (f == 3) {
	        now_ans++;
	    }
        f--;
    };
	// 窗口优化
    int blk = (int)sqrt(n);
    vector<Query> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
        queries[i].blk = queries[i].l / blk;
    }
    sort(queries.begin(), queries.end(), [&](const Query &A, const Query &B) {
        if (A.blk == B.blk) return A.r < B.r;
        return A.blk < B.blk;
    });
    int curL = 1, curR = 0;
    for (auto &q : queries) {
        while (curR < q.r) add(original[++curR]);
        while (curR > q.r) remove(original[curR--]);
        while (curL < q.l) remove(original[curL++]);
        while (curL > q.l) add(original[--curL]);
        ans[q.id] = now_ans;
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
    return 0;
}

KMP算法

字符匹配匹配加速，加速的点在于匹配失败后不一定直接返回起点重新匹配，而是跳到最大前缀处，如abab......匹配失败时，会跳到2位置而不是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
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s1, s2;
    cin >> s1 >> s2;
    int n = int(s1.size());
    int m = int(s2.size());
    vector<int> next1(m + 1, 0);
    int i1 = 2;
    int mark1 = 0;
    while(i1 <= m){
        if(s2[i1 - 1] == s2[mark1]){
            next1[i1++] = ++ mark1;
        }else if(mark1 != 0){
            mark1 = next1[mark1];
        }else{
            next1[i1++] = 0;
        }
    }
    int j1 = i1 = 0;
    while(j1 < n){
        if(s1[j1] == s2[i1]){
            j1 ++, i1 ++;
        }else if(i1 != 0){
            i1 = next1[i1];
        }else{
            j1 ++;
        }
        if(i1 == m){
            cout << j1 - i1 + 1 << "\n";
            i1 = next1[i1];
        }
    }
    for(int i = 1; i <= m; i ++){
    	cout << next1[i];
    	if(i != m) cout << " ";
    }
    return 0;
}

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define fr first
#define sc second
string manacherss(string s){
	string ss = "#";
	for(int i = 0; i < s.size(); i ++){
		ss += s[i];
		ss += '#';
	}
	return ss;
}
void solve(){
	string s;
	cin >> s;
	string ss = manacherss(s);
	int n = ss.size();
	vector<int> r1(n, 0); // 真实回文串的长度为r[i] - 1;
	int ans = 0;
	for(int i = 0, r = 0, c = 0, len; i < n; i ++){
		len = r > i ? min(r1[2 * c - i], r - i) : 1;
		while(i - len >= 0 && i + len < n && ss[i - len] == ss[i + len]){
			len ++;
		}
		if(len + i > r){
			r = len + i;
			c = i;
		}
		r1[i] = len;
		ans = max(ans, len);
	}
	cout << ans - 1 << "\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
   
    int t = 1;
    // cin >> t;
    while (t--) {
	     solve();
    }
    return 0;
}

Z函数

对于一个长度为n的字符串s，定义函数z[i]表示s和s[i, n - 1]的最长公共前缀（LCP）的长度则z被成为s的Z函数

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
#include <bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P5410
#define int long long 
#define fr first
#define sc second
void Z1(vector<int> & z, string s, int n){
	z[0] = n;
	for(int i = 1, c = 1, r = 1, len; i < n; i ++){
		len = r > i ? min(z[i - c], r - i) : 0;
		while(i + len < n && s[len] == s[i + len]){
			len ++;
		}
		if(i + len > r){
			r = i + len;
			c = i;
		}
		z[i] = len;
	}
}
void E1(vector<int> & e, vector<int> & z, string s1, string s2, int n){
	for(int i = 0, r = 0, c = 0, len; i < n; i ++){
		len = r > i ? min(z[i - c], r - i) : 0;
		while(i + len < n && s1[i + len] == s2[len]){
			len ++;
		}
		if(i + len > r){
			r = i + len;
			c = i;
		}
		e[i] = len;
	}
}
void solve(){
	string s1, s2;
	cin >> s1 >> s2;
	// 求得该字符串的最长前缀
	int n = s2.size();
	vector<int> Z(n, 0);
	Z1(Z, s2, n);
	// 求该串以某一串为基准的最长前缀
	int m = s1.size();
	vector<int> E(m + 1);
	E1(E, Z, s1, s2, m);
}

前缀树

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
#include<bits/stdc++.h>
using namespace std;
//静态数组版本
const int M = 150001;
const int M2 = 28;
int cnt=1;
int pass1[M];
int end1[M];
int t1[M][M2];
int op1;
string op2;
void build() {
    cnt = 1;
    memset(t1, 0, sizeof(t1));
    memset(end1, 0, sizeof(end1));
    memset(pass1, 0, sizeof(pass1));
}
void insert(const string& word){
    int cur=1;
    pass1[cur]++;
    for(int i=0;i<word.size();i++){
        int path = word[i]-'a';
        if(t1[cur][path]==0){
            t1[cur][path]=++cnt;
        }
        cur=t1[cur][path];
        pass1[cur]++;
    }end1[cur]++;
}
int search(const string& word){
    int cur=1;int path;
    for(int i=0;i<word.size();i++){
        path=word[i]-'a';
        if(t1[cur][path]==0){
            return 0;
        }
        cur=t1[cur][path];
    }return end1[cur];
}
void erase(const string& word){
    if(search(word)>0){
        int path;
        int cur=1;
        for(int i=0;i<word.size();i++){
            path = word[i]-'a';
            if(--pass1[t1[cur][path]]==0){
                t1[cur][path]=0;
                //  之后会重新分配节点，所以遍历不到未减减的end
                return ;
            }cur=t1[cur][path];
        }
        end1[cur]--;
    }
}
int prefixNumber(const string& pre){
    int cur=1;
    int path;
    for(int i=0;i<pre.size();i++){
        path = pre[i]-'a';
        if(t1[cur][path]==0){
            return 0;
        }
        cur=t1[cur][path];
    }return pass1[cur];
}
int main() { 
    string line;
    while (getline(cin, line)) {
        build();
        int m = stoi(line);
        for (int i = 0; i < m; ++i) {
            getline(cin, line);
            stringstream ss(line);
            int op;
            string word;
            ss >> op >> word;
            if (op == 1) {
                insert(word);
            } else if (op == 2) {
                erase(word);
            } else if (op == 3) {
                cout << (search(word) > 0 ? "YES" : "NO") << endl;
            } else if (op == 4) {
                cout << prefixNumber(word) << endl;
            }
        }
    }
    return 0;
}

AC自动机

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
#include<bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P3796
const int N = 2e4;
int cnt1;
vector<int> fail1(N);
vector<vector<int>> tree1(N, vector<int>(26,0));
int n;
vector<int> end1(N);
vector<int> times1(N);
vector<int> v1(N); // BFS队列实现
//  链式前向星
int cnt2;
vector<int> head(N);
vector<int> next1(N);
vector<int> to(N);
string s1;
// 构建前缀树
vector<string> F1(){
	vector<string> s1(n + 1);
	string temp1;
    for(int i = 1, x; i <= n; i ++){
        cin >> temp1;
        s1[i] = temp1; 
        x = 0;
        for(int j = 0, y; j < temp1.size(); j ++){
            y = temp1[j] - 'a';
            if(tree1[x][y] == 0){
                tree1[x][y] = ++cnt1;
            }
            x = tree1[x][y];
        }
        end1[i] = x;
    }
    return s1;
}
// 构建自动机
void F2(){
	// BFS遍历
    int l, r;
    l = r = 0;
    for(int i = 0; i < 26; i ++){
        if(tree1[0][i] != 0){
            v1[r++] = tree1[0][i];
        }
    }
    int u;
    while(l < r){
        u = v1[l ++];
        for(int i = 0; i < 26; i ++){
            if(tree1[u][i] == 0){
                tree1[u][i] = tree1[fail1[u]][i];
            }else{
                fail1[tree1[u][i]] = tree1[fail1[u]][i];
                v1[r ++] = tree1[u][i];
            }
        }
    }
}
// 反向建图
void add1(int u, int v){
    next1[++cnt2] = head[u];
    head[u] = cnt2;
    to[cnt2] = v;
}
// 统计次数
void F3(int x){
    for(int e = head[x]; e > 0; e = next1[e]){
        F3(to[e]);
        times1[x] += times1[to[e]];
    }
}
void build(){
	for(int i = 0; i < N; i ++){
		for(int j = 0; j < 26; j ++){
			tree1[i][j] = 0;
		}
	}
	cnt2 = cnt1 = 0;
	fill(head.begin(), head.end(), 0);
	fill(times1.begin(), times1.end(), 0);
	fill(fail1.begin(), fail1.end(), 0);
}
void solve(){
	build();
    vector<string> ss = F1();
    F2();
    cin >> s1;
    for(int i = 0, u = 0; i < s1.size(); i ++){
        u = tree1[u][s1[i] - 'a'];
        times1[u] ++;
    }
    for(int i = 1; i <= cnt1; i ++){
        add1(fail1[i], i);
    }
    F3(0);
    int max1 = -1;
    for(int i = 1; i <= n; i ++){
        if(times1[end1[i]] > max1){
        	max1 = times1[end1[i]];
        }
    }
    cout << max1 << "\n";
    for(int i = 1; i <= n; i ++){
    	if(times1[end1[i]] == max1){
    		cout << ss[i] << "\n";
    	}
    }
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    cin >> n;
    while(n){
    	solve();
    	cin >> 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
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
#include <bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P3370
// 利用质数进制信息
#define int long long 
#define fr first
#define sc second
int base = 39127;
int v(char c){
	int ans;
	if('0' <= c && '9' >= c){
		ans = c - '0' + 1;
	}else if('a' <= c && 'z' >= c){
		ans = c - 'a' + 11;
	}else{
		ans = c - 'A' + 37;
	}
	return ans;
}
// 加速进制
int F(string s){
	int ans = v(s[0]);
	for(int i = 1; i < s.size(); i ++){
		ans = ans * base + v(s[i]);
	}
	return ans;
}
void solve(){
	int n;
	cin >> n;
	vector<int> v1(n);
	string s;
	for(int i = 0; i < n; i ++){
		cin >> s;
		v1[i] = F(s);
	}
	sort(v1.begin(), v1.end());
	int ans = 1;
	for(int i = 1; i < n; i ++){
		if(v1[i] != v1[i - 1]){
			ans ++;
		}
	}
	cout << ans << "\n";
}
// https://www.luogu.com.cn/record/204776127
// 要求一段区间内的hash值，用前缀和
int H(vector<int> & hash, vector<int> & power, int l, int r){
	if(l > 0){
		l = hash[l - 1] * power[r - l + 1]; 
	}
	r = hash[r];
	return r - l;
}
void solve2(){
	string s1, s2;
	cin >> s1 >> s2;	
	int n = s1.size(), m = s2.size();
	vector<int> hash1(n), hash2(m), power(max(n, m));
	power[0] = 1;
	for(int i = 1; i < power.size(); i ++){
		power[i] = power[i - 1] * base;
	}	
	hash1[0] = s1[0] - 'A' + 1;
	for(int i = 1; i < n; i ++){
		hash1[i] = hash1[i - 1] * base + s1[i] - 'A' + 1;
	}
	hash2[0] = s2[0] - 'A' + 1;
	for(int i = 1; i < m; i ++){
		hash2[i] = hash2[i - 1] * base + s2[i] - 'A' + 1;
	}
	int ans = 0;
	int l1, l2, r1;
	int l, r, len, mid;
	int k;
	for(int i = 0; i <= n - m; i ++){
		l1 = i, r1 = i + m - 1;
		k = 0;
		l2 = 0;
		while(l1 <= r1 && k <= 3){
			l = l1, r = r1;
			len = 0;
			while(l <= r){
				mid = (l + r) >> 1;
				if(H(hash1, power, l1, mid) == H(hash2, power, l2, l2 + mid - l1)){
					len = mid - l1 + 1;
					l = mid + 1;
				}else{
					r = mid - 1;
				}
			}
			if(l1 + len <= r1){
				k ++;
				l1 += len + 1;
				l2 += len + 1;
			}else{
				break;
			}
		}
		if(k <= 3){
			ans ++;
		}
	}
	cout << ans << "\n";
}

异或哈希

题目大概描述：给定一个数字序列a，请你找出最长的连续子区间，使得这个子区间内所有数字的乘积是一个完全平方数。如果存在多个长度相同的子区间，选择最靠左的一个。

完全平方数可以差分为质因数乘积，且所有质因数的个数均为偶数。

故把每一个数的值改为落单质因数的哈希值，如果某一个区间的异或值为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
using ull = unsigned long long;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
constexpr int N = 1e6 + 1;
vector<int> spf(N); // 最小质因子
vector<ull> prime_hash(N);
auto init() = [&](){
	iota(spf.begin(), spf.end(), 0);
    for(int i = 2; i < N; i ++){
        if(spf[i] == i){
            prime_hash[i] = rng();
            for(int j = i << 1; j < N; j += i){
                if(spf[j] == j){
                    spf[j] = i;
                }
            }
        }
    } 
}
// 根据最小质因子求某一个数的hash值
auto get_hash = [&](int x) -> ull {
    ull ans = 0;
    while(x > 1){
        int p = spf[x];
        int cnt = 0;
        while(x % p == 0){
            x /= p;
            cnt ^= 1;
        }
        if(cnt & 1){
            ans ^= prime_hash[p];		
        }
    }
    return ans;
};
int t = 1;
cin >> t;
while(t --){
    int n;
    cin >> n;
    vector<int> v1(n + 1);
    vector<ull> pref(n + 1);
    pref[0] = 0;
    for(int i = 1; i <= n; i ++){
        cin >> v1[i];
        pref[i] = pref[i - 1] ^ get_hash(v1[i]);
    }
    unordered_map<ull,int> pos;
    pos[0] = 0;
    int ans = 0, l = -1, r = -1;
    ull x;
    for(int i = 1; i <= n; i ++){
        x = pref[i];
        if(pos.count(x)){
            if(i - pos[x] > ans){
                ans = i - pos[x];
                l = pos[x] + 1, r = i;
            }
        }else{
            pos[x] = i;
        }
    }
    cout << l << " " << r << "\n";
}

质数/素数

质数判别

Miller Rabin的时间复杂度为$O(log\ n)^{3}$.

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
#include<bits/stdc++.h>
using namespace std;
// 普通判别方法
int p(int n){
	if (n <= 3) {
        return n > 1;
    }
    if (n % 6 != 1 && n % 6 != 5) {
        return false;
    }
    int sqrt1 = (int) sqrt(n);
    for (int i = 5; i <= sqrt1; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}
// Miller Rabin Prime判别法
using ll = long long;
// 大数的时候用
//typedef __int128 ll;
vector<ll> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
ll power(ll base, ll exp, ll mod) {
    ll result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}
bool witness(ll a, ll n) {
    ll u = n - 1;
    int t = 0;
    while ((u & 1) == 0) {
        t++;
        u >>= 1;
    }
    ll x = power(a, u, n);
    if (x == 1 || x == n - 1) return false;
    for (int i = 0; i < t - 1; i++) {
        x = (x * x) % n;
        if (x == n - 1) return false;
    }
    return true;
}
bool millerRabin(ll n) {
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;
    for (ll p : primes) {
        if (p >= n) break;
        if (witness(p, n)) return false;
    }
    return true;
}

线性质数筛

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
// 质数筛
void F1(int x){
	vector<int> v1;
	for(int i = 2; i * i <= x; i ++){
		if(x % i != 0){
			v1.push_back(i);
			while(x % i == 0) x /= i;
		}
	}
    if(x > 1) v1.push_back(x); 
}
// 求数值小于等于n的质数的个数,
// 质数筛-埃氏筛
void solve() {
	int n;
  	cin >> n;
  	vector<int> v(n + 1, 0);
	v[1] = 1;
  	int cnt = 0;
	for (int i = 2; i <= sqrt(n); i++){
		if (v[i] == 0){
	    	for (int j = i + i; j <= n; j += i) v[j] = 1;
		}
	}
  	for (int i = 1; i <= n; i++) {
    	if (!v[i]) cnt++;
  	}
  	cout << cnt << endl;
}
// 只是计数的话，埃氏筛还能改进
int ehrlich2(int n) {
    if (n <= 1) {
        return 0;
    }
    vector<bool> visit(n + 1, false);
    int cnt = (n + 1) / 2; // 估计质数数量(奇数)
    for (int i = 3; i * i <= n; i += 2) {
        if (!visit[i]) {
            for (int j = i * i; j <= n; j += 2 * i) {
                if (!visit[j]) {
                    visit[j] = true;
                    cnt--;
                }
            }
        }
    }
    return cnt;
}
// 使用线性筛法计算每个数字的最小质因子 `spf`（smallest prime factor）
constexpr int N = 1e6 + 1;
vector<int> spf(N);
auto init() = [&](){
	iota(spf.begin(), spf.end(), 0);
    for(int i = 2; i < N; i ++){
        if(spf[i] == i){
            prime_hash[i] = rng();
            for(int j = i << 1; j < N; j += i){
                if(spf[j] == j){
                    spf[j] = i;
                }
            }
        }
    } 
}
// 欧拉筛时间复杂度O(n)
int euler(int n) {
    vector<bool> visit(n + 1, false);
    vector<int> prime(n / 2 + 1);
    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (!visit[i]) {
            prime[cnt++] = i;
        }
        for (int j = 0; j < cnt; j++) {
            if (i * prime[j] > n) {
                break;
            }
            visit[i * prime[j]] = true;
            if (i % prime[j] == 0) {
    			// 保证每个合数只被最小的质数遍历一次
                break;
            }
        }
    }
    return cnt;
}

Pick定理

S = i + b / 2 - 1

S：图形的面积（可以是实数）；

i：图形内部的格点数；

b：图形边界上的格点数（包括顶点）；

给定两个整数点(x1, y1), (y1, y2), 两点间（包括端点)的格点数为gcd(|x2 - x1|, |y2 - y1|) + 1

则求某区域内的格点数的方法为i = S − 2 / b + 1

差分

对区间进行快速加法操作

一维

1
2
3
4
5
6
7
8
9
// 若有原数组则要分开处理，最后加上原数组或者进行以下处理
v[i] = original[i] - original[i - 1];
void add(int l, int r, int x, vector<int> & v){
	v[l] += x;
	v[r + 1] -= x;
}
for(int i = 1; i <= n; i ++){
    v[i] += v[i - 1];
}

二维

1
2
3
4
5
6
7
8
// 和原数组分开处理，最后加上原数组，或者进行以下处理
v[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];
void add(int x1, int y1, int x2, int y2, int val, vector<vector<int>> v){
	v[x1][y1] += val;
    v[x2 + 1][y1] -= val;
    v[x1][y2 + 1] -= val;
    v[x2 + 1][y2 + 1] += val;
}

序列/数组问题

最长公共子序列

递归/递推+路径

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
#include<bits/stdc++.h>
using namespace std;
// 递归版
int n, m;
string s1, s2;
vector<vector<int>> dp(1001, vector<int>(1001, -1));
int F1(int i, int j){
    if(i == n || j == n){
        return 0;
    }else{
        if(dp[i][j] != -1) return dp[i][j];
        int ans = 0;
        if(s1[i] == s2[j]){
            ans = max({F1(i + 1, j + 1) + 1, F1(i + 1, j), F1(i , j + 1)});
        }else{
            ans = max(F1(i + 1, j), F1(i, j + 1));
        }
        dp[i][j] = ans;
        return ans;
    }
}
// 递推版
void F2(){
    string s1, s2;
    cin >> s1 >> s2;
    int n = s1.size(), m = s2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            if(s1[i - 1] == s2[ j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else{
                dp[i][j] = max(dp[i - 1][j], dp[i][ j - 1]);
            }
        }
    }
    // 求路径
    string s;
    for(int i = n, j = m; i && j;){
    	if(s1[i - 1] == s2[j - 1]){
    		s += s1[i - 1];
    		i --;
    		j --;
    	}else{
    		if(dp[i - 1][j] > dp[i][j - 1]) i --;
    		else j --;
    	}
    }
    if(s.size() == 0){
    	cout << -1 << "\n";
    	return 0;
    }
    for(int i = 0, j = s.size() - 1; i < j; i ++, j --) swap(s[i], s[j]);
    cout << s << "\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
#include<bits/stdc++.h>
using namespace std;
int F1(int x, vector<int> & v){
    int l = 0;
    int r = v.size() - 1;
    int ans = -1;
    int mid;
    while(l <= r){
        mid = (l + r) >> 1;
        if(x < v[mid]) l = mid + 1;
        else{
            r = mid - 1;
            ans = mid;
        }
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> v2(n + 1), temp(n + 1);
    for(int i = 1, x; i <= n; i ++){
        cin >> x;
        temp[x] = i;
    }
    for(int i = 1; i <= n ; i ++){
        cin >> v2[i];  
        v2[i] = temp[v2[i]];
    }
    vector<int> ans;
    for(int i = n, x; i; i --){
        x = F1(v2[i], ans);
        if(x == -1){
            ans.push_back(v2[i]);
        }else{
            ans[x] = v2[i];
        }
    }
    cout << ans.size() << "\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
#include<bits/stdc++.h>
using namespace std;
int F1(int x, vector<int> & v){
	int ans = -1;
	int l = 0;
	int r = v.size() - 1;
	int mid;
	while(l <= r){
		mid = (l + r) >> 1;
		if(x < v[mid]){
			l = mid + 1;
		}else{
			r = mid - 1;
			ans = mid;
		}
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	vector<int> v1(n);
	for(auto& x : v1) cin >> x;
	vector<int> v2;
	vector<int> dp(n);
	for(int i = n - 1, ans; i >= 0; i --){
		ans = F1(v1[i], v2);
		if(ans == -1){
			v2.push_back(v1[i]);
			dp[i] = v2.size();
		}else{
			v2[ans] = v1[i];
			dp[i] = ans + 1;
		}
	}
	int m = v2.size();
	vector<int> ans(m, 1e9);
	for(auto x : dp) cout << x << " ";cout << "\n";
	for(int i = 0, x; i < n; i ++){
		x = dp[i];
		if(x == m) ans[0] = v1[i];
		else{
			if(ans[m - x - 1] < v1[i]){
				ans[m - x] = v1[i];
			}
		}
	}
	for(int i = 0; i < m; i ++){
		cout << ans[i];
		if(i != m) cout << " ";
	}
	cout << "\n";
	return 0;
}

累加和不大于k的最长子数组

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
#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	int k;
	cin >> n >> k;
	vector<int> v1(n, 0);
	for(auto & x : v1) cin >> x;
	vector<int> min1(n);
	vector<int> minend(n);
	min1[n - 1] = v1[n - 1];
	minend[n - 1] = n - 1;
	for(int i = n - 2; i >= 0; i --){
		if(min1[i + 1] <= 0){
			min1[i] = v1[i] + min1[i + 1];
			minend[i] = minend[i + 1];
		}else{
			min1[i] = v1[i];
			minend[i] = i;
		}
	}
	int ans = 0;
	for(int i = 0, sum1 = 0, r = 0; i < n; i ++){
		while(r < n  && sum1 + min1[r] <= k){
			sum1 += min1[r];
			r = minend[r] + 1;
		}
		if(r > i){
			ans = max(ans, r - i);
			sum1 -= v1[i];
		}else r = i + 1;
	}
	cout << ans << "\n";
	return 0;
}

DP

数位DP

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
// 数位dp https://www.luogu.com.cn/problem/P2602
#include<bits/stdc++.h>
using namespace std;
#define int long long
int F(int n, int d){
    int ans = 0;
    for(int cur, temp = n, l, r = 1; temp; r *= 10, temp /= 10){
        cur = temp % 10;
        l = temp / 10;
        if(d == 0) l --;
        ans += l * r;
        if(d < cur){
            ans += r;
        }else if(d == cur){
            ans += n % r + 1;
        }
    }
    return ans;
}
signed main(){
    int l, r;
    cin >> l >> r;
    for(int i = 0; i < 10; i ++){
        cout << F(r, i) - F(l - 1, i);
        if(i != 9) cout << " ";
    }
    return 0;
}
// https://www.luogu.com.cn/problem/P3413
constexpr int mod = 1e9 + 7;
bool is(string s){
    for(int i = 1, j; i < s.size(); i ++){
        j = i - 2;
        if((j >= 0 && s[j] == s[i]) || s[i] == s[i - 1]) return false;
    }
    return true;
}
// 统计0-n中所有不是回文数的数 f1表示是否选过数 f2表示是否可以任意选
int F(int i1, string s, int l, int ll, bool f1, bool f2){
    if(i1 == s.size()) return 1;
    int ans = 0;
    if(!f1){
        ans = (ans + F(i1 + 1, s, -1, -1, false, true)) % mod;
        if(!f2){
            for(int i = 1; i < s[i1] - '0'; i ++){
                if(i != l && i != ll){
                    ans = (ans + F(i1 + 1, s, i, l, true, true)) % mod;
                }
            }
            if(s[i1] - '0' != l && s[i1] - '0' != ll) ans = (ans + F(i1 + 1, s, s[i1] - '0', l, true, false)) % mod;
        }else{
            int sum = 9;
            if(++i1 != s.size()) sum *= 9;
            while(++i1 < s.size()){
                sum = (sum * 8) % mod;
            }
            ans = (ans + sum) % mod;
        }
    }else{
        if(!f2){
            for(int i = 0; i < s[i1] - '0'; i ++){
                if(i != l && i != ll){
                    ans = (ans + F(i1 + 1, s, i, l, true, true)) % mod;
                }
            }
            if(s[i1] - '0' != l && s[i1] - '0' != ll) ans = (ans + F(i1 + 1, s, s[i1] - '0', l, true, false)) % mod;
        }else{
            int sum;
            if(ll == -1){
                sum = 9;
                while(++ i1 < s.size()){
                    sum = (sum * 8) % mod;
                }
            }else{
                sum = 8;
                while(++ i1 < s.size()){
                    sum = (sum * 8) % mod;
                }
            }
            ans = (ans + sum) % mod;
        }
    }
    return ans;
}
// 统计0-n中的所有数 f1表示是否选过数 f2表示是否可以任意选
int F2(int i1, string s, bool f1, bool f2){
    if(i1 == s.size()) return 1;
    int ans = 0;
    if(!f1){
        ans = (ans + F2(i1 + 1, s, false, true)) % mod;
        if(!f2){
            for(int i = 1; i < s[i1] - '0'; i ++){
                ans = (ans + F2(i1 + 1, s, true, true)) % mod;
            }
            ans = (ans + F2(i1 + 1, s, true, false)) % mod;
        }else{
            int sum = 9; // 不能为零
            while(++ i1 < s.size()){
                sum = (sum * 10) % mod;
            }
            ans = (ans + sum) % mod;
        }
    }else{
        if(!f2){
            for(int i = 0; i < s[i1] - '0'; i ++){
                ans = (ans + F2(i1 + 1, s, true, true)) % mod;
            }
            ans = (ans + F2(i1 + 1, s, true, false)) % mod;
        }else{
            int sum = 10; // 能为零
            while(++ i1 < s.size()){
                sum = (sum * 10) % mod;
            }
            ans = (ans + sum) % mod;
        }
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s1, s2;
    cin >> s1 >> s2;
    int n1 = F(0, s1, -1, -1, false, false);
    int n2 = F(0, s2, -1, -1, false, false);
    int ans1 = (n2 - n1  + is(s1) + mod) % mod;
    int n3 = F2(0, s1, false, false);
    int n4 = F2(0, s2, false ,false);
    int ans2 = (n4 - n3 + 1 + mod) % mod;
    cout << (ans2 - ans1 + mod) % mod << "\n";
    return 0;
}

树形DP

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
#include <bits/stdc++.h>
using namespace std;
// https://pintia.cn/problem-sets/1859417373569925120/exam/problems/type/7?problemSetProblemId=1859417373590896646
#define int long long
#define fr first
#define sc second
struct my{
	int w, b;
	priority_queue<int, vector<int>, greater<>> qw, qb;
};
signed main(){
	cin.tie(0) -> ios::sync_with_stdio(0);
	int t = 1;
    // cin >> t;
    while (t--){
    	int n;
    	cin >> n;
    	vector<int> color(n + 1), val(n + 1), root(n + 1, 0);
    	vector adj(n + 1, vector<int>());
    	for(int i = 1; i <= n; i ++){
    		int m;
    		cin >> color[i] >> val[i] >> m;
    		for(int j = 0; j < m; j ++){
    			int v;
    			cin >> v;
    			adj[i].push_back(v);
    			root[v] --;
    		}
    	}
    	int ans = 0;
        // 传回可以被改色的节点
		auto F = [&](auto && f, int u) -> my {
			int w1 = 0, b1 = 0;
			priority_queue<int, vector<int>, greater<>> qw1, qb1;
			for(auto v : adj[u]){
				my temp = f(f, v);
				w1 += temp.w;
				b1 += temp.b;
				while(!temp.qw.empty()){
					qw1.push(temp.qw.top());
					temp.qw.pop();
				}
				while(!temp.qb.empty()){
					qb1.push(temp.qb.top());
					temp.qb.pop();
				}
			}
			// cout << u << " " << w1 << " " << b1 <<  "\n";
			// priority_queue<int, vector<int>, greater<>> q11 = qw1, q22 = qb1;
			// cout << "w: ";
			// while(!q11.empty()){
				// cout << q11.top() << " ";
				// q11.pop();
			// }cout << "\n";
			// cout << "b: ";
			// while(!q22.empty()){
				// cout << q22.top() << " ";
				// q22.pop();
			// }cout << "\n";
			my temp;
			priority_queue<int, vector<int>, greater<>> q1, q2;
			temp.w = temp.b = 0;
			if(color[u] == 0){
				temp.w ++;
				q1.push(val[u]);
			}else{
				temp.b ++;
				q2.push(val[u]);
			}
			if(w1 != b1){
				if(abs(w1 - b1) == 1){
					if(w1 > b1){
						q1.push(qw1.top());
					}else{
						q2.push(qb1.top());
					}
				}else{
					while(abs(w1 - b1) >= 2){
						if(w1 > b1){
							ans += qw1.top();
							qw1.pop();
							w1 --, b1 ++;
						}else{
							ans += qb1.top();
							qb1.pop();
							w1 --, b1 ++;
						}
					}
				}
			}
			temp.qw = q1, temp.qb = q2;
			temp.w += w1, temp.b += b1;
			return temp;
		};
		for(int i = 1; i <= n; i ++){
			if(root[i] == 0){
				F(F, i);
				break;
			}
		}
    	cout << ans << "\n";
	}
    return 0;
}

区间DP

一般的区间DP是$O(n^{4})$复杂度，但可以在第三层时通过搜索优化达到$O(n^{3}log\ n)$.

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
// https://ac.nowcoder.com/acm/contest/108298/I
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
signed main(){
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int t = 1;
    cin >> t;
	while(t --){
		int n;
		cin >> n;
		vector<int> v1(n + 1), pre(n + 1);
		pre[0] = 0;
		for(int i = 1; i <= n; i ++) cin >> v1[i], pre[i] = pre[i - 1] + v1[i];
		vector dp(n + 1, vector(n + 1, vector<pair<int,int>>()));
		for(int i = 1; i <= n; i ++) dp[i][i].push_back({0ll, 0ll});
		auto get = [&](int x, vector<pair<int,int>> & v) -> int {
			int l = 0, r = v.size() - 1;
			int mid, ans = -1;
			while(l <= r) {
				mid = l + r >> 1;
				if(v[mid].sc <= x) {
					ans = v[mid].fr;
					l = mid + 1;
				} else r = mid - 1;
			}
			return ans;
		};
		for(int len = 2, dif, val_l, val_r, cost, cost_l, cost_r; len <= n; len ++) {
			for(int l = 1, r = l + len - 1; r <= n; l ++, r ++) {
                // 优化位置
				for(int k = l; k < r; k ++) {
					val_l = pre[k] - pre[l - 1], val_r = pre[r] - pre[k];
					dif = abs(val_l - val_r);
					int cost = min(val_l, val_r) * ceil(log2(val_l + val_r));
                    // 快速搜索
					cost_l = get(dif, dp[l][k]), cost_r = get(dif, dp[k + 1][r]);
					if(len == n) {
						if(cost_l == -1 || cost_r == -1) cout << "-1 ";
						else cout << cost_l + cost + cost_r << " ";
						continue;
					}
					if(cost_l == -1 || cost_r == -1) continue;
					dp[l][r].push_back({cost_l + cost + cost_r, dif});
				}
                // 优化策略
				sort(dp[l][r].begin(), dp[l][r].end(), [&](const pair<int,int> & a, const pair<int,int> & b){
					if(a.sc == b.sc) return a.fr < b.fr;
					return a.sc < b.sc;
				});
				for(int i = 1; i < dp[l][r].size(); i ++) dp[l][r][i].fr = min(dp[l][r][i].fr, dp[l][r][i - 1].fr);
			}
		}
		cout << "\n";
    }
    return 0;
}

Fliegel–Van Flandern 算法

这个算法可以将从公元前4713年1月1日（即儒略日JD=0）起计算的**儒略日数（JD）**转换为公历日期（年、月、日），并自动判断是在儒略历还是格里历中（1582年10月15日为切换点）。

  • JD ≥ 2299161：采用格里历（即1582年10月15日之后）
  • JD < 2299161：采用儒略历
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
// Fliegel–Van Flandern 算法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void julianDayToDate(ll JD, ll &day, ll &month, ll &year, bool &isBC) {
    ll A, B, C, D, E;
    if (JD >= 2299161) { 
        double alpha = floor((JD - 1867216.25) / 36524.25);
        A = JD + 1 + alpha - floor(alpha / 4.0);
    }
    else { 
        A = JD;
    }
    B = A + 1524;
    C = floor((double)(B - 122.1) / 365.25);
    D = floor(365.25 * (double)C);
    E = floor((double)(B - D) / 30.6001);
    day = B - D - floor(30.6001 * E);
    if (E < 14)
        month = E - 1;
    else
        month = E - 13;

    if (month > 2)
        year = C - 4716;
    else
        year = C - 4715;

    if (year <= 0) {
        isBC = true;
        day = day;
        month = month;
        year = -(year) + 1;
    }
    else {
        isBC = false;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll Q;
    cin >> Q;
    while(Q--){
        ll JD;
        cin >> JD;
        ll day, month, year;
        bool isBC = false;
        julianDayToDate(JD, day, month, year, isBC);
        if(isBC){
            cout << day << " " << month << " " << year << " BC\n";
        }
        else{
            cout << day << " " << month << " " << year << "\n";
        }
    }
    return 0;
}

逆波兰式

逆波兰表达式（Reverse Polish Notation，简称 RPN），也称为后缀表达式，是一种将运算符放在操作数之后的数学表达方式。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod1 1000000007
constexpr int N = 3e5 + 1;
vector<ll> stack1(N,0);
int size1;
ll a;
ll b;
ll ans;
void solve(void){
    size1 = 0;
    string s;
    getline(cin,s);
    istringstream ios(s);
    string token;
    while(ios >> token){
        if(isdigit(token[0])){
            stack1[size1++] = stoll(token);
            // cout << stoll(token) << "\n";
        }else{
            b = stack1[--size1];
            a = stack1[--size1];
            // cout << a << " " << b << "\n";
            if(token == "+"){
                ans = (a + b) % mod1;
            }else if(token == "-"){
                ans = (a - b) % mod1;
            }else if(token == "*"){
                ans = (a * b) % mod1;
            }else{
                ans = (a / b) % mod1;
            }
            // cout << ans << "\n";
            stack1[size1++] = ans;
        }
    }
    cout << stack1[size1 - 1] << "\n";
}

约瑟夫环

约瑟夫环问题描述的是一群人围成一圈，每隔固定人数（即第 k 个人）被淘汰，直到最后剩下一个人。最后存活的人的位置可以通过下面的递推式来求解：

假设只有 1 个人时，存活的位置为 0（注意：这里用 0 表示编号，从 0 开始）；当有 i 个人时，可以利用 i-1 个人的结果递推出 i 个人的情况。
递推公式为：

f(i) = (f(i−1) + k ) mod  i

其中，f(i)表示 i 个人时最后存活者的编号。

i = 1 时，f[i]显然等于0

1
2
3
4
5
6
7
int josephus(int n, int k) {
    int result = 0; // 初始只有一个人时，位置是 0
    for (int i = 2; i <= n; i++) {
        result = (result + k) % i;
    }
    return result;
}

离散化

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
signed main(){
	cin.tie(0) -> ios::sync_with_stdio(0);
	int t = 1;
    // cin >> t;
    while (t--){
    	int n;
    	cin >> n;
    	vector<int> v1(n + 1), ord(n + 1);
    	for(int i = 1; i <= n; i ++){
    		cin >> v1[i];
    		ord[i] = v1[i];
    	}
    	sort(ord.begin() + 1, ord.end());
    	int m = 1;
    	for(int i = 2; i <= n; i ++){
    		if(ord[m] != ord[i]){
    			ord[++ m] = ord[i];
    		}
    	}
    	auto find = [&](int x) -> int {
    		int l = 1, r = m;
    		int mid, ans;
    		while(l <= r){
    			mid = (l + r) >> 1;
    			if(x >= ord[mid]){
    				ans = mid;
    				l = mid + 1;
    			}else{
    				r = mid - 1;
    			}
    		}
    		return ans;
    	};
    	for(int i = 1; i <= n; i++){
            cout << "after: " << find(v1[i]) << "\n";
        }
    }
    return 0;
}

N皇后问题

位运算版本

每次将状态进行左移和右移一位模拟对角线移动，而且利用位运算快速得到此行能够放置的位置

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
#include <bits/stdc++.h>
using namespace std;
int n;
vector<array<int,11>> sols;
void dfs(int row, int colMask, int d1Mask, int d2Mask, array<int,11>& col) {
    if (row == n) {
        sols.push_back(col);
        return;
    }
    int avail = ((1 << n) - 1) & ~(colMask | d1Mask | d2Mask); 
    while (avail) {
        int p = avail & -avail; 
        int c = __builtin_ctz(p);
        col[row] = c;
        dfs(row + 1,
            colMask | p,
            (d1Mask | p) << 1,
            (d2Mask | p) >> 1,
            col);
        avail ^= p;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	cin >> n;
    array<int,11> col{};
    dfs(0, 0, 0, 0, col);
    long long ans = 0;
    int S = sols.size();
    cout << S << '\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
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
// https://ac.nowcoder.com/acm/contest/108299/H
#include <bits/stdc++.h>
using namespace std;
// 使用 long long 防止溢出
#define int long long
#define fr first
#define sc second
// 最大节点数和最大边数，根据题目限制调整
constexpr int N = 1e5, M = 3e5;
// 邻接表存储
vector<int> head(N + 1), next1(M + 1), to(M + 1), weight(M + 1);
// 存储从 1 出发的最短距离、到 n 的最短距离
vector<int> d1(N + 1), d2(N + 1);
// 原始边信息
vector<int> u(M + 1), v(M + 1), w(M + 1), t1(M + 1);
// Dijkstra 标记用
vector<int> has(N + 1);
// 直线结构 y = k*x + b
struct line {
    int k, b;
};
// 用于维护下凸包的直线数组
vector<line> l1(M + 1), ans1(M + 1);
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        // 读入所有边
        for (int i = 1; i <= m; i++) {
            cin >> u[i] >> v[i] >> w[i] >> t1[i];
        }
        int cnt1 = 1;
        // 邻接表插入函数
        auto add = [&](int uu, int vv, int ww) {
            next1[cnt1] = head[uu];
            to[cnt1] = vv;
            weight[cnt1] = ww;
            head[uu] = cnt1++;
        };
        // Dijkstra 模板，in 表示起点
        auto dj = [&](vector<int> &d, int in) {
            // 重置图和距离
            fill(head.begin() + 1, head.begin() + n + 1, 0);
            fill(has.begin() + 1, has.begin() + n + 1, 0);
            fill(d.begin() + 1, d.begin() + n + 1, (int)1e18);
            cnt1 = 1;
            // 重新插入边
            for (int i = 1; i <= m; i++) {
                add(u[i], v[i], w[i]);
            }
            // 最小堆
            priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
            d[in] = 0;
            pq.push({0, in});
            while (!pq.empty()) {
                auto [dist, u0] = pq.top();
                pq.pop();
                if (has[u0]) continue;
                has[u0] = 1;
                // 松弛操作
                for (int ei = head[u0]; ei; ei = next1[ei]) {
                    int v0 = to[ei], wt = weight[ei];
                    if (d[u0] + wt < d[v0]) {
                        d[v0] = d[u0] + wt;
                        pq.push({d[v0], v0});
                    }
                }
            }
        };
        // 计算从 1 到各点的最短路
        dj(d1, 1);
        // 反向图：交换 u 和 v
        for (int i = 1; i <= m; i++) swap(u[i], v[i]);
        // 计算从 n 到各点的最短路（即原图各点到 n 的最短路）
        dj(d2, n);
        // 恢复原向边
        for (int i = 1; i <= m; i++) swap(u[i], v[i]);
        // 构造每条边对应的一条直线 l: y = -t1*x + (d1[u]+d2[v]+w)
        for (int i = 1; i <= m; i++) {
            l1[i] = line{-t1[i], d1[u[i]] + d2[v[i]] + w[i]};
        }
        // 按斜率 k 降序排序，若 k 相同，按截距 b 降序
        sort(l1.begin() + 1, l1.begin() + m + 1, [](auto &A, auto &B) {
            if (A.k == B.k) return A.b > B.b;
            return A.k > B.k;
        });
        // 计算两条直线相交的 x 坐标（向下取整）
        auto getX = [&](const line &A, const line &B) {
            // A.k > B.k 保证分母非负
            return (B.b - A.b) / (A.k - B.k);
        };
        // 维护下凸包
        int len = 0;
        for (int i = 1; i <= m; i++) {
            // 去掉失效的或不必要的直线
            while (len > 0) {
                // 如果新线在上一条线之上，则上一条线无效
                if (l1[i].b <= ans1[len-1].b) len--;
                // 或者相交点不递增，也要去掉上一条
                else if (len > 1 && getX(l1[i], ans1[len-1]) <= getX(ans1[len-1], ans1[len-2])) len--;
                else break;
            }
            ans1[len++] = l1[i];
        }
        // 处理查询
        int q; cin >> q;
        while (q--) {
            int x; cin >> x;
            // 二分找在凸包上对应 x 的最佳直线
            int l = 0, r = len - 2, best = 0;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (getX(ans1[mid], ans1[mid+1]) < x) {
                    best = mid + 1;
                    l = mid + 1;
                } else r = mid - 1;
            }
            // 输出答案
            cout << ans1[best].k * x + ans1[best].b << "\n";
        }
    }
    return 0;
}

FFT

核心思想

FFT（快速傅里叶变换）的目标是高效计算两个多项式的卷积。
设
$$
C(x) = A(x)B(x),\quad A(x)=\sum_{i=0}^n a_i x^i,\quad B(x)=\sum_{j=0}^m b_j x^j
$$

那么卷积的系数是：

$$
c_k = \sum_{i+j=k} a_i b_j
$$

朴素算法是枚举 $i,j$，复杂度 $O(n^2)$。FFT 的作用是利用 离散傅里叶变换（DFT） 的性质，把这个卷积问题降到 $O(n\log n)$。

离散傅里叶变换（DFT）与逆变换

给定序列 $a_0,a_1,\dots,a_{n-1}$，定义 DFT：

$$
A_k = \sum_{j=0}^{n-1} a_j \cdot \omega_n^{jk}, \quad k=0,\dots,n-1
$$

其中

$$
\omega_n = e^{2\pi i / n}
$$

是 $n$ 次单位根。

逆变换公式为：

$$
a_j = \frac{1}{n} \sum_{k=0}^{n-1} A_k \cdot \omega_n^{-jk}
$$

性质：

  • 在点值表示下，多项式乘法等价于卷积。
  • 即：在频域做乘法，等价于时域做卷积。

卷积定理

  1. 把 $A(x),B(x)$ 变换到频域：
    得到 ${A(\omega_n^k)}, {B(\omega_n^k)}$

  2. 点值相乘：

    $$
    C(\omega_n^k) = A(\omega_n^k) \cdot B(\omega_n^k)
    $$

  3. 逆变换：
    得到 $C(x)$ 的系数。

因此，卷积过程就是：
FFT(A) → FFT(B) → 点乘 → IFFT。
总复杂度 $O(n\log n)$。

FFT 加速

如果直接算 DFT，需要 $O(n^2)$。
FFT 利用了分治思想：
$$
A(x) = A_{even}(x^2) + x A_{odd}(x^2)
$$

代入 $\omega_n^k$ 得到：

$$
A(\omega_n^k) = A_{even}(\omega_{n/2}^k) + \omega_n^k A_{odd}(\omega_{n/2}^k)
$$

这说明一个 $n$ 点 DFT 可以分解为两个 $n/2$ 点 DFT，再加上合并时的若干乘法。
递归展开，复杂度降为 $O(n\log n)$。

在代码层面，分治被转化为迭代形式：

  1. 位逆序重排：先将数组下标按二进制反转排序。
  2. 逐层蝴蝶操作：从长度 2 的小段开始，不断倍增，每一层都用旋转因子 $\omega$ 做合并。

蝴蝶操作形式为：

$$
u = a[i],\quad v = w \cdot a[i+mid]
$$

$$
a[i] = u+v,\quad a[i+mid] = u-v
$$

这就是代码中循环的核心。

代码关键点对应数学

  • for (int i = 0; i < tot; i++)：遍历 FFT 长度（tot 为最近的 2 次幂）。
  • 位逆序数组 rev[i]：保证每一层分治合并时顺序正确。
  • 每一层长度 len 翻倍，旋转因子 wn = exp(±2πi/len)。
  • if (op == 1) 正变换（FFT），if (op == -1) 逆变换（IFFT）。
  • 逆变换最后要除以 tot，对应公式里的 $1/n$。
  • <tot 而不是 <=tot：因为数组下标从 0 到 tot-1，总共 tot 个点。

在题目中的作用

在这道题里，给定两个多项式（或 01 串映射为系数数组），需要快速计算卷积。
FFT 的流程是：

  1. 读入序列，扩充到 2 次幂长度。
  2. FFT 变换。
  3. 点值相乘。
  4. IFFT 还原，得到卷积结果。
  5. 再做题目所需的“进制归约”（例如 $\sqrt{-2}$ 进位）。
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
// https://ac.nowcoder.com/acm/contest/108305/J
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fr first
#define sc second
constexpr int N = 3e5;
const double PI = acos(-1);
// 简单复数结构，支持 +,-,*
struct Complex{
    double x, y;
    Complex operator +(const Complex &t) const { return {x + t.x, y + t.y}; }
    Complex operator -(const Complex &t) const { return {x - t.x, y - t.y}; }
    Complex operator *(const Complex &t) const { return {x * t.x - y * t.y, x * t.y + y * t.x}; }
};
// 工作数组
vector<Complex> a(N + 1), b(N + 1);
vector<int> rev(N + 1), res(N << 1 | 1);
int bit, tot; // FFT 长度信息
signed main(){
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int t = 1;
    cin >> t;
    // FFT：inv=1 正变换, inv=-1 逆变换
    auto FFT = [&](vector<Complex> & v, int inv) {
        for(int i = 0; i < tot; i ++) if(i < rev[i]) swap(v[i], v[rev[i]]);
        for(int mid = 1; mid < tot; mid <<= 1) {
            Complex w1 = {cos(PI / mid), inv * sin(PI / mid)};
            for(int i = 0; i < tot; i += (mid << 1)) {
                Complex wk = {1, 0};
                for(int j = 0; j < mid; j ++, wk = wk * w1) {
                    Complex x = v[i + j], y = wk * v[i + j + mid];
                    v[i + j] = x + y;
                    v[i + j + mid] = x - y;
                }
            }
        }
    };
    while(t --) { 
        string s1, s2;
        cin >> s1 >> s2;
        int n1 = s1.size(), n2 = s2.size();
        // 低位在前存储
        for(int i = 0; i < n1; i ++) a[i] = {double(s1[n1 - i - 1] - '0'), 0};
        for(int i = 0; i < n2; i ++) b[i] = {double(s2[n2 - i - 1] - '0'), 0};
        // 取最近 2 次幂长度
        bit = 0;
        while((1 << bit) < n1 + n2 - 1) bit ++;
        tot = 1 << bit;
        // 补 0
        for(int i = n1; i < tot; i ++) a[i] = {0, 0};
        for(int i = n2; i < tot; i ++) b[i] = {0, 0};
        // 位逆序表
        for(int i = 0; i < tot; i ++)
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
        // FFT → 逐点相乘 → IFFT
        FFT(a, 1), FFT(b, 1);
        for(int i = 0; i < tot; i ++) a[i] = a[i] * b[i];
        FFT(a, -1);
        // 卷积结果（未进位）
        int len = 0;
        for (int i = 0; i < n1 + n2 - 1; ++i)
            res[i] = (int)(a[i].x / tot + 0.5);
        // √-2 进制进位归约
        for(len = 0; len < n1 + n2 - 1 || res[len + 1] || res[len]; len ++) {
            if(res[len] < 0) {
                res[len] = -res[len];
                res[len + 2] += res[len];
            }
            if(res[len] > 0) {
                res[len + 2] -= res[len] >> 1;
                res[len] %= 2;
            }
        }
        // 去掉前导 0
        while(len > 1 && !res[len - 1]) len --;
        // 输出（高位在前）
        for(int i = len - 1; i >= 0; i --) cout << char('0' + res[i]);
        cout << "\n";
        // 清理
        fill(res.begin(), res.begin() + len + 1, 0);
    }
    return 0;
}

容器

set

基于红黑树实现的自动排序、无重复元素的关联容器

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
#include <set>
using namespace std;
set<int> s;                  // 升序，默认 less<int>
set<string> names;
set<int, greater<int>> s2;   // 降序排列
s.insert(5);    // 插入 5，若已存在则无效
s.erase(5);       // 删除值为5的元素
s.erase(it);      // 通过迭代器删除
s.erase(s.begin(), s.end()); // 清空
auto it = s.find(5);     // 找到返回迭代器，否则为 s.end()
if (it != s.end()) cout << *it << " found\n";
if (s.count(5)) cout << "存在";
s.size();
s.empty();
s.clear();
for (auto it = s.begin(); it != s.end(); ++it)
    cout << *it << " ";
for (int x : s)
    cout << x << " ";
auto it1 = s.lower_bound(5); // 返回 ≥ 5 的第一个元素迭代器
auto it2 = s.upper_bound(5); // 返回 > 5 的第一个元素迭代器
struct cmp {
    bool operator()(const pair<int,int>& a, const pair<int,int>& b) const {
        return a.first < b.first;  // 可定义复合排序规则
    }
};
set<pair<int,int>, cmp> s;

插入/删除/查找都是O(log n)

ordered_set

解释各个部分的作用

代码部分 功能 说明
s.insert(5) 插入元素 ordered_set 自动去重
s.erase(7) 删除元素 需先检查元素是否存在
find_by_order(k) 获取第 k 小元素 0-based，需先检查是否为空
order_of_key(10) 获取小于某个值的元素数量 O(log n) 复杂度
find(5) 查找元素 直接返回迭代器
s.size() 获取集合大小 O(1) 复杂度
s.clear() 清空集合 直接清空

时间复杂度

  • 插入：O(log n)
  • 删除：O(log n)
  • 查找：O(log n)
  • 获取第 k 小元素：O(log n)
  • 获取小于 x 的元素数量：O(log n)
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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<
    int, 
    null_type, 
    less<int>, 
    rb_tree_tag, 
    tree_order_statistics_node_update
> ordered_set;

using namespace std;

int main() {
    ordered_set s;
    s.insert(5);
    if (s.find(7) != s.end()) s.erase(7);
    if (s.size() > 1) {
        cout << "The 2nd smallest element is: " << *s.find_by_order(1) << '\n';
    }
    if (s.find(5) != s.end()) {
        cout << "5 exists in the set\n";
    }
    if (!s.empty()) {
        cout << "Minimum element: " << *s.find_by_order(0) << '\n';
        cout << "Maximum element: " << *s.find_by_order(s.size() - 1) << '\n';
    }
    s.clear();
    return 0;
}

string

数值与字符串转化

函数签名 作用说明
to_string(val) 把 val 转换成 string
stoi(s, p, b) 把字符串 s 从下标 p 开始转换成 b 进制的 int
stol(s, p, b) 转换成 long
stoul(s, p, b) 转换成 unsigned long
stoll(s, p, b) 转换成 long long
stoull(s, p, b) 转换成 unsigned long long
stof(s, p, b) 转换成 float
stod(s, p, b) 转换成 double
stold(s, p, b) 转换成 long double

p 和 b可省，默认为十进制

字符串输入与分割

getline(cin, s)

stringstream s(ss)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
string s1;
getline(cin, s1);
vector<int> v1;
stringstream ss(s1);
string temp;
// while(ss >> temp) 按空格读取
while(getline(ss, temp, ',')){
    if(temp[0] == '-'){
        temp = temp.substr(1);
        v1.push_back(-stoi(temp));
    } else {
        v1.push_back(stoi(temp));
    }
}

改变大小写

1
2
3
4
5
6
7
8
9
10
11
transform(起点, 终点, 输出位置, 处理函数)
// 变小写
transform(s1.begin(), s1.end(), s1.begin(), ::tolower);
// 变大写
transform(s1.begin(), s1.end(), s1.begin(), ::toupper);
// 转换到另一个字符串
string src = "Hello";
string dest;
dest.resize(src.size());
transform(src.begin(), src.end(), dest.begin(), ::tolower);
// dest 现在是 "hello"，原始 src 不变

子串substr

substr(st, len)

len省略时表示到en

查找

find
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    std::string str ("There are two needles in this haystack with needles.");
    std::string str2 ("needle");
    //在str当中查找第一个出现的needle，找到则返回出现的位置，否则返回结尾
    std::size_t found = str.find(str2);
    if (found!=std::string::npos) // 结尾
    //在str当中，从第found+1的位置开始查找参数字符串的前6个字符
    found = str.find("needles are small",found+1,6);
}
rfind
1
2
//rfind是找最后一个出现的匹配字符串
std::size_t found = str.rfind(str2);
find_...of
1
2
3
4
find_first_of(args) // **查找args中任何一个字符第一次出现的位置**
find_last_of(args) // **最后一个出现的位置**
find_fist_not_of(args) // **查找第一个不在args中的字符**
find_last_not_of // **查找最后一个不在args中出现的字符**

插入insert

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    string str="to be question";
    string str2="the ";
    string str3="or not to be";
    string::iterator it;
    //s.insert(pos,str)//在s的pos位置插入str
    str.insert(6,str2); 
    //s.insert(pos,str,a,n)在s的pos位置插入str中插入位置a到后面的n个字符
    str.insert(6,str3,3,4);
    //s.insert(pos,cstr,n)//在pos位置插入cstr字符串从开始到后面的n个字符
    str.insert(10,"that is cool",8); 
    //s.insert(pos,n,ch)在s.pos位置上面插入n个ch
    str.insert(15,1,':')
    //s.insert(s.it,ch)在s的it指向位置前面插入一个字符ch，返回新插入的位置的迭代器
    it = str.insert(str.begin()+5,','); // to be, not to be: that is the question
    //s.insert(s.it,n,ch)//在s的it所指向位置的前面插入n个ch
    str.insert (str.end(),3,'.');
    //s.insert(it,str.ita,str.itb)在it所指向的位置的前面插入[ita,itb)的字符串
    str.insert (it+2,str3.begin(),str3.begin()+3);
    return 0;
}

map & unordered_map

map基于红黑树（或其他平衡二叉树）实现，所有元素按照key的大小有序存储。

unordered_map基于哈希表实现，元素按照哈希桶无序存储。

操作 map unordered_map
查找/插入/删除 O(logN)（严格） 平均O(1),最坏O(N)（哈希冲突）

如果对 key 的顺序有需求，或数据量不极端、性能要求严格稳定，就用 map。

如果数据随机分布、对遍历顺序无要求，希望获得极快的平均查找速度，可用 unordered_map，但要注意：

  1. 适当 reserve：提前 reserve(bucket_count) 或 max_load_factor 来减少扩容；
  2. 自定义哈希：在 CF 等平台上可用 splitmix64 等更安全的哈希函数，防止碰撞攻击。

tips

重载运算符号（比较）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 结构体
struct my{
    int l, r, index;
    my(int a, int b, int c){
        l = a, r = b, index = c;
    }
    bool operator < (const my x) const {  
            // 优先队列中比较关系反着来
            return l > x.l;
    }  
};
// lambda（示例为小根堆）
auto cmp = [](pair<int, int> x, pair<int, int> y) {
    return x.second > y.second;
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);

求最大的最小或者最小的最大问题

大概率是用二分来查询最合适的答案，具体算法看题

圆周率π

1
const double pi  =  acos(-1);

求容器最大值

1
*max_element(vec.begin(), vec.end());

全排列

1
2
3
4
5
std::string s = "aba"; 
do{
    std::cout << s << '\n';
}while (std::next_permutation(s.begin(), s.end()));
std::cout << s << '\n';

求二维平面上的三角形面积

给定三个顶点

1
2
3
4
S = abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2;
// or
S = abs((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) / 2;
// 两个参数相较于三个参数，有如下优势，可以取一个坐标为基准（2坐标与1坐标，3坐标与1坐标，每个参数都进行了一次碰面），进行点与点之间的逻辑处理，如判断处坐标异或值

给定三条边

1
2
p = (a + b + c) / 2;
S = sqrt(p * (p -a ) * (p - b) * (p - c));

求三维空间中两条直线最短距离

L1经过A(x1, y1, z1), B(x2, y2, z2)

L2经过 C(x3, y3, z3), D(x4, y4, z4)

L1的方向向量d1 = B - A, L2的方向向量d2 = D - C

n = d1 * d2

如果n为0,则两直线平行

任选L1上的点A和L2上的点C，计算AC = C - A

不平行时，两直线最短距离d = |AC .* n| / |n|

平行时，d = |AC * d1| / |d1|

不平行情况
$$
若 \vec{d_1} \times \vec{d_2} \neq 0，则最短距离公式为
$$

$$
d = \frac{\left| (C - A) \cdot \bigl(\vec{d_1} \times \vec{d_2}\bigr) \right|}{|\vec{d_1} \times \vec{d_2}|}.
$$

其中：
$$
(C - A) 表示向量，
\cdot 为点乘，
\times 为叉乘。
$$

$$
该公式的几何意义是：\vec{d_1} \times \vec{d_2} 垂直于两条直线，(C - A) 在此垂直方向上的投影长度即为两条直线的最短距离。
$$

平行情况
$$
若 \vec{d_1} \times \vec{d_2} = 0，则说明两条直线平行或重合。此时最短距离可以由下式给出：
$$

$$
d = \frac{|(C - A) \times \vec{d_1}|}{|\vec{d_1}|}.
$$

如果出现退化情况（例如 A=B 或 C=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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
// baidu 14 2
struct point{
	double x, y, z;
	point(double x1 = 0, double y1 = 0, double z1 = 0): x(x1), y(y1), z(z1) {}
};
signed main(){
	cin.tie(0) -> ios::sync_with_stdio(0);
	int t = 1;
    cin >> t;
    while (t--){
    	double x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4;
    	cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2 >> x3 >> y3 >> z3 >> x4 >> y4 >> z4;
    	point a = point{x1, y1, z1}, b = {x2, y2, z2}, c = {x3, y3, z3}, d = {x4, y4, z4};
    	// 向量减法：返回 b - a
    	auto vecSub = [](const point & a, const point & b) -> point {
    		point temp = point(b.x - a.x, b.y - a.y, b.z - a.z);
    		return temp;
    	};
    	// 向量叉乘 (仅适用于 3D)
    	auto crossProduct = [](const point & a, const point & b) -> point{
    		point temp = point(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x);
    		return temp;
    	};
    	// 向量点乘
    	auto dotProduct = [](const point & a, const point & b) -> double {
    		return a.x * b.x + a.y * b.y + a.z * b.z;
    	};
    	// 向量的模长
    	auto norm = [](const point & a) -> double {
    		return sqrt(a.x * a.x + a.y * a.y + a.z * a.z);
    	};
    	point d1 = vecSub(a, b), d2 = vecSub(c, d); 
    	point n = crossProduct(d1, d2);
    	double norm_n = norm(n);
    	point AC = vecSub(c, a);
    	double distance = 0.0;
    	// 如果 n != 0，说明两条直线不平行
    	if(fabs(norm_n) > 1e-12){
    		// 最短距离公式: |(C - A) · (d1 x d2)| / ||d1 x d2||
    		distance = fabs(dotProduct(AC, n)) / norm_n;
    	}else{
    		// n = 0，说明两条直线平行或共线
		    // 使用平行直线距离公式: ||(C - A) x d1|| / ||d1||
		    point temp1 = crossProduct(AC, d1);
		    double norm_temp1 = norm(temp1), norm_d1 = norm(d1);
		    if(fabs(norm_d1) < 1e-12){
		    	// 若 d1Norm=0，说明 A、B 是同一点；若 d2Norm=0，C、D 同理。此时需特殊处理
		    	double norm_d2 = norm(d2);
		    	if(fabs(norm_d2) < 1e-12){
		    		// 两条“直线”都是点，计算 A 到 C 的距离
		    		distance = sqrt(pow(a.x - c.x, 2) + pow(a.y - c.y, 2) + pow(a.z - c.z, 2));
;		    	}else{
		    		// 只需计算点 A 到直线 CD 的距离
	                // 距离 = ||(C - A) x d2|| / ||d2||
	                point temp2 = crossProduct(AC, d2);
	                distance = norm(temp2) / norm(d2);
		    	}
		    }else{
		    	distance = norm(temp1) / norm(d1);
		    }
    	}
    	printf("%.3lf\n", distance);
	}
    return 0;
}

点到直线的距离公式 & 关系（三点之间）

设$P(x_0,,y_0)$为平面上一点， 直线 L 的方程为
$$
A x + B y + C = 0.
$$
则P到直线L的距离d为
$$
d = \frac{|,A x_0 + B y_0 + C,|}{\sqrt{A^2 + B^2}}.
$$

平面上三个点A()x1, y1), B(x2, y2), C(x3, y3), 判断点C与$\overrightarrow{AB}$的位置关系

S(A, B, C) = $\frac{(x1-x3)(y2-y3)-(y1-y3)(x2-x3)}{2}$

若S大于0，则C在矢量AB的左侧

若S小于0，则C在矢量AB的右侧

若S等于0，则C在直线AB上。

随机数

1
2
srand((unsigned)time(NULL));
cout << (rand()) % 17;

完全平方数

一个数为完全平方数当且仅当该分解后该数所有质因数个数均为偶数

随机哈希编码

1
2
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int a_hash = rng();

批量操作

1
2
3
4
5
6
7
8
9
int a[5];
// 连续填充
iota(a, a + 5, 1);  // a = {1, 2, 3, 4, 5}
// 适合设置为0、-1、255（即所有字节一致的值）
memset(a, 0, sizeof(a));  // 将数组 a 中的所有字节设为 0
// 支持所有基础类型和STL容器
vector<int> v;
fill(a, a + 5, 42);  // a = {42, 42, 42, 42, 42}
fill(v.begin(), v.end(), 42);

lower_bound & upper_bound

ower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

在从小到大的排序数组中，

  • lower_bound(begin, end, value)

    返回第一个 ≥ value 的位置

  • upper_bound(begin, end, value)
    返回第一个 > value 的位置

在从小到大的排序数组中，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    vector<int> v = {-1, 1, 2, 4, 7, 15, 34};
    sort(v.begin() + 1, v.end());

    int pos1 = lower_bound(v.begin() + 1, v.end(), 7) - v.begin();
    int pos2 = upper_bound(v.begin() + 1, v.end(), 7) - v.begin();
    cout << pos1 << " " << v[pos1] << endl;
    cout << pos2 << " " << v[pos2] << endl;

    sort(v.begin() + 1, v.end(), greater<int>());
    int pos3 = lower_bound(v.begin() + 1, v.end(), 7, greater<int>()) - v.begin();
    int pos4 = upper_bound(v.begin() + 1, v.end(), 7, greater<int>()) - v.begin();
    cout << pos3 << " " << v[pos3] << endl;
    cout << pos4 << " " << v[pos4] << endl;
    return 0;
}

折尺定理

一堆有各自长度($a_{1},a_{2},a_{3} \dots$)木棍能否连接在两个点上，取决于是否$L_{\min}\le D\le L_{\max}$,其中，$L_{\max} = \sum_{i = 1}^{n}a_{i} $ ,$L_{\min} = max(0, 2 * a_{\max} - L_{\max})$，D为两点间距离

两两绝对值求和

当你把一组数排序后，对所有「两两差的绝对值之和」$\sum_{0\le p<q\le n} |a_q - a_p|$ 有一个经典结论：

$\sum_{0 \le p < q \le n} (a_q - a_p)= \sum_{k=0}^n a_k (k - (n-k))$

这是因为：

  • 对于固定的$a_k$，它作为“右端” $q_{q}$ 的时候，会和前面所有 k 个更小的数 $a_0,\dots,a_{k-1}$ 相减，累计贡献

    $\displaystyle +,a_k\times k$。

  • 同时它也会作为“左端” $a_p$ 被后面所有 (n−k) 个更大的数 $a_{k+1},\dots,a_n$相减，贡献

    $-,a_k\times (n - k)$。

  • 合并起来，就是

    $a_k(k−(n−k))=a_k(2k−n).$

注意这里不需要再写绝对值了，因为排序保证了“后者减前者”总是非负的。

ASCII Table

ASCII_Table

优先级

priority

规模

guimo

隔板法（Stars and Bars）

无界非负整数组合

  • 题型：求非负整数解   $x_1+\cdots+x_k=N$ 的方案数
  • 答案：$\binom{N+k-1}{k-1}$
  • 含义：把 N 个「星星」放入 kk个「盒子」，盒子间用 k−1道隔板分隔。

单调序列差分

非增/非减序列（$a_1 \ge a_2 \ge \dots \ge a_k \ge 0$）可转为差分$d_i = a_i - a_{i - 1}$,再用隔板法算$\sum di = a_k - a_1$

普通生成函数（OGF）

定义

  • 给定序列 ${a_n}$，其 OGF 为
    $$
    A(t)=\sum_{n\ge0}a_n,t^n.
    $$

乘法对应「独立事件的卷积」

  • 若要把两类结构独立拼接，总方案数的序列是两生成函数相乘：
    $$
    A(t)\times B(t);\Longrightarrow; [t^n]\bigl(A(t)B(t)\bigr);=;\sum_{i+j=n}a_i,b_j.
    $$

幂运算

  • $A(t)^k$ 表示独立选取 k 份相同结构并联。

广义二项式与系数提取

广义二项式定理
$$
(1 - t)^{-\alpha} = \sum_{n=0}^\infty \binom{\alpha+n-1}{n},t^n, \quad \binom{\alpha+n-1}{n} = \frac{\alpha(\alpha+1)\cdots(\alpha+n-1)}{n!}.
$$
系数提取

  • 对于已知闭式 G(t)，常用：

    $[t^n],G(t) \quad\text{或}\quad \text{前缀和 }\sum_{i=0}^n [t^i]G(t).$

累加恒等式
$$
\sum_{i=0}^m \binom{i+r}{r} = \binom{m+r+1}{r+1}, \quad \sum_{i=0}^m \binom{r}{i} = \binom{r}{0}+\cdots+\binom{r}{m}.
$$

曼哈顿距离转换（菱形转矩形）

原菱形覆盖（曼哈顿距离$\le$）在（i,j）平面上难以直接判断，另u = i + j, v = i - j, 则菱形在(u, v)空间投影为轴对齐矩形

逆序对

一个排列中，交换任意两个数，会导致整个排列的逆序对个数奇偶性改变

证明: 交换任意两个数L和R（L < R，当L比R大时证明思路一致）,，L左边的和R右边的数对[L,R]内的数的贡献、(L,R)内的数相互之间的贡献不发生改变，再看(L,R)内，对于其中任意一个数，如果这个数在L和R中间，交换之前的该数与L和R的贡献值之和为0,那么L和R交换后，其贡献值还是2，若比L和R都小或者都大，交换前后的贡献值都是1，故不管三个数之间的关系是什么，改变都是偶数，都不改变总体奇偶性，而L和R的交换本身会带来绝对值为1的改变，故总体奇偶性最后改变

一个排列中，对任意区间进行循环单向移动时，当移动区间的长度为奇数时，每次移动的改变都是偶数，不改变奇偶，长度偶数时，每次移动的改变都是奇数，故每次移动都会改变奇偶，

证明：对于任何一个数，在长度为d的区间中，有a个数比他大，有b个数比他小，a + b = d - 1，两个数的和为偶数，那么两个数的差也为偶数，而将一侧的数循环移动到另一侧时，在循环左移时，其贡献就是b - a，因此，其奇偶性确定

组合数求和

$\sum_{i = 1}^{n} \frac{i * (i + 1)}{2}$的值为(n * (n + 1) * (n + 2)) / 6.

数位和之和

数位和的意思是对于f(100), 其值为每一位上的数之和，值为1+0+0=1,而对于f(123),其值同理为1+2+3=6.

若要求$zh$，方法如下，将视角转移至数位上，把所有数的数位以补零的方式与n的数位对齐，然后分三部分进行值的计算：

计算之前要指出，对于$10^{l}$次方以前的数，每一个$10^{l}$都对应着$l * 10^{l - 1}$个45，可自行枚举再稍加思考发现规律

  1. 当前数字以前的所有数字所对应的45的组数
  2. 当前位的当前数字以前的值之和
  3. 当前位的当前数字的和
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
// https://codeforces.com/contest/2132/problem/D
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
signed main(){
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int t = 1;
    cin >> t;   // 输入测试用例数量
    while(t --){
        int n;
        cin >> n;   // 输入 k（保留的总位数）
        // get(x): 计算从 1 拼到 x 一共用了多少位数字
        auto get = [&](int x) -> int {
            int len1 = 0;   // 记录总长度
            int p = 1;      // 当前区间的起始数：1, 10, 100, ...
            int d = 1;      // 当前区间的位数（1 位数，2 位数，...）
            // 先处理完整区间（例如 1~9, 10~99, ...）
            while(p * 10 <= x) {
                len1 += 9 * p * d;  // 该区间一共的位数 = 数字个数 * 位数
                d ++;
                p *= 10;
            }
            // 最后剩余区间（p..x）
            len1 += (x - p + 1) * d;
            return len1;
        };
        // 二分查找：找到最小的 ans 使得写到 ans 的位数 ≥ n
        int l = 1, r = 1e15, mid, ans;
        while(l <= r) {
            mid = (l + r) >> 1;
            if(get(mid) >= n) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        int val = 0; // 结果：数位和
        // 如果 get(ans) > n，说明 ans 的最后一个数可能多取了几位，需要回退
        if(get(ans) > n) {
            int x = ans;
            int len2 = get(ans --); // 先退到 ans-1
            // 继续退掉多余的位
            while(len2 > n) len2 --, x /= 10;
            // 把保留下来的 x 的每一位加到答案
            while(x) val += x % 10, x /= 10;
        }
        // 处理完整的部分（1 到 ans）
        if(ans) {
            string s = to_string(ans); // 把 ans 转成字符串
            int l = 1;    // 当前处理的位数
            int base = 1; // 位权
            int sum = 0;  // 前缀和（用来算贡献）   
            // 从低位到高位枚举 ans 的每一位
            for(auto i = s.rbegin(); i < s.rend(); i ++, base *= 10, l ++) {
                int x = *i - '0';  // 当前位的数值
                sum += x * base;
                // 复杂的公式：计算该位对数位和的贡献
                val += x * (x - 1) / 2 * base              // 当前位取 0..(x-1) 的贡献
                    + 45 * base / 10 * (l - 1) * x         // 低位的循环贡献
                    + x * (sum - x * base + 1);            // 高位固定时的贡献
            }
        }
        cout << val << "\n"; // 输出结果
    }
    return 0;
}

分层补齐高度问题

要把一个区间通过子区间加一的操作将区间统一高度，可以通过以下方法

  • 若i为第一个数，其代价为max - val[i]
  • 否则，当i要被填补的高度大于i - 1时，才进行高度差距的补充，类似与只有上楼梯才有消耗，下楼梯没有消耗，代价为(max - val[i]) - (max - val[i - 1])

而区间可容纳两种最终高度时，可dp每个点变为最终两个值中的某一个的代价，假设最终高度为x,y,可参考以下代码

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
constexpr int N = 400;
// dp[i][0/1]：处理到下标 i（0-based），并且把 v1[i] 提升到“高位 x(=0)”或“低位 y(=1)”时，
//             使得前缀 0..i 达到目标高度序列所需的最小“操作代价”
vector dp(N + 1, vector<int>(2));
signed main(){
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int t = 1;
    cin >> t;
   	while(t --){
		int n, m;
		cin >> n >> m;
		vector<int> v1(n);
		int max1 = 0;
		for(auto & x : v1) cin >> x, max1 = max(max1, x);
		int ans = 0;
		if(m == 1) {
			// 只允许选择 1 个“目标高度”时，最优即取 H = max(v1)
			// 下面这段等价于：把所有位置都“补到” H 的最少“前缀加一”操作次数。
			// 令 delta[i] = H - v1[i]，则
			// 代价 = delta[0] + Σ_{i=1..n-1} max(0, delta[i] - delta[i-1])
			for(int i = 0; i < n; i ++) {
				if(i == 0) ans += max1 - v1[i];
				else ans += max(0ll, (max1 - v1[i]) - (max1 - v1[i - 1]));
				//               ↑↑↑           即 delta[i] - delta[i-1]
			}
		} else {
		    // 允许选择 2 个“目标高度”：高位 x 与低位 y（并约束 y <= x）
		    // 我们要在每个位置自由选择 x 或 y，使得 h[i] >= v1[i] 且总代价最小。
		    auto get = [&](int x, int y) -> int {
		    	// 初始化 DP 为 +∞
		    	fill(dp.begin(), dp.begin() + 1 + n, vector<int>(2, 1e18));
		    	// i = 0 的转移：若 v1[0] 不超过目标位，则代价为补到该位的“新开层数”
		    	if(v1[0] <= x) dp[0][0] = x - v1[0];  // delta[0] = x - v1[0]
		    	if(v1[0] <= y) dp[0][1] = y - v1[0];  // delta[0] = y - v1[0]
		    	for(int i = 1; i < n; i ++) {
		    		// 若当前位置选择“高位 x”
		    		if(v1[i] <= x) {
		    			// 从上一位也是 x 转来：
		    			//  需要额外付出 max(0, (x - v[i]) - (x - v[i-1])) = max(0, delta[i]-delta[i-1])
		    			dp[i][0] = min({
		    				dp[i][0],
		    				dp[i - 1][0] + max(0ll, (x - v1[i]) - (x - v1[i - 1])),
		    				// 从上一位是 y 转来：
		    				//  比较 delta[i]=x-v[i] 与 前一位的 delta[i-1]=y-v[i-1]
		    				dp[i - 1][1] + max(0ll, (x - v1[i]) - (y - v1[i - 1]))
		    			});
		    		}
		    		// 若当前位置选择“低位 y”
		    		if(v1[i] <= y) {
		    			dp[i][1] = min({
		    				dp[i][1],
		    				dp[i - 1][0] + max(0ll, (y - v1[i]) - (x - v1[i - 1])),
		    				dp[i - 1][1] + max(0ll, (y - v1[i]) - (y - v1[i - 1]))
		    			});
		    		}
		    	}
		    	return min(dp[n - 1][0], dp[n - 1][1]);
		    };
		    // 穷举所有 (x, y)（0..200 且 y<=x）取最小值
		    // 注：范围 200 来自题面（或数据范围）假设
		    ans = 1e18;
			for(int i = 0; i <= 200; i ++)
				for(int j = 0; j <= i; j ++)
					ans = min(ans, get(i, j));
		}

		cout << ans << "\n";
    }
    return 0;
}

参考资料

字符串 CSDN

左程云

三角形面积

lower_bound & upper_bound

C++ 参考手册

ASCII WIKI

判断点与直线的位置关系

母函数

傅里叶变换

AVL树