algorithm

算法板子

算法汇总

算法

建图

三种建图方式

#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算法

普通堆

#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;
}

反向索引堆

#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,若不为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});
            }
        }
    }
}

/*迷宫有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算法

#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：标记当前节点是否在队列中，防止重复入队

#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算法

// 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算法

// 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;
}

二叉树

二叉树的序列化与反序列化及先中序构造

#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;
    }
};

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

//先序和中序构造二叉树
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算法

//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;
    }
};

树状数组

一维

单点修改区间查询

#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点的值

#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;
}

范围修改范围查询

#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;
}

二维

单点修改范围查询

#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;
}

范围查询范围修改

#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;
}

线段树

范围增加范围查询累加和

// 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;
}

有优先级调整的多范围修改任务

// 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的数据中间添加一个数

区间最值和历史最值

// 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 数

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;
    }
};

结合线段树求区间海王数

// 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;
    }
};

求一个数组中某一个区间出现了某个数的次数

参考上面摩尔投票结合线段树的例子，将一个数组按照数的大小和出现顺序升序排序，然后用不同逻辑的二分查找得到相对位置

稀疏表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 的区间最大值

2. 初始化

for (int i = 1; i <= n; i++) {
    st[i][0] = arr[i];
}

3. 状态转移

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)，预处理可避免浮点误差和时间浪费

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

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

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 步可覆盖到的位置

构建：

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

查询：

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

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

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

模板封装（最值查询）

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表用于快速查询父亲及以上节点

// 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信息

// 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;
}

练习题

树的重心

如果在树中选择某个节点并删除，这棵树将分为若干棵子树，使所有子树最大值最小的节点被称为整个树的重心。

性质：

• 树的重心如果不唯一，则至多有两个，且这两个重心相邻。
• 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
• 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
• 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
• 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

#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必为直径的一端。

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}$能取到的最大值

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]);
}

并查集

对数据进行分类

// 递归找祖先
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);
}

常见二分

加速查询

#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;
}

三分

// 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为从某一节点开始，到最大限度往前便利后的第一个没有出现的自然数。

#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;
}

乘积最大子数组

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

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";

栈

单调栈

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

#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;
}

最大频率栈

#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;
    }
};

堆

动态堆寻找中位数

#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;
}

大小根堆

#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;
}

扫描线

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

// 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;
}

排序

归并分治

分而治之

#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 小/大 的数

#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;
}

阶乘与逆元

乘以逆元等于除以某一个数再取模

#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;
};

线性递推逆元

// p 必须为质数
inv2[1] = 1;
for(int i = 2; i <= n; i ++){
	inv2[i] = (p - p / i) * inv2[p % i] % p;
}

矩阵快速幂

加速矩阵计算

#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为贝祖系数（裴蜀定理的算法实现）

#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;
}

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，从而找到它们的最大公约数。

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)算法

#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;
}

二进制位

位图

判断某一个数是否存在

#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;
}

位运算实现四则运算

加速运算

#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);
}

位运算骚操作

#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算法

异或技巧

#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);
        }
    }
}

链表基本操作

返回两个无环链表相交的第一个节点

#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个节点一组翻转链表

//每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;
    }
}

复制带随机指针的链表

//复制带随机指针的链表
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;
}

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

//判断链表是否是回文结构（快慢指针）
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;
}

返回第一个入环节点

//返回链表的第一个入环节点
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;
}

稳定排序

//在链表上排序，时间复杂度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个有序链表

#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;
}

莫队算法

离线加速处理查询

#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位置

#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算法

以某一节点为中心向两端扩展的最大回文串

#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函数

#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);
}

前缀树

#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自动机

#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;
}

字符串哈希

#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' + 27;
	}
	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，就说明该区间的质因数都是偶数，说明乘积是一个完全平方数，利用前缀和思想可以加速这一查找过程（当一个状态第一次出现时，记录位置，以后每次出现都说明中间与第一次出现的位置的间隔为一个完全平方数）。

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";
}   

质数/素数

质数判别

#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;
}

线性质数筛

// 质数筛
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;
		}
	}
}
// 求数值小于等于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

差分

对区间进行快速加法操作

一维

// 若有原数组则要分开处理，最后加上原数组或者进行以下处理
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];
}

二维

// 和原数组分开处理，最后加上原数组，或者进行以下处理
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;
}

序列/数组问题

最长公共子序列

递归/递推+路径

#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;
}

最长递增子序列

两个序列包含完全相同的数字使，可以将一个数组的顺序映射到另一个数组上，这时其最长公共子序列变成求最长递增子序列问题（或者反向求最长递减子序列）

普通版

#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;
}

字典序最小版

#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的最长子数组

#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

// 数位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

#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;
}

Fliegel–Van Flandern 算法

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

• JD ≥ 2299161：采用格里历（即1582年10月15日之后）
• JD < 2299161：采用儒略历

// 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），也称为后缀表达式，是一种将运算符放在操作数之后的数学表达方式。

#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

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

离散化

#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皇后问题

位运算版本

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

#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;
}

容器

set

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

#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)

#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)

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));
    }
}

改变大小写

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

#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

//rfind是找最后一个出现的匹配字符串
std::size_t found = str.rfind(str2);

find_...of

find_first_of(args) // **查找args中任何一个字符第一次出现的位置**
find_last_of(args) // **最后一个出现的位置**
find_fist_not_of(args) // **查找第一个不在args中的字符**
find_last_not_of // **查找最后一个不在args中出现的字符**

插入insert

#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;
}

tips

重载运算符号（比较）

// 结构体
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); 

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

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

圆周率π

const double pi  =  acos(-1);

求容器最大值

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

全排列

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

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

给定三个顶点

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坐标，每个参数都进行了一次碰面），进行点与点之间的逻辑处理，如判断处坐标异或值

给定三条边

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），需要进一步做特殊处理。

#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;
}

GCD数量级

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

点到直线的距离公式

设：
$$
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}}.
$$

随机数

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

完全平方数

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

随机哈希编码

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

批量操作

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);

参考资料

字符串 CSDN

左程云

三角形面积