# 通用

注意等号 “==”

连续子串想想能不能转换为滑动窗口问题？比如 #1658 将 x 减少到最小操作数
维护一堆候选状态 + 动态删除 + 区间批量处理”，就优先考虑 set 加速 BFS

// 按奇偶维护“未访问”的状态池
set<int> unvis[2];
for (int x = 0; x <= n; ++x) {
    if (x == c0) continue;
    unvis[x & 1].insert(x); // 奇数 & 1 = 1
}
auto &S = unvis[parity]; 
auto it = S.lower_bound(lo);
while (it != S.end() && *it <= hi) {
    int x = *it;
    it = S.erase(it);      // 从未访问集合中“批量摘除”
    dist[x] = dist[c] + 1; // 赋最短距离
    if (x == 0) return dist[x];
    q.push(x);
}

维护区间问题：

有关和，最大值之类的可以规约的，与区间重叠无关的，那么可以考虑 st 表，前缀和，线段树
有关频次，比如某段区间出现最多，那么考虑用前缀的思想，用一个 vector<map<,>>，其中 a [i], 表示从 1 到 i 的所有出现数字的频次，那么查询任意区间只需要做减法。

对于一坨数组上的计算操作，考虑先 sort 后会怎么样？nlogn

通用头

#include <bits/stdc++.h>
using namespace std;

using u64= unsigned long long;
using ll=long long;
using ld=long double;
using ull=unsigned long long;

const double PI = acos(-1.0);
const double eps = 1e-6;

ll INF=((ull)~0)>>2;



ll M=1e9+7;

template<typename T>T MO(T x){return (x%M+M)%M;} 

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

不能用通用库

/*
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<iomanip>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include<functional> 
*/

快速 IO

inline int rd() {
    int k = 0, w = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (ch == '-') w = -1; 
        c = getchar(); 
    }
    while (c >= '0' && c <= '9') {
        k = k * 10 + (c ^ '0'), c = getchar();
    }
    return k;
}

inline void wr(int x) {
    if (x == -1) {
        putchar('-');
        putchar('1');
        return;
    }
    if (x > 9) wr(x / 10);
    putchar((x % 10) ^ '0');
}

输入输出

// 输入是 1 2 3 4 5 \n
while(cin >> n){
        if(l1==nullptr){
            l1 = new ListNode(n);
            p1 = l1;
        }   
        else{
            p1->next = new ListNode(n);
            p1 = p1-> next;
        }
        if(cin.get()=='\n') break;
    }
// cin.get() 可以获得当前的下一个字符，为 char，可以是，\n
// 输入是一行想拆分成单个
string a;
cin >> a;
for(int i=a.size()-1;i>=0;i--) // a[i]-'0'

x1 = 42
cout << "......" << setw(10) << setfill('0') << x1 << '\n';
// 输出：......0000000042

# 算法复杂度

数据范围	时间复杂度	常用思路	示例算法
∞	O(logn)	二分、数论、打表	二分查找、快速幂、欧几里得算法、哈希表查找
10⁷ → 10⁸	O(n)	在线、贪心	线性扫描、双指针、滑动窗口、前缀和、KMP 字符串匹配
10⁵ → 10⁶	O(nlogn)	排序、分治	归并排序、快速排序、堆排序、线段树操作、Dijkstra 最短路
10³ → 10⁴	O(n²)	动态规划	最长公共子序列、背包问题、Floyd 算法、简单 DP、冒泡排序
200 → 500	O(n³)	模拟	三重循环暴力、矩阵乘法、Floyd-Warshall、复杂 DP 状态转移
20 → 50	O(2ⁿ)	BFS / DFS、状态压缩 DP	子集枚举、旅行商问题 (TSP)、图的所有路径
20	O(n!)	组合	全排列生成、八皇后问题、旅行商问题全搜索

# 内存预算大小

二维 / 三维示例（ int ，4B）

20000 × 6000 → 120,000,000 × 4 = 480,000,000 B ≈ 458.0 MiB ✅（接近上限，需谨慎）
10000 × 10000 → 100,000,000 × 4 = 400,000,000 B ≈ 381.5 MiB ✅
300 × 300 × 300 → 27,000,000 × 4 = 108,000,000 B ≈ 103.0 MiB ✅

堆 vs 栈：大数组放堆（ new / malloc / std::vector ）。栈通常 1–8 MB，避免在栈上开大数组（或加 static ）。

# 优乐美

# 边

// 题目与边本身有关，边上记录属性，比如求最小路，边排序
struct Edge{ int u,v; long long w; };

// 链式前向星，题目与边无关，只是方向 to, 同起点的下一条边 next
// 数组下标表示出点，也就是上面的 u
struct Edge { int to, next; long long w;} E[N<<1]; 
int head[N], ecnt=0;
fill(head, head + n + 1, 0);
inline void add_edge(int u, int v, long long w){
    E[++ecnt] = {v, head[u], w};
    head[u] = ecnt;
}
for (int i=head[u]; i; i=E[i].next)

# 优先队列 / 大顶堆

如果只需要频繁地获取最大 / 最小元素，并且只关心移除最值，那么 priority_queue 通常是更轻量级和更直接的选择。
如果需要一个始终保持排序的集合，并且可能需要进行查找、遍历或删除集合中任意位置的元素，那么 multiset 更适合。

priority_queue<int> max_pq; // 存储 int 类型，默认是最大堆

priority_queue<int, vector<int>, greater<int>> min_pq; // 存储 int 类型，最小堆

// lamada 小根堆
auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);

pq.push(10)
pq.pop()
pq.top() // 取堆顶

#include<set>
multiset<ll,greater<ll>> a;//大顶堆
multiset<ll,less<ll>> b;//小顶堆

auto cmps = [](const Node& a, const Node& b) 
{ return a.du < b.du; };
multiset<Node, decltype(cmps)> sho(cmps);

// 目标在 begin()
//允许重复的 set
a.size();//返回集合大小
a.empty();//判断集合是否为空
a.begin();//指向堆顶的迭代器
a.end();//指向正向迭代的最后一个元素下一个位置
a.rbegin();//指向堆底
a.rend();//指向逆向迭代的最后一个元素的下一个元素
a.insert(123);//插入元素，会自动排序
a.find(1234);//返回一个迭代器，指向第一个被查询的元素，如果没有，则指向 end()
//a.find()!=a.end()//判断集合内是否存在元素
a.count(143);//统计元素数量
a.erase(it);//按迭代器删除元素，常用搭配：a.erase(a.find(x));//注意得先判断集合内有该元素

auto it = find_if(sho.begin(), sho.end(), 
[&](const Node& n){ return n.id == u; });
if(it != sho.end()) {
    // 找到了
}

# 并查集

高效的查两个元素是否在同一个强连通分量上或者集合里
可以参与解决问题：环检测、

struct DSU{
    vector<int> p,r,sz;
    int sets_count;
    DSU(int n=0):p(n+1),r(n+1),sz(n+1,1), sets_count(n) { iota(p.begin(),p.end(),0); }
    int find(int x){ while(p[x]!=x){ p[x]=p[p[x]]; x=p[x]; } return x; }
    bool unite(int a,int b){
        a=find(a); b=find(b); if(a==b) return false;
        if(r[a]<r[b]) swap(a,b); p[b]=a; if(r[a]==r[b]) r[a]++;
        sz[a]+=sz[b]; sets_count--; return true;
    }
    int size(int x){ return sz[find(x)]; }
};

# 前缀和

// 计算前缀和 P[0..n]
static inline vector<ll> prefix(const vector<ll>& a){
    int n = (int)a.size();
    vector<ll> P(n+1, 0);
    for(int i = 1; i <= n; ++i) P[i] = P[i-1] + a[i-1];
    return P;
}

// 二维前缀和类
// 支持 O(1) 查询子矩阵和 (x1,y1) 到 (x2,y2)
 // *   vector<vector<int>> matrix = {{1,2,3}, {4,5,6}, {7,8,9}};
 // *   PrefixSum2D ps(matrix);
 // *   int sum = ps.rangeSum(0,0, 1,1); 
class PrefixSum2D {
private:
    vector<vector<long long>> prefixSum;
    int rows, cols;
  
public:
    /**
     * 构造函数：根据二维数组构建二维前缀和
     */
    PrefixSum2D(const vector<vector<int>>& matrix) {
        rows = matrix.size();
        if (rows == 0) return;
        cols = matrix[0].size();
      
        prefixSum.assign(rows + 1, vector<long long>(cols + 1, 0));
      
        for (int i = 1; i <= rows; ++i) {
            for (int j = 1; j <= cols; ++j) {
                prefixSum[i][j] = matrix[i-1][j-1] 
                                + prefixSum[i-1][j] 
                                + prefixSum[i][j-1] 
                                - prefixSum[i-1][j-1];
            }
        }
    }
    /**
     * 查询子矩阵 (x1,y1) 到 (x2,y2) 的和（闭区间，0-indexed）
     */
    long long rangeSum(int x1, int y1, int x2, int y2) {
        if (x1 < 0 || y1 < 0 || x2 >= rows || y2 >= cols || x1 > x2 || y1 > y2) {
            return 0; // 非法区间返回 0
        }
        return prefixSum[x2+1][y2+1] - prefixSum[x1][y2+1] - prefixSum[x2+1][y1] + prefixSum[x1][y1];
    }
};

# ST 表

建立 nlogn，查询 O1，解决大量请求，不涉及区间更改的 GCD, min, max 问题

struct SparseTable {
    int n, K;
    vector<int> lg;
    vector<vector<int>> st;
    SparseTable(const vector<int>& a) {
        n = a.size();
        lg.resize(n+1);
        lg[1] = 0;
        for (int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;
        K = lg[n] + 1;

        st.assign(K, vector<int>(n));
        st[0] = a; // 长度为 1 的区间就是自身

        for (int k = 1; k < K; k++) {
            for (int i = 0; i + (1<<k) <= n; i++) {
                st[k][i] = min(st[k-1][i], st[k-1][i + (1<<(k-1))]); // max 或 gcd
            }
        }
    }
    int query(int l, int r) {
        int k = lg[r - l + 1];
        return min(st[k][l], st[k][r - (1<<k) + 1]);
    }
};
SparseTable st(a);

# 全排列

需要排列的问题，对于物品可以用 order 列表塞一个 1-n 的序列先，然后来搞

#include <bits/stdc++.h>
#include <numeric> // iota

vector<int> make_order(int n) { //生成一个 填满 0 - n-1 的数组
    vector<int> order(n);
    iota(order.begin(), order.end(), 0); // 0,1,2,...,n-1
    return order;
}

vector<vector<int>> permute_lex(vector<int> nums) { //允许重复元素的全排序列生成
    sort(nums.begin(), nums.end());          // 先排好序
    vector<vector<int>> res;
    do { res.push_back(nums); }
    while (next_permutation(nums.begin(), nums.end()));
    return res;
}

# 单调栈

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，用单调栈
 比如：接雨水

现在的目标：找到右边第一个比自己大的数；以下标，存为 result [n]

想象一个栈  栈口到栈底（递增的栈）：对于 data [n]：

塞入 73（data0），塞入 74（data1）发现 74>73 弹出 73（下标为 0）直接 result [0]=1-0；75 同理；

塞入 71（data3），71<75 不动，塞 69，再塞 72 发现 72>69，弹出 69 更新 69 的 result，再发现 72>71 更新 71 的。

// 右边第一个更大元素（strict：true 用 >，false 用 >=）
vector<int> next_greater_right(const vector<int>& a, bool strict = true) {
    int n = (int)a.size(); vector<int> nxt(n, -1); stack<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && (strict ? a[i] > a[st.top()] : a[i] >= a[st.top()])) {
            nxt[st.top()] = i; st.pop();
        }
        st.push(i);
    }
    return nxt;
}

// 右边第一个更小元素（strict：true 用 <，false 用 <=）
vector<int> next_smaller_right(const vector<int>& a, bool strict = true) {
    int n = (int)a.size(); vector<int> nxt(n, -1); stack<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && (strict ? a[i] < a[st.top()] : a[i] <= a[st.top()])) {
            nxt[st.top()] = i; st.pop();
        }
        st.push(i);
    }
    return nxt;
}

// 左边第一个更大元素
vector<int> prev_greater_left(const vector<int>& a, bool strict = true) {
    int n = (int)a.size(); vector<int> prv(n, -1); stack<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && (strict ? a[st.top()] <= a[i] : a[st.top()] < a[i])) st.pop();
        if (!st.empty()) prv[i] = st.top();
        st.push(i);
    }
    return prv;
}

// 左边第一个更小元素
vector<int> prev_smaller_left(const vector<int>& a, bool strict = true) {
    int n = (int)a.size(); vector<int> prv(n, -1); stack<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && (strict ? a[st.top()] >= a[i] : a[st.top()] > a[i])) st.pop();
        if (!st.empty()) prv[i] = st.top();
        st.push(i);
    }
    return prv;
}

# 滑动窗口

// 滑动窗口算法伪码框架
void slidingWindow(string s) {
    // 用合适的数据结构记录窗口中的数据，根据具体场景变通
    // 比如说，我想记录窗口中元素出现的次数，就用 map
    unordered_map<char, int> window;
    // 如果我想记录窗口中的元素和，就可以只用一个 int
    auto window = ...
  
    int left = 0, right = 0;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        window.add(c);
        // 增大窗口
        right++;

        // 进行窗口内数据的一系列更新
        ...

        // *** debug 输出的位置 ***
        printf("window: [%d, %d)\n", left, right);
        // 注意在最终的解法代码中不要 print
        // 因为 IO 操作很耗时，可能导致超时

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            window.remove(d);
            // 缩小窗口
            left++;

            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

# 二分查找

int binarySearch(vector<int> &a, int e){ // 保证输入有序; lower_bound 形式
    int le = 0, ri = a.size();
    while(ri - le > 1){ // [le, ri) 夹逼
        int mid = (le + ri) >> 1;
        if(a[mid] <= e)
            le = mid; // le 处元素总是<=
        else
            ri = mid; // ri 处元素总是>
    }
    return le; // 返回下标
}

# 线段树

只查和 / 最值？
点改 → 普通线段树 / BIT
区间加 / 赋值 → 懒标记线段树（上面的 A/B）
有 chmin/chmax？
性能高要求 → Segment Tree Beats
数据小 / 询问少 → 拆分或暴力
第 k 小？
静态 + 区间 → 主席树 / Merge Sort Tree
全局 + 动态 → BIT/SegTree 维护频次 + kth
区间 + 动态 → 难（块状 / 平衡树 / 离线），优先主席树或改题

# add - max/min/sum

// Range Add + Query {min, max, sum}
struct SegAddMMS {
    struct Node { int l, r; long long mn, mx, sum, add; };
    int n;
    vector<Node> t;

    SegAddMMS(int n=0){ init(n); }
    void init(int n_){
        n = n_;
        t.assign(4*n+4, {0,0,0,0,0,0});
    }
    inline int len(int u) const { return t[u].r - t[u].l + 1; }

    inline void pull(int u){
        t[u].mn  = min(t[u<<1].mn,  t[u<<1|1].mn);
        t[u].mx  = max(t[u<<1].mx,  t[u<<1|1].mx);
        t[u].sum =      t[u<<1].sum + t[u<<1|1].sum;
    }
    inline void apply_add(int u, long long v){
        t[u].mn  += v;
        t[u].mx  += v;
        t[u].sum += v * len(u);
        t[u].add += v;
    }
    inline void push(int u){
        if(t[u].add){
            apply_add(u<<1,   t[u].add);
            apply_add(u<<1|1, t[u].add);
            t[u].add = 0;
        }
    }

    // 建树：a 为 1..n
    void build(int u, int l, int r, const vector<long long>& a){
        t[u] = {l, r, 0, 0, 0, 0};
        if(l==r){
            long long v = a[l];
            t[u].mn = t[u].mx = t[u].sum = v;
            return;
        }
        int mid = (l + r) >> 1;
        build(u<<1, l, mid, a);
        build(u<<1|1, mid+1, r, a);
        pull(u);
    }

    // [L,R] 加 v
    void range_add(int u, int L, int R, long long v){
        int l=t[u].l, r=t[u].r;
        if(R<l || r<L) return;
        if(L<=l && r<=R){ apply_add(u, v); return; }
        push(u);
        range_add(u<<1, L, R, v);
        range_add(u<<1|1, L, R, v);
        pull(u);
    }

    // 查询 [L,R] 的 min/max/sum —— 三合一
    struct Res { long long mn, mx, sum; };
    Res query(int u, int L, int R){
        int l=t[u].l, r=t[u].r;
        if(L<=l && r<=R) return {t[u].mn, t[u].mx, t[u].sum};
        push(u);
        int mid = (l + r) >> 1;
        const long long INF = (1LL<<62);
        Res left{+INF, -INF, 0}, right{+INF, -INF, 0};
        if(L<=mid) left  = query(u<<1,   L, R);
        if(R> mid) right = query(u<<1|1, L, R);
        return { min(left.mn,right.mn), max(left.mx,right.mx), left.sum+right.sum };
    }
};

// n = 4 构建的树：

//              [1,4] (t[1]) //t[1] 管 [1,4]
//             /           \
//      [1,2] (t[2])      [3,4] (t[3])
//      /      \           /      \
//  [1,1]   [2,2]     [3,3]    [4,4]
//  t[4]    t[5]     t[6]     t[7]

// 注意：线段树 build 期望 a[1..n]
vector<long long> r(n+1);
for(int i=1;i<=n;i++) cin >> r[i];

SegAddMMS seg(n);
seg.build(1, 1, n, r);  // 初始：每天剩余 = 可用教室数

t[1].mn //表示整个区间的最小值


seg.range_add(1, L, R, v);
auto res = seg.query(1, L, R);

# chmax/chmin - max/min/sum

比如需要 a_i = min(a_i, x) 的区间操作

struct SegBeats {
    struct Node {
        int l, r;
        long long sum, add; // 区间和 + 区间加懒标记
        int mx, smax, cmx;  // 最大值、次大值、最大值个数
        int mn, smin, cmn;  // 最小值、次小值、最小值个数
    };
    int n;
    vector<int> a;        // a[1..n]
    vector<Node> t;       // 4n

    SegBeats(int n=0){ init(n); }
    void init(int n_){
        n=n_;
        a.assign(n+1,0);
        t.assign(4*n+4, {});
    }

    inline int len(int u) const { return t[u].r - t[u].l + 1; }

    // 叶子赋值
    inline void build_leaf(int u, int v){
        t[u].sum = v;
        t[u].add = 0;
        t[u].mx = t[u].mn = v;
        t[u].cmx = t[u].cmn = 1;
        t[u].smax = INT_MIN;
        t[u].smin = INT_MAX;
    }

    void build(int u, int l, int r){
        t[u].l = l; t[u].r = r; t[u].add = 0;
        if(l==r){ build_leaf(u, a[l]); return; }
        int m=(l+r)>>1;
        build(u<<1, l, m);
        build(u<<1|1, m+1, r);
        pull(u);
    }

    // —— 合并两个子结点到父结点
    inline void pull(int u){
        const Node &L=t[u<<1], &R=t[u<<1|1];
        t[u].sum = L.sum + R.sum;

        // max 侧
        if(L.mx == R.mx){
            t[u].mx = L.mx;
            t[u].cmx = L.cmx + R.cmx;
            t[u].smax = max(L.smax, R.smax);
        }else if(L.mx > R.mx){
            t[u].mx = L.mx; t[u].cmx = L.cmx;
            t[u].smax = max(L.smax, R.mx);
        }else{
            t[u].mx = R.mx; t[u].cmx = R.cmx;
            t[u].smax = max(R.smax, L.mx);
        }

        // min 侧
        if(L.mn == R.mn){
            t[u].mn = L.mn;
            t[u].cmn = L.cmn + R.cmn;
            t[u].smin = min(L.smin, R.smin);
        }else if(L.mn < R.mn){
            t[u].mn = L.mn; t[u].cmn = L.cmn;
            t[u].smin = min(L.smin, R.mn);
        }else{
            t[u].mn = R.mn; t[u].cmn = R.cmn;
            t[u].smin = min(R.smin, L.mn);
        }
    }

    // —— 区间加 懒标记
    inline void apply_add(int u, long long v){
        t[u].sum += v * len(u);
        t[u].mx  += (int)v;
        t[u].mn  += (int)v;
        if(t[u].smax != INT_MIN) t[u].smax += (int)v;
        if(t[u].smin != INT_MAX) t[u].smin += (int)v;
        t[u].add += v;
    }

    // —— 整段 chmin：要求 smax < x < mx
    inline void apply_chmin(int u, int x){
        long long dec = 1LL*(t[u].mx - x) * t[u].cmx;
        t[u].sum -= dec;
        t[u].mx = x;
        // 极端同值段时 mn 也会变到 x；一般情况下 mn <= x 恒成立
        if(t[u].mn > x) t[u].mn = x;
        // smax/cmx 语义保持，不需改；smin 安全起见界一界
        if(t[u].smin > t[u].mx) t[u].smin = t[u].mx;
    }

    // —— 整段 chmax：要求 mn < x < smin
    inline void apply_chmax(int u, int x){
        long long inc = 1LL*(x - t[u].mn) * t[u].cmn;
        t[u].sum += inc;
        t[u].mn = x;
        if(t[u].mx < x) t[u].mx = x;
        if(t[u].smax < t[u].mn) t[u].smax = t[u].mn;
    }

    // —— 下传：先传 add，再尝试把儿子 clamp 到父的 mx/mn
    void push(int u){
        if(t[u].l == t[u].r) return;
        if(t[u].add){
            apply_add(u<<1,   t[u].add);
            apply_add(u<<1|1, t[u].add);
            t[u].add = 0;
        }
        // 让儿子的 mx 不超过父 mx
        for(int v : {u<<1, u<<1|1}){
            if(t[v].mx > t[u].mx && t[v].smax < t[u].mx){
                apply_chmin(v, t[u].mx);
            }
        }
        // 让儿子的 mn 不低于父 mn
        for(int v : {u<<1, u<<1|1}){
            if(t[v].mn < t[u].mn && t[v].smin > t[u].mn){
                apply_chmax(v, t[u].mn);
            }
        }
    }

    // —— 对外：区间加
    void range_add(int u, int L, int R, long long v){
        int l=t[u].l, r=t[u].r;
        if(R<l || r<L) return;
        if(L<=l && r<=R){ apply_add(u, v); return; }
        push(u);
        range_add(u<<1, L, R, v);
        range_add(u<<1|1, L, R, v);
        pull(u);
    }

    // —— 对外：区间 chmin
    void range_chmin(int u, int L, int R, int x){
        int l=t[u].l, r=t[u].r;
        if(R<l || r<L || x>=t[u].mx) return;
        if(L<=l && r<=R && t[u].smax < x){
            apply_chmin(u, x); return;
        }
        push(u);
        range_chmin(u<<1, L, R, x);
        range_chmin(u<<1|1, L, R, x);
        pull(u);
    }

    // —— 对外：区间 chmax
    void range_chmax(int u, int L, int R, int x){
        int l=t[u].l, r=t[u].r;
        if(R<l || r<L || x<=t[u].mn) return;
        if(L<=l && r<=R && t[u].smin > x){
            apply_chmax(u, x); return;
        }
        push(u);
        range_chmax(u<<1, L, R, x);
        range_chmax(u<<1|1, L, R, x);
        pull(u);
    }

    // —— 查询
    long long query_sum(int u, int L, int R){
        int l=t[u].l, r=t[u].r;
        if(R<l || r<L) return 0;
        if(L<=l && r<=R) return t[u].sum;
        push(u);
        return query_sum(u<<1,L,R) + query_sum(u<<1|1,L,R);
    }
    int query_min(int u, int L, int R){
        int l=t[u].l, r=t[u].r;
        if(R<l || r<L) return INT_MAX;
        if(L<=l && r<=R) return t[u].mn;
        push(u);
        return min(query_min(u<<1,L,R), query_min(u<<1|1,L,R));
    }
    int query_max(int u, int L, int R){
        int l=t[u].l, r=t[u].r;
        if(R<l || r<L) return INT_MIN;
        if(L<=l && r<=R) return t[u].mx;
        push(u);
        return max(query_max(u<<1,L,R), query_max(u<<1|1,L,R));
    }

    void build(const vector<int>& A){ // A: 1..n
        a.assign(1,0); a.insert(a.end(), A.begin()+1, A.end());
        build(1,1,n);
    }
    void range_add(int L,int R,long long v){ range_add(1,L,R,v); }
    void range_chmin(int L,int R,int x){ range_chmin(1,L,R,x); }
    void range_chmax(int L,int R,int x){ range_chmax(1,L,R,x); }
    long long query_sum(int L,int R){ return query_sum(1,L,R); }
    int query_min(int L,int R){ return query_min(1,L,R); }
    int query_max(int L,int R){ return query_max(1,L,R); }
};

ector<int> A(n+1); // 1-based
A[1]=5; A[2]=2; A[3]=9; A[4]=7; A[5]=1;

SegBeats st(n);
st.build(A);
st.range_add(2,4,3);   // [2..4] +3 => [5,5,12,10,1]
st.range_chmin(1,5,6); // cap to 6 => [5,5,6,6,1]
st.range_chmax(1,3,4); // floor to 4 on [1..3] => [5,5,6,6,1]

# k-th 问题

主席树，分治树这种，见树章节

# STL

# vector

vector<type> v;
vector<vector<Node>> mono;
mono.assign(a.size() + 1, vector<Node>(b.size() + 1, {-1,-1}));
v.clear() // 清空 vector
//去重
sort(v.begin(), v.end()); 
auto uni=unique(v.begin(), v.end()); // 用库函数把重复元素移到后面
v.erase(uni, v.end()); // 删除 unique 移位到最后的重复元素

# Stack, Queue

stack<type> s;
s.push(x); // 栈顶压入（添加）元素 x
s.pop(); // 栈顶弹出（删除）元素
s.top(); // 返回栈顶元素
s.empty(); // 检查栈是否为空
s.size(); // 返回栈长度
queue<type> q;
q.push(x); // 入队（在队尾添加元素）
q.pop(); // 出队（在队首删除元素）
q.front(); // 队首元素值
q.back(); // 队尾元素值
q.empty(); // 检查队列是否为空
q.size(); // 返回队列长度

# 排序

// cmp(a,b)==true，a 排在 b 前面
auto cmp = [](const Edge& a, const Edge& b){return a.w>b.w;};
sort(e.begin(), e.end(), cmp); // 从大到小

// cmp(a,b)==true，a 的优先级低
priority_queue<int> pq; // std::less<int> a < b 大根堆
// 下面是小根堆
auto cmp = [](const Node& a, const Node& b){return a.w>b.w;}; 
priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);

stable_sort(beg, end, cmp) 稳定排序，保持相等元素的相对顺序
partial_sort(beg, mid, end, cmp) 部分排序，只保证前k个元素有序，k=mid-beg


// 手搓快排
void quicksort(vector<int> &a, int le, int ri){
    if(le >= ri - 1) return;
    int i = le - 1, j = le - 1, pivot = ri - 1, r = (rand()%(ri-le))+le;
    swap(a[pivot], a[r]); // 随机化处理
    while(++j < pivot){
        if(a[j] < a[pivot])
            swap(a[++i], a[j]);
    }
    swap(a[i + 1], a[pivot]);
    quicksort(a, le, i+1);
    quicksort(a, i+2, ri);
 }

// 去重排序，比 set 快一点？
sort(ks.begin(), ks.end());
ks.erase(unique(ks.begin(), ks.end()), ks.end());

# map 使用方法

元素按 key 的比较器（默认升序）排序，而不是按 value。

set<int, greater<int>> s = {3, 1, 4};  // 按降序排序

if (s.find(3) != s.end()) {
    cout << "找到元素 3" << endl;
}
for (auto it = s.rbegin(); it != s.rend(); ++it) // 反向遍历

s.insert({key,value})
s.erase(key)

map<int, string> m;
m.insert({1, "apple"});
m[2] = "banana"; 
m.erase(1); 
//修改
m[2] = "grape";  // 修改键为 2 的值为 "grape"

map<int,int> mp;
auto it = mp.begin();          // it 是迭代器
cout << it->first << endl;     // key
cout << it->second << endl;    // value
for (auto& kv : freq) {
    int val = kv.first, cnt = kv.second;
    if (cnt > bestCnt || (cnt == bestCnt && val < bestVal)) {
        bestCnt = cnt;
        bestVal = val;
    }
}


lower_bound(key)：返回第一个大于等于 key 的元素。
upper_bound(key)：返回第一个大于 key 的元素。
set<int, greater<int>> s = {3, 1, 4};
s.erase(s.lower_bound(10), s.upper_bound(50)); 删除 [10,50]

//定义一个 vector 的数组
vector<unordered_map<int,int>> qmap(n);  // ✅ 正确
qmap[0][nums[0]]++;  // ✅ 使用正常

不能用 **std::map** 直接 “按 value 排”。

// 返回 map 中 (value 最大，tie 时 key 最大) 的 pair
pair<int,int> getBest(const map<int,int>& freq) {
    // 拷贝到 vector
    vector<pair<int,int>> items(freq.begin(), freq.end());
    // 自定义排序
    sort(items.begin(), items.end(), [](const auto& a, const auto& b) {
        if (a.second != b.second) return a.second > b.second; // value 大的优先
        return a.first > b.first;                             // value 相同，key 大的优先
    });
    return items.empty() ? make_pair(-1,-1) : items[0];
}

map<int,int> freq;
freq[1] = 4;
freq[2] = 4;
freq[5] = 2;

auto [val, cnt] = getBest(freq);
cout << "best key=" << val << " freq=" << cnt << "\n";

vector<pair<int,int>> getTopK(const map<int,int>& freq, int K) {
    vector<pair<int,int>> items(freq.begin(), freq.end());
    sort(items.begin(), items.end(), [](const auto& a, const auto& b) {
        if (a.second != b.second) return a.second > b.second;
        return a.first > b.first;
    });
    if ((int)items.size() > K) items.resize(K);
    return items;
}

# 字符串与转换

s.substr(pos, len) // pos: 起始位置，len: 长度，提取子串
s.find(target) //target: 要查找的字符串/字符，查找首次出现位置，返回索引
s.erase(pos, len) // pos: 起始位置，len: 删除长度，删除指定部分

#include <format>
int x = 255;
std::string s = std::format("{}", x);   // "255"
std::string h = std::format("{:x}", 255); // "ff"
std::string b = std::format("{:b}", 13);  // "1101"
  
// 进制 / 前缀 / 大小写 
printf("%x %X\n", 255, 255);     // ff FF
printf("%#x %#o\n", 255, 64);    // 0xff 010   (# 显示前缀)
printf("%.2f")
printf("%08d", value) //整数前补 0，总宽度 8 位

cout << dec << 255
cout << oct // 8 进制
cout << hex // 16
cout << hex << uppercase << 255; // 输出 FF，大写
//显示进制前缀 (0x, 0) cout << hex << showbase << 255; // 输出 0xff
cout << showpos //正数有+
cout << scientific // 科学计数 1234.5; // 输出 1.234500e+03

# KMP

KMP 是一个 解决模式串在文本串是否出现过 ，如果出现过，最早出现的位置的经典算法。

int next[MAXN];
 int KMP(string text, string pattern){   // 输入参数保证为序列即可
    int i = next[0] = -1, j = 0;
    int n = text.size(), m = pattern.size();
    while(j < m){   // 自匹配，获得 next[] 表
        if(i == -1 || pattern[j] == pattern[i]){
            i++; j++; next[j] = i;
        } else{
            i = next[i];
        }
    }
    i = j = 0;   // KMP
    while(i < n && j < m) {
        if(j == -1 || text[i] == pattern[j]){
            i++; j++;
        } else{
            j = next[j];   // 失配
        }
        // if(j == m){  // 依次输出所有匹配位置
        //     cout << i - j + 1 << endl;
        //     j = next[j];   // 完美匹配，当作失配处理
        // }
    }
    if(j == m) return i - j + 1;
    else return -1;
 }

// 匹配全部可能的起点 0-based
template <class T>
vector<int> kmp_all(const vector<T>& text, const vector<T>& pattern) {
    vector<int> res;
    int n = (int)text.size(), m = (int)pattern.size();
    if (m == 0) { for (int i = 0; i <= n; ++i) res.push_back(i); return res; }

    vector<int> nxt(m + 1);
    int i = -1, j = 0; nxt[0] = -1;
    while (j < m) {
        if (i == -1 || pattern[j] == pattern[i]) { ++i; ++j; nxt[j] = i; }
        else i = nxt[i];
    }

    i = 0; j = 0;
    while (i < n) {
        if (j == -1 || text[i] == pattern[j]) { ++i; ++j; }
        else j = nxt[j];
        if (j == m) { res.push_back(i - j); j = nxt[j]; }
    }
    return res;
}

int main() {
    string s = "ababaabababa";
    string p = "ababa";
    vector<char> text(s.begin(), s.end());
    vector<char> pattern(p.begin(), p.end());

    vector<int> pos = kmp_all(text, pattern); // 0-based 起点
    for (int x : pos) cout << x << " ";
    cout << "\n"; // 输出：0 5 7
}

# 大暴力

# 回溯算法

递归函数参数
 递归终止条件

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

# 树枝剪枝

剩下的元素长度明显无法有正确路径

输出 1-n 里面，组合为 k 的子集，
考虑定义两个东西一个存当前路径，一个存全局的答案
//i <= n-(k-path.size ())+1 剩下的元素取不到 k 个了

vector<vector<int>> res;
vector<int> path;

// 1-based
void backtrace(int n, int k, int st){
    if(path.size()==k) {
        res.push_back(path);
        return;
    }
    for(int i=st;i<=n;i++){ // 这里做剪枝
        // i <= n-(k-path.size())+1
        path.push_back(i);
        backtrace(n, k, i+1);
        path.pop_back();
    }
}

int main(){
    int n,k;cin>>n>>k;
    backtrace(n,k,1);
    cout << res.size() << endl;
    return 0;
}

# 同层剪枝

求解和为 target 的组合，每个数字（候选字）只能选一次，考虑回溯法
先 sort 一遍，让他们紧挨着
剪枝：只能选一次，同层去重

for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
    // used[i - 1] == true，说明同一树枝 candidates[i - 1] 使用过
    // used[i - 1] == false，说明同一树层 candidates[i - 1] 使用过
    // 要对同一树层使用过的元素进行跳过
    if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
        continue;
    }
    sum += candidates[i];
    path.push_back(candidates[i]);
    used[i] = true;
    backtracking(candidates, target, sum, i + 1, used); 
    // 和 39.组合总和的区别 1：这里是 i+1，每个数字在每个组合中只能使用一次
    used[i] = false;
    sum -= candidates[i];
    path.pop_back();
}

# 组合问题

/**
 * @brief 2. 组合问题
 * 
 * 从 1...n 这 n 个数字中，找出 k 个数的组合。
 */
class CombinationSolver {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        if (n <= 0 || k <= 0 || k > n) return result;
      
        vector<int> path;
        backtrack(1, n, k, path, result);
        return result;
    }

private:
    void backtrack(int start, int n, int k, vector<int>& path, vector<vector<int>>& result) {
        // 终止条件：路径中的数字个数等于 k
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
      
        // 遍历选择列表
        // 剪枝优化：如果剩余的数字数量已经不足以凑够 k 个，就没必要继续了
        // 还需要 k - path.size() 个数
        // 剩下的可选数字范围是 [i, n]，共 n - i + 1 个
        // n - i + 1 >= k - path.size()  =>  i <= n - (k - path.size()) + 1
        for (int i = start; i <= n - (k - path.size()) + 1; ++i) {
            // 做选择
            path.push_back(i);
          
            // 进入下一层决策，起始点为 i+1，保证不重复选择
            backtrack(i + 1, n, k, path, result);
          
            // 撤销选择
            path.pop_back();
        }
    }
};

# n 皇后（n!）

vector<vector<string>> result;
// n 为输入的棋盘大小
// row 是当前递归到棋盘的第几行了
void backtracking(int n, int row, vector<string>& chessboard) {
    if (row == n) {
        result.push_back(chessboard);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
            chessboard[row][col] = 'Q'; // 放置皇后
            backtracking(n, row + 1, chessboard);
            chessboard[row][col] = '.'; // 回溯，撤销皇后
        }
    }
}
bool isValid(int row, int col, vector<string>& chessboard, int n) {
    // 检查列
    for (int i = 0; i < row; i++) { // 这是一个剪枝
        if (chessboard[i][col] == 'Q') {
            return false;
        }
    }
    // 检查 45 度角是否有皇后
    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    // 检查 135 度角是否有皇后
    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}
public:
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        std::vector<std::string> chessboard(n, std::string(n, '.'));
        backtracking(n, 0, chessboard);
        return result;
    }
};

# DFS

染色问题

#include <bits/stdc++.h>
using namespace std;
int a[32][32],b[32][32];
int dx[5]={0,-1,1,0,0};
int dy[5]={0,0,0,-1,1};//第一个表示不动，是充数的，后面的四个分别是上下左右四个方向
int n,i,j;
void dfs(int p,int q){
    int i;
    if (p<0||p>n+1||q<0||q>n+1||a[p][q]!=0) return;
    //如果搜过头或者已经被搜过了或者本来就是墙的就往回
    a[p][q]=1;//染色
    for (i=1;i<=4;i++) dfs(p+dx[i],q+dy[i]);//向四个方向搜索
}
int main(){
    cin>>n;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++){
            cin>>b[i][j];//其实不拿两个数组也可以，不过我喜欢啦
            if (b[i][j]==0) a[i][j]=0;
            else a[i][j]=2;
        }
    dfs(0,0);//搜索 从 0，0 开始搜
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++)
        if (a[i][j]==0) cout<<2<<' ';
//如果染过色以后 i，j 那个地方还是 0，说明没有搜到，就是周围有墙，当然就是被围住了，然后输出 2
        else cout<<b[i][j]<<' ';
        //因为被染色了，本来没有被围住的水和墙都染成了 1，所以就输出 b[i][j]
        cout<<'\n';//换行
    }
}

# 岛屿与染色问题

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void dfs(int i, int j, int n, int m, vector<string>& ta){
    if (i < 0 || i >= n || j < 0 || j >= m || ta[i][j] == '.') return;
    ta[i][j] = '.';
    for (int k = 0; k < 4; k++) {
        dfs(i + dx[k], j + dy[k], n, m, ta);
    }
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<string> ta(n);
    for(int i = 0; i < n; i++) {
        cin >> ta[i];
    }
    int ans = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(ta[i][j] == 'W') {
                dfs(i, j, n, m, ta);
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

# 迷宫路径

#include <bits/stdc++.h>
using namespace std;

int n, m, t;
vector<vector<int>> ta;     // 0: 空地，1: 障碍
vector<vector<bool>> vis;   // 访问标记
long long ans = 0;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

inline bool in_bounds(int i, int j) {
    return (i >= 1 && i <= n && j >= 1 && j <= m);
}

void backtrace(int i, int j, int x, int y) {
    // 越界或障碍或已访问，直接返回
    if (!in_bounds(i, j) || ta[i][j] == 1 || vis[i][j]) return;

    // 到达终点
    if (i == x && j == y) {
        ans++;
        return;
    }

    vis[i][j] = true;
    for (int q = 0; q < 4; q++) {
        int ni = i + dx[q];
        int nj = j + dy[q];
        if (in_bounds(ni, nj) && !vis[ni][nj] && ta[ni][nj] == 0) {
            backtrace(ni, nj, x, y);
        }
    }
    vis[i][j] = false; // 回溯
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> t;

    ta.assign(n + 1, vector<int>(m + 1, 0));
    vis.assign(n + 1, vector<bool>(m + 1, false));

    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    for (int i = 0; i < t; i++) {
        int x3, y3; 
        cin >> x3 >> y3;
        // 确保障碍坐标合法
        if (x3 >= 1 && x3 <= n && y3 >= 1 && y3 <= m) {
            ta[x3][y3] = 1;
        }
    }

    backtrace(x1, y1, x2, y2);
    cout << ans << "\n";
    return 0;
}

# 贪心

首先明确能暴力枚举先拿分就暴力，参考 @理发师，不要贪心。

如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？
靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。
最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧
首先想所有的状态，最简单的那种，可能怎么拼凑。

小孩子吃饼干，局部最优是让大胃口吃大的，然后全局最优是尽可能多的孩子吃到饼干
摆动序列，局部最优是删除单调坡度上的节点，直到刚好单峰。
股票买卖最大利润 2，要学会转变为利润，不要去模拟买卖过程，只在利润为正的时候交易。
环绕一圈加油站起点问题，局部最优是 [充油 - 花费] + [充油 - 花费] 一旦扫到负数了，那么直接把把下一个油站选为起点，因为前面怎么选那里都不行。
分发糖果，一列孩子，rate 高的比两边糖果多，要糖果最少，两次贪心，局部最优是右边只要比左边高就 +1 否则变成 1；从右边，同理，然后二者取最大值。
 遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度
找零问题，优先保留万能换钱的，比如 5，10，20，优先用 10，5 组合找 20 的零。

# 区间问题

# 不相交区间

# 区间选点

比如射气球问题，重叠区间问题

# 区间覆盖

比如跳跃游戏

# 线性基 (异或和最大）

给定 n 个整数（数字可能重复），求在这些数中选取任意个【不一定连续】，使得他们的异或和最大。

#include <cstdio>
 #define maxn 105
 typedef long long Lovelive;
 Lovelive base[maxn];
 int main() {
    Lovelive n, tmp;
    scanf("%lld", &n);   // 【n 个整数】
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &tmp);  // 【输入每个整数】
        for (int j = 50; j >= 0; --j) {
            if(tmp & (1LL << j)) {   // 贪心
                if(!base[j]) base[j] = tmp;
                tmp ^= base[j];
            }
        }
    }
    Lovelive ans = 0;
    for(int i = 50; i >= 0; --i) {
        if(ans < (ans ^ base[i])) ans ^= base[i];
    }
    printf("%lld\n", ans);   // 【最大异或和】
}

# 动态规划

动规五部曲：
确定 dp 数组（dp table）以及下标的含义
确定递推公式
dp 数组如何初始化
确定遍历顺序
举例推导 dp 数组
DP 有两种状态转移策略：
**【刷表法】：更新贪心 dp [i] 影响的所有后继（必须保证每个状态依赖的所有影响相互独立） **
**【填表法】：利用 dp [i] 的所有前驱，一次性状态转移计算出 dp [i] **

# 朴素的子问题思考法 DFS+ 记忆化

「SDOI2011」消耗战
给定一棵树（n 个点，n-1 条边），每条边有炸毁代价。
总部在 1 号点。
多次询问：给出若干 关键点（能源岛屿），要切掉一些边，使 1 号点无法到达任何关键点，代价最小。
每次询问独立。

子问题：两个点 → 必切边。
往上一层：父亲多一条路，决策 = min(切当前边, 用子树代价) 。
多个子树：每个子树独立取最优，结果相加。
关键点节点：必切与父亲的边。
👉 核心：每往上加一层，就判断 “切这一条边” 还是 “依靠下面的割边”，逐层累积最小代价。

# 背包 DP

# 01 背包

问题抽象为，一个背包容量 j，n 个物品，要么选要么不选
状态：有两个状态决定结果，背包大小，哪些物品
转移：考虑当前新加的物品 i 要选他还是不选他
转移 1：选他，价值为为 v [i] + dp (i-1, j-w [i]);
转移 2：不选他，价值为 dp [i-1, j]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, V;
vector<int> w, v;
vector<vector<ll>> memo;  // 备忘录，-1 表示还没算过

ll dfs(int i, int cap) {            // 从第 i 件开始，剩余容量 cap 的最大价值
    if (i == n || cap == 0) return 0;
    ll &res = memo[i][cap];
    if (res != -1) return res;

    // 不选第 i 件
    res = dfs(i + 1, cap);

    // 选第 i 件（若放得下）
    if (cap >= w[i]) res = max(res, (ll)v[i] + dfs(i + 1, cap - w[i]));
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> V;
    w.resize(n); v.resize(n);
    for (int i = 0; i < n; ++i) cin >> w[i];
    for (int i = 0; i < n; ++i) cin >> v[i];

    memo.assign(n, vector<ll>(V + 1, -1));
    cout << dfs(0, V) << "\n";
    return 0;
}

// 递推，一定要倒序
// dp[cap] 表示容量为 cap 的最大价值
vector<long long> dp(V + 1, 0);

for (int i = 0; i < n; ++i) {
    // 0/1 背包倒序枚举容量，避免同一层重复使用第 i 件物品
    for (int cap = V; cap >= w[i]; --cap) {
        dp[cap] = max(dp[cap], dp[cap - w[i]] + (long long)v[i]);
    }
}

cout << dp[V] << "\n";

# 完全背包

物品无限，参考平方数问题，整数问题，选硬币问题
正序 01 背包的递推
注意如果是恰好装满的最少物品选取，那么初始化的时候 dp [0][0] = 0

int n, V;
vector<int> w, v;
vector<vector<ll>> memo;  // memo[i][j]：用前 i 件、容量 j 的最优值
const ll UNK = LLONG_MIN / 4; // 未计算标记（假定 v >= 0）

ll dfs(int i, int j) {
    if (i == 0 || j == 0) return 0;
    ll &res = memo[i][j];
    if (res != UNK) return res;

    // 1) 不用第 i 件（注意下标对应：第 i 件是 w[i-1], v[i-1]）
    res = dfs(i - 1, j);

    // 2) 用第 i 件一次（完全背包：仍是 dfs(i, ...)，可以继续用第 i 件）
    if (j >= w[i - 1]) {
        res = max(res, dfs(i, j - w[i - 1]) + v[i - 1]);
    }
    memo[i][j] = res;
    return res;
}


int dp[MAXN]; // 滚动数组，全局变量自动初始化 注意是 0-base
int DP(vector<int> w, vector<int> v, int n, int V){ 
    // n 为物品数，V 为背包容量，w 是重量
    for(int i = 0; i < n; ++i)
        for(int j = w[i]; j <= V; ++j) // 正序更新！！！
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    return dp[V];
 }

# 多重背包

物品有限个。
当作 01 背包
可以加速，先分组，二进制分组。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Item { int w; ll v; }; // 0/1 物品

// 多重背包 -> 二进制分组 -> 0/1 背包
// n 种物品，容量 V；每种 (w, v, c)
ll multiple_knapsack_binary(int n, int V, const vector<int>& w, const vector<ll>& v, const vector<int>& c) {
    vector<Item> items;
    items.reserve(n * 20); // 预估
    for (int i = 0; i < n; ++i) {
        int cnt = c[i], base = 1;
        while (base <= cnt) { // 1,2,4,..
            items.push_back({w[i] * base, v[i] * (ll)base});
            cnt -= base;
            base <<= 1;
        }
        if (cnt) items.push_back({w[i] * cnt, v[i] * (ll)cnt});
    }
    vector<ll> dp(V+1, 0); // 不要求恰装
    for (auto &it: items) {
        for (int j = V; j >= it.w; --j)
            dp[j] = max(dp[j], dp[j - it.w] + it.v);
    }
    return *max_element(dp.begin(), dp.end()); // 或 dp[V]
}
// 恰好装满（最小化/最大化）问题：初始化目标改（最小化设 dp[0]=0 其余=−INF/+INF 等）。

# 线性 DP

就是一定要以某个 num 结尾？会怎么样，怎么转移过来的？

# 最大子段和

d [i] 表示以 A [i] 结尾的连续序列的最大和。
要么就是自己（前面和是个负数了），要么就是前面的最大值加上自己

int dp[MAXN];
 int MCS(vector<int>& A){
    int ret = dp[0] = A[0];
    for(int i = 1; i < A.size(); ++i){
        dp[i] = max(A[i], dp[i - 1] + A[i]);
        ret = max(ret, dp[i]);
    }
    return ret;
 }

// 进一步需要知道是哪个区间
int dp[MAXN];
pair<int, int> seq[MAXN];  // 记录区间
pair<int, int> MCS(vector<int>& A){
    dp[0] = A[0];
    seq[0] = make_pair(0, 0);
    for(int i = 1; i < A.size(); ++i){
        dp[i] = max(A[i], dp[i - 1] + A[i]);
        if(A[i] < dp[i - 1] + A[i]) // 扩展
            seq[i].first = seq[i - 1].first,  seq[i].second = i;
        else // 单个元素作为新区间
            seq[i].first = seq[i].second = i;
    }
    int ret = 0;
    for(int i = 0; i < A.size(); ++i) 
        if(dp[ret] < dp[i]) ret = i;
    return seq[ret];
 }

# 最大两段子段和

选一个分界点，分左边和右边分别取最大值

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; if (!(cin >> n)) return 0;
    vector<ll> a(n+1);
    for (int i=1;i<=n;i++) cin >> a[i];

    const ll NEG = (ll)-4e18;
    vector<ll> L(n+2, NEG), R(n+2, NEG);

    // 左到右：L[i] = [1..i] 内最大子段和
    ll endSum = NEG;
    for (int i=1;i<=n;i++){
        endSum = (endSum<=0)? a[i] : endSum + a[i];
        L[i] = (i==1)? endSum : max(L[i-1], endSum);
    }
    // 右到左：R[i] = [i..n] 内最大子段和
    ll startSum = NEG;
    for (int i=n;i>=1;i--){
        startSum = (startSum<=0)? a[i] : startSum + a[i];
        R[i] = (i==n)? startSum : max(R[i+1], startSum);
    }

    // 至少隔 1 个元素：i 做“间隔点”
    ll ans = NEG;
    for (int i=2;i<=n-1;i++) ans = max(ans, L[i-1] + R[i+1]);

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

# 最大 m 段子序和

相邻（比如 [2,4] 和 [5,7]）是允许的
至少间隔一个数，把新开一段时用到的状态从 g[i-1] 换成 g[i-2，注意边界

// a: 1..n（a[0] 可忽略）；m: 选 m 段互不相交子段，使总和最大
ll maxMSubarraySum(const vector<ll>& a, int m) {
    int n = (int)a.size() - 1;
    const ll NEG = (ll)-4e18;

    // g[i] = 用前 i 个数选 (k-1) 段的最大和（上一次循环的结果）
    // f[i] = 用前 i 个数选 k 段的最大和（本次循环）
    vector<ll> g(n+1, 0), f(n+1, NEG);

    for (int k = 1; k <= m; ++k) {
        fill(f.begin(), f.end(), NEG);

        ll bestEnd = NEG; // 第 k 段“必须以 i 结尾”的最佳值
        // i 至少为 k（保证能取到 k 段）
        for (int i = k; i <= n; ++i) {
            // 要么把第 k 段继续延伸到 a[i]，要么在 i 启动新段（接在 g[i-1] 后）
            bestEnd = max(bestEnd + a[i], g[i-1] + a[i]);

            // f[i] = 用前 i 个数选 k 段的最大值：要么不选 a[i] 结尾（承接 f[i-1]），要么选
            f[i] = (i == k) ? bestEnd : max(f[i-1], bestEnd);
        }

        swap(g, f); // 下一轮作为“前 k-1 段”的基底
    }
    return g[n];
}

# 受限子序列最大和

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 计算前缀和 P[0..n]
static inline vector<ll> prefix(const vector<ll>& a){
    int n = (int)a.size();
    vector<ll> P(n+1, 0);
    for(int i = 1; i <= n; ++i) P[i] = P[i-1] + a[i-1];
    return P;
}

// 1) 最大子段和，子段长度 ≤ m
// 维护窗口 [r-m, r-1] 内 prefix 的最小值 -> deque 单调递增（存下标）
ll maxSubarrayLenAtMost(const vector<ll>& a, int m){
    int n = (int)a.size();
    auto P = prefix(a);
    deque<int> dq;               // 存候选 l 的下标，保证 P[dq[0]] 最小
    dq.push_back(0);
    ll ans = LLONG_MIN;
    for(int r = 1; r <= n; ++r){
        // 丢掉窗口外 l < r-m
        while(!dq.empty() && dq.front() < r - m) dq.pop_front();
        // 用当前最小前缀更新答案
        ans = max(ans, P[r] - P[dq.front()]);
        // 把 r 作为未来的 l 加入，维持 P 递增
        while(!dq.empty() && P[dq.back()] >= P[r]) dq.pop_back();
        dq.push_back(r);
    }
    return ans;
}

// 2) 最大子段和，子段长度 ≥ m
// 对每个 r(≥m)，取 bestMin = min_{l≤r-m} P[l]
ll maxSubarrayLenAtLeast(const vector<ll>& a, int m){
    int n = (int)a.size();
    auto P = prefix(a);
    ll ans = LLONG_MIN, bestMin = LLONG_MAX;
    for(int r = 1; r <= n; ++r){
        if(r - m >= 0) bestMin = min(bestMin, P[r - m]); // 更新允许的最小前缀
        if(r >= m)      ans = max(ans, P[r] - bestMin);
    }
    return ans;
}

// （赠）3) 最大子段和，子段长度 = m
ll maxSubarrayLenExactly(const vector<ll>& a, int m){
    int n = (int)a.size();
    auto P = prefix(a);
    ll ans = LLONG_MIN;
    for(int r = m; r <= n; ++r) ans = max(ans, P[r] - P[r - m]);
    return ans;
}

# 环状最大和

将序列倍长，就可以做一遍长度不大于 n 的受限最大子段和。
思路（“最大 + 最小” 法）令 sum = Σa[i] 。
线性最大子段和 best = maxSubarray(a) （Kadane）。
线性最小子段和 mn = minSubarray(a) （等价于在 -a 上跑 Kadane）。
环状答案是 max(best, sum - mn) 。
但全负时 mn == sum （最小子段就是整段），此时环状不该取空洞，所以取 best 。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static inline ll kadane_max(const vector<ll>& a){
    ll cur = a[0], best = a[0];
    for(size_t i=1;i<a.size();++i){
        cur = max(a[i], cur + a[i]);
        best = max(best, cur);
    }
    return best;
}
static inline ll kadane_min(const vector<ll>& a){
    ll cur = a[0], best = a[0];
    for(size_t i=1;i<a.size();++i){
        cur = min(a[i], cur + a[i]);
        best = min(best, cur);
    }
    return best;
}

// 环状最大子段和
ll maxSubarrayCircular(const vector<ll>& a){
    ll best = kadane_max(a);
    ll sum = accumulate(a.begin(), a.end(), 0LL);
    ll mn  = kadane_min(a);
    if (mn == sum) return best;          // 全负：不能取“整段作为最小子段”
    return max(best, sum - mn);
}

# 环状最大双子段和

// 线性最大双子段和（两段非空，且至少间隔 1 个数）
ll maxTwoSegmentsLinear_gap1(const vector<ll>& a){
    int n = (int)a.size();
    if (n < 3) return LLONG_MIN/4;  // 不可行
    vector<ll> L(n), R(n), pre(n), suf(n);

    // 以 i 结尾的最大子段和
    L[0] = a[0];
    for(int i=1;i<n;++i) L[i] = max(a[i], L[i-1]+a[i]);
    pre[0] = L[0];
    for(int i=1;i<n;++i) pre[i] = max(pre[i-1], L[i]);

    // 以 i 开始的最大子段和
    R[n-1] = a[n-1];
    for(int i=n-2;i>=0;--i) R[i] = max(a[i], R[i+1]+a[i]);
    suf[n-1] = R[n-1];
    for(int i=n-2;i>=0;--i) suf[i] = max(suf[i+1], R[i]);

    ll ans = LLONG_MIN/4;
    for(int mid=1; mid+1 < n; ++mid){      // 左段 ≤ mid-1，右段 ≥ mid+1
        ans = max(ans, pre[mid-1] + suf[mid+1]);
    }
    return ans;
}

// 环状最大双子段和（两段非空，且至少间隔 1 个数）
ll maxTwoSegmentsCircular_gap1(const vector<ll>& a){
    int n = (int)a.size();
    if (n < 2) return LLONG_MIN/4; // 两段都非空在环上至少要 2 个点
    ll t1 = maxTwoSegmentsLinear_gap1(a);     // 不跨环
    ll sum = accumulate(a.begin(), a.end(), 0LL);
    vector<ll> b(n);
    for(int i=0;i<n;++i) b[i] = -a[i];
    ll t2 = sum + maxTwoSegmentsLinear_gap1(b);  // 跨环（选两段最小缺口）
    return max(t1, t2);
}

# 环最大合并

# 最大子矩阵和

定上下两行→把这两行之间的每一列纵向求和→变成一维的最大子段和（Kadane）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Rect { ll sum; int top, bot, lef, rig; };

// Kadane，顺便恢复左右端点
static inline pair<ll, pair<int,int>> kadane_with_pos(const vector<ll>& a){
    ll best = LLONG_MIN, cur = 0;
    int bestL = 0, bestR = -1, curL = 0;
    for (int r = 0; r < (int)a.size(); ++r) {
        if (cur <= 0) { cur = a[r]; curL = r; }
        else          { cur += a[r]; }
        if (cur > best) { best = cur; bestL = curL; bestR = r; }
    }
    return {best, {bestL, bestR}};
}

// 最大子矩阵和（返回和与矩形坐标，0-index）
Rect max_submatrix_sum(const vector<vector<int>>& A){
    int n = (int)A.size(), m = (int)A[0].size();
    Rect ans{LLONG_MIN, 0,0,0,0};
    vector<ll> col(m, 0);

    for (int top = 0; top < n; ++top) {
        fill(col.begin(), col.end(), 0);
        for (int bot = top; bot < n; ++bot) {
            for (int c = 0; c < m; ++c) col[c] += A[bot][c];
            auto [best, LR] = kadane_with_pos(col);
            if (best > ans.sum) ans = {best, top, bot, LR.first, LR.second};
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    // 如果是“黑白差值”：把 '1' 映射为 +1，'0' 映射为 -1
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; ++i){
        string s; cin >> s;
        for (int j = 0; j < m; ++j) a[i][j] = (s[j] == '1' ? +1 : -1);
    }
    auto res = max_submatrix_sum(a);
    cout << res.sum << "\n";                 // 最大子矩阵和
// 如需坐标：cout << res.top << " " << res.bot << " " << res.lef << " " << res.rig << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; 
    if (!(cin >> n)) return 0;
    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) cin >> a[i][j];

    long long ans = LLONG_MIN;
    vector<long long> col(n, 0);

    for (int top = 0; top < n; ++top) {
        fill(col.begin(), col.end(), 0);
        for (int bottom = top; bottom < n; ++bottom) {
            for (int j = 0; j < n; ++j) col[j] += a[bottom][j];   // 压缩为一维
            long long cur = col[0], best = col[0];               // Kadane
            for (int j = 1; j < n; ++j) {
                cur = max(col[j], cur + col[j]);
                best = max(best, cur);
            }
            ans = max(ans, best);
        }
    }
    cout << ans << "\n";
    return 0;
}

# 最长上升子序列

# 最长公共子序列

一个简要的例子：字符串 abcde 与字符串 acde 的公共子序列有 a 、 c 、 d 、 e 、 ac 、 ad 、 ae 、 cd 、 ce 、 de 、 ade 、 ace 、 cde 、 acde ，最长公共子序列的长度是 4。就是求 f (i,j)，A 的前 i 个元素，B 的前 j 个元素时的公共序列

dp 数组含义， 就是 f (i,j)，这个可以固定住一个状态
 我们思考，i 和 j 增加会怎么样

#include <bits/stdc++.h>
using namespace std;

// f(i,j): a 的前 i 个字符 和 b 的前 j 个字符 的 LCS 长度
int dfs(const string& a, int i, const string& b, int j, vector<vector<int>>& memo){
    if (i == 0 || j == 0) return 0;
    int &res = memo[i][j];
    if (res != -1) return res;
    if (a[i-1] == b[j-1]) return res = 1 + dfs(a, i-1, b, j-1, memo);
    return res = max(dfs(a, i-1, b, j, memo), dfs(a, i, b, j-1, memo));
}

int LCS_len_dfs(const string& a, const string& b){
    int n = (int)a.size(), m = (int)b.size();
    vector<vector<int>> memo(n+1, vector<int>(m+1, -1));
    return dfs(a, n, b, m, memo);
}

#include <bits/stdc++.h>
using namespace std;

// 返回 LCS 长度；如需序列，可用 dp 回溯（见注释）。
int LCS_len_dp(const string& a, const string& b){
    int n = (int)a.size(), m = (int)b.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 (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[n][m];
}

/* 如要恢复一个 LCS：
string LCS_pick(const string& a, const string& b){
    int n=a.size(), m=b.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)
        dp[i][j] = (a[i-1]==b[j-1]) ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]);

    string res; int i=n, j=m;
    while(i>0 && j>0){
        if(a[i-1]==b[j-1]){ res.push_back(a[i-1]); --i; --j; }
        else if(dp[i-1][j] >= dp[i][j-1]) --i;
        else --j;
    }
    reverse(res.begin(), res.end());
    return res;
}
*/

# 树状 DP

# 其他题目

最小操作次数使数组元素相等：
 给定一个长度为 n 的 ** 非空 ** 整数数组，每次操作将会使 n - 1 个元素增加 1。找出让数组所有元素相等的最小操作次数。
 输入：[1,2,3] 输出：3 解释：
 只需要 3 次操作（注意每次操作会增加两个元素的值）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

本题采用动态规划的方法，首先将给定数组进行排序（从小到大排序），其次依次遍历排序后的数组，当访问第 i 个元素时计算 diff = a [i]-a [i-1]，即 a [i-1] 和 a [i] 之间的差值。因为每次操作元素只能增加 1，所以操作次数 move += diff。按照题目要求每次将会操作 n-1 个元素，因此当遍历到第 i 个元素时，除了前 i-1 个元素要增加 diff，后面的 a [j] += diff（其中 j > i && j < n）。实际上我们可以将 a [j] 的增幅，累积到 move 上面，当每次遍历到第 i 个元素时，先更新 a [i] += move 再计算 diff，这样就不需要每次更新 a [j] 的值。遍历结束后 move 的值即为最小的操作次数

class Solution {
public:
    int minMoves(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int diff = 0;
        int move = 0;
        for(int i = 1; i < n; ++i)
        {
            nums[i] += move;
            diff = nums[i] - nums[i-1];
            move += diff;
        }
        return move;
    }
};

# 树

# 基本定义和构树


// 节点属性（1..tot），0 表示空
int n = 0, tot = 0;
vector<int> lc, rc, val;      // 左儿子、右儿子、节点值
unordered_map<int,int> pos;   // 值 -> inorder 位置，值唯一


void init(int n_){
    n = n_;
    tot = 0;
    lc.assign(n+1, 0);
    rc.assign(n+1, 0);
    val.assign(n+1, 0);
    pos.clear();
    pos.reserve(n*2+1);
}

// ====== 构树（前序 + 中序）======
// 入参：pre[0..n-1], in[0..n-1]；返回：根下标（int）
int buildFromPreIn(const vector<int>& pre, const vector<int>& in){
    init((int)pre.size());
    for(int i=0;i<(int)in.size();++i) pos[in[i]]=i;
    return buildPreIn(pre, 0, (int)pre.size()-1, in, 0, (int)in.size()-1);
}
int buildPreIn(const vector<int>& pre, int pl, int pr,
               const vector<int>& in,  int il, int ir){
    if(pl>pr) return 0;
    int rootVal = pre[pl];
    int k = pos[rootVal];           // root 在中序中的位置
    int L = k - il;                 // 左子树大小
    int u = ++tot; val[u]=rootVal;
    lc[u] = buildPreIn(pre, pl+1, pl+L,   in, il,   k-1);
    rc[u] = buildPreIn(pre, pl+L+1, pr,   in, k+1,  ir);
    return u;
}

// ====== 构树（中序 + 后序）======
int buildFromInPost(const vector<int>& in, const vector<int>& post){
    init((int)in.size());
    for(int i=0;i<(int)in.size();++i) pos[in[i]]=i;
    return buildInPost(in, 0, (int)in.size()-1, post, 0, (int)post.size()-1);
}
int buildInPost(const vector<int>& in,   int il, int ir,
                const vector<int>& post, int pl, int pr){
    if(il>ir) return 0;
    int rootVal = post[pr];
    int k = pos[rootVal];
    int L = k - il;
    int u = ++tot; val[u]=rootVal;
    lc[u] = buildInPost(in, il, k-1, post, pl,       pl+L-1);
    rc[u] = buildInPost(in, k+1, ir, post, pl+L,     pr-1);
    return u;
}

// ====== 遍历（递归版）======
void preorder(int u, vector<int>& out) const {
    if(!u){ out.push_back(INT_MIN); return; } 
    out.push_back(val[u]);
    preorder(lc[u], out);
    preorder(rc[u], out);
}
void inorderWalk(int u, vector<int>& out) const {
    if(!u){ out.push_back(INT_MIN); return; }
    inorderWalk(lc[u], out);
    out.push_back(val[u]);
    inorderWalk(rc[u], out);
}
void postorder(int u, vector<int>& out) const {
    if(!u){ out.push_back(INT_MIN); return; }
    postorder(lc[u], out);
    postorder(rc[u], out);
    out.push_back(val[u]);
}
// 层序：输出值序列
vector<int> levelorder(int root) const {
    vector<int> res;
    if(!root) return res;
    queue<int> q; q.push(root);
    while(!q.empty()){
        int u=q.front(); 
        q.pop();
        if(!u) // 空的逻辑 
        res.push_back(val[u]);
        if(lc[u]) q.push(lc[u]);
        if(rc[u]) q.push(rc[u]);
    }
    return res;
}

// ====== 序列化 / 反序列化（前序 + “#,”表空）======
// 序列化为字符串
void serializePre(int u, string& out) const{
    if(!u){ out += "#,"; return; }
    out += to_string(val[u]) + ",";
    serializePre(lc[u], out);
    serializePre(rc[u], out);
}
// 反序列化：把 tokens 还原为树，返回根下标
int deserializePre(list<string>& t){
    if(t.empty()) return 0;
    string s = t.front(); t.pop_front();
    if(s=="#") return 0;
    int u = ++tot; val[u] = stoi(s);
    lc[u] = deserializePre(t);
    rc[u] = deserializePre(t);
    return u;
}
int deserializePreString(const string& data){
    init(n); // 若不确定 n，init 可以先传 0，
    // 再动态扩容（简单起见保持固定池）
    list<string> t; string x; istringstream iss(data);
    while(getline(iss, x, ',')) if(!x.empty()) t.push_back(x);
    return deserializePre(t);
}


// ====== 卡塔兰数 & BST 计数 ======
// 1) 取模版：Catalan(n) = C(2n, n)/(n+1)  (mod 1e9+7)
struct CombMod {
    static const int MOD = 1'000'000'007;
    vector<long long> fac, ifac;
    CombMod(int N=0){ if(N) init(N); }
    long long qpow(long long a,long long e){
        long long r=1; while(e){ if(e&1) r=r*a%MOD; a=a*a%MOD; e>>=1; } return r;
    }
    void init(int N){
        fac.assign(N+1,1);
        for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%MOD;
        ifac.assign(N+1,1);
        ifac[N]=qpow(fac[N], MOD-2);
        for(int i=N;i>0;i--) ifac[i-1]=ifac[i]*i%MOD;
    }
    long long C(int n,int k){
        if(k<0||k>n) return 0;
        return fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;
    }
    long long catalan(int n){
        if(n<0) return 0;
        return C(2*n, n) * qpow(n+1, MOD-2) % MOD;
    }
};
// 2) long long 版（不取模，小 n 用）
long long catalanLL(int n){
    vector<long long> dp(n+1,0);
    dp[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            dp[i]+=dp[j]*dp[i-1-j];
    return dp[n];
}
// 不同 BST 的数量（值为 1..n）：等于 Catalan(n)
long long numBST_LL(int n){ return catalanLL(n); }
long long numBST_mod(int n, CombMod& C){ return C.catalan(n); }

# 树的直径，中心，重心

就是求树中最远的两个端点，下面可以处理负权边。

struct Edge { int u, v; long long w; };

constexpr int N = 100000 + 5;
const long long NEG_INF = LLONG_MIN / 4;

int n;
vector<Edge> edges;           // 存边：u, v, w
vector<int> G[N];             // 邻接表存“边的下标”
long long downv[N];           // 从 u 向下的最大和（至少一条边）
long long ans = NEG_INF;      // 直径（至少一条边）

void dfs(int u, int fa) {
  long long best1 = NEG_INF, best2 = NEG_INF;

  for (int eid : G[u]) {
    const Edge &e = edges[eid];
    int v = (e.u == u ? e.v : e.u);
    if (v == fa) continue;

    dfs(v, u);
    long long t = max(e.w, downv[v] + e.w); // 允许只取这一条边（关键应对负权）

    if (t > best1) { best2 = best1; best1 = t; }
    else if (t > best2) { best2 = t; }
  }

  downv[u] = best1;
  ans = max(ans, best1);                 // 单链候选（包含单边）
  if (best2 != NEG_INF) ans = max(ans, best1 + best2);  // 两链拼接候选
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n;
  edges.reserve(n - 1);
  for (int i = 1; i < n; ++i) {
    int u, v; long long w;
    cin >> u >> v >> w;
    edges.push_back({u, v, w});
    int id = (int)edges.size() - 1;
    G[u].push_back(id);
    G[v].push_back(id);
  }

  dfs(1, 0);
  cout << ans << "\n";
  return 0;
}

中心位于树的直径上，找树的 “最小高度根”，其实就是找树的中心；
直径为偶数 ⇒ 1 个中心；奇数 ⇒ 2 个中心（中点两端）

// 这份代码默认节点编号从 1 开始，即 i ∈ [1,n]，使用 vector 存图
int d1[N], d2[N], up[N], x, y, mini = 1e9;  // d1,d2 对应上文中的 len1,len2

struct node {
  int to, val;  // to 为边指向的节点，val 为边权
};

vector<node> nbr[N];

void dfsd(int cur, int fa) {  // 求取 len1 和 len2
  for (node nxtn : nbr[cur]) {
    int nxt = nxtn.to, w = nxtn.val;  // nxt 为这条边通向的节点，val 为边权
    if (nxt == fa) {
      continue;
    }
    dfsd(nxt, cur);
    if (d1[nxt] + w > d1[cur]) {  // 可以更新最长链
      d2[cur] = d1[cur];
      d1[cur] = d1[nxt] + w;
    } else if (d1[nxt] + w > d2[cur]) {  // 不能更新最长链，但可更新次长链
      d2[cur] = d1[nxt] + w;
    }
  }
}

void dfsu(int cur, int fa) {
  for (node nxtn : nbr[cur]) {
    int nxt = nxtn.to, w = nxtn.val;
    if (nxt == fa) {
      continue;
    }
    up[nxt] = up[cur] + w;
    if (d1[nxt] + w != d1[cur]) {  // 如果自己子树里的最长链不在 nxt 子树里
      up[nxt] = max(up[nxt], d1[cur] + w);
    } else {  // 自己子树里的最长链在 nxt 子树里，只能使用次长链
      up[nxt] = max(up[nxt], d2[cur] + w);
    }
    dfsu(nxt, cur);
  }
}

void GetTreeCenter() {  // 统计树的中心，记为 x 和 y（若存在）
  dfsd(1, 0);
  dfsu(1, 0);
  for (int i = 1; i <= n; i++) {
    if (max(d1[i], up[i]) < mini) {  // 找到了当前 max(len1[x],up[x]) 最小点
      mini = max(d1[i], up[i]);
      x = i;
      y = 0;
    } else if (max(d1[i], up[i]) == mini) {  // 另一个中心
      y = i;
    }
  }
}

树的重心，把他去了之后，子树的节点总数最小

//节点编号从 1 开始，即 i ∈ [1,n]
int size[MAXN],  // 这个节点的「大小」（所有子树上节点数 + 该节点）
    weight[MAXN],  // 这个节点的「重量」，即所有子树「大小」的最大值
    centroid[2];  // 用于记录树的重心（存的是节点编号）

void GetCentroid(int cur, int fa) {  // cur 表示当前节点 (current)
  size[cur] = 1;
  weight[cur] = 0;
  for (int i = head[cur]; i != -1; i = e[i].nxt) {
    if (e[i].to != fa) {  // e[i].to 表示这条有向边所通向的节点。
      GetCentroid(e[i].to, cur);
      size[cur] += size[e[i].to];
      weight[cur] = max(weight[cur], size[e[i].to]);
    }
  }
  weight[cur] = max(weight[cur], n - size[cur]);
  if (weight[cur] <= n / 2) {  // 依照树的重心的定义统计
    centroid[centroid[0] != 0] = cur;
  }
}

# 最近公共祖先

LCA (Lowest Common Ancestor)

倍增法 LCA
预处理： O(n log n)
查询： O(log n)
优点：内存较省，写法简单。
适合：中小规模，查询次数不多。

const int N = 200005;
int n, dfn[N], dep[N], fa[N][20], tot;
vector<int> G[N];

void dfs0(int u,int p){
    dfn[u] = ++tot;
    fa[u][0] = p; dep[u] = dep[p]+1;
    for(int i=1;i<20;i++) fa[u][i] = fa[fa[u][i-1]][i-1];
    for(int v:G[u]) if(v!=p) dfs0(v,u);
}
int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=19;i>=0;i--)
        if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    if(u==v) return u;
    for(int i=19;i>=0;i--)
        if(fa[u][i]!=fa[v][i]) u=fa[u][i], v=fa[v][i];
    return fa[u][0];
}
int root = 1; 
dfs0(root, 0);

**Euler Tour + ST 表 LCA - 树结构固定 + LCA 查询很多 **
预处理： O(n log n)
查询： O(1)
缺点：额外存一个欧拉序（ 2n 大小）+ ST 表（ O(n log n) 内存），比倍增占空间。
适合：大规模、多查询的题，比如几十万次 LCA。

#include <bits/stdc++.h>
using namespace std;

const int N = 200000 + 5;    
struct Edge { int to, next; } E[N<<1];
int head[N], ecnt;

int n;
int depthEuler[N<<1], dfn[N<<1], pos[N], tot;
int lg2v[N<<1];
int st[20][N<<1];      // 存“最小深度值”
int revv[20][N<<1];    // 存“该最小深度对应的节点编号”

void add_edge(int u,int v){
    E[++ecnt] = {v, head[u]}; head[u] = ecnt;
    E[++ecnt] = {u, head[v]}; head[v] = ecnt;
}

void dfs(int u, int fa, int dep){
    dfn[++tot] = u; depthEuler[tot] = dep;
    if(!pos[u]) pos[u] = tot;              // 记录第一次出现位置
    for(int i=head[u]; i; i=E[i].next){
        int v = E[i].to;
        if(v==fa) continue;
        dfs(v, u, dep+1);
        dfn[++tot] = u; depthEuler[tot] = dep;   // 回溯时再记父亲一次
    }
}

void build_st(){
    // 预处理 log
    lg2v[1] = 0;
    for(int i=2;i<=tot;i++) lg2v[i] = lg2v[i>>1] + 1;

    // k=0 层
    for(int i=1;i<=tot;i++){
        st[0][i] = depthEuler[i];
        revv[0][i] = dfn[i];
    }
    // 其余层
    for(int k=1;k<=lg2v[tot];k++){
        for(int i=1;i + (1<<k) - 1 <= tot; i++){
            int leftDepth  = st[k-1][i];
            int rightDepth = st[k-1][i + (1<<(k-1))];
            if(leftDepth <= rightDepth){
                st[k][i]   = leftDepth;
                revv[k][i] = revv[k-1][i];
            }else{
                st[k][i]   = rightDepth;
                revv[k][i] = revv[k-1][i + (1<<(k-1))];
            }
        }
    }
}

int rmq_node(int L, int R){                 // 在欧拉序区间 [L,R] 上取“最浅节点”
    int k = lg2v[R - L + 1];
    int dL = st[k][L], dR = st[k][R - (1<<k) + 1];
    if(dL <= dR) return revv[k][L];
    else         return revv[k][R - (1<<k) + 1];
}

int lca(int u,int v){
    int L = pos[u], R = pos[v];
    if(L > R) swap(L, R);
    return rmq_node(L, R);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for(int i=1;i<=n;i++){ head[i]=0; pos[i]=0; }
    ecnt = tot = 0;

    for(int i=1;i<n;i++){
        int u,v; cin >> u >> v;
        add_edge(u,v);
    }

    int root = 1;           // 可选任意根
    dfs(root, 0, 0);
    build_st();

    int q; cin >> q;
    while(q--){
        int u,v; cin >> u >> v;
        cout << lca(u,v) << "\n";
    }
    return 0;
}

# 虚树

在原树上只保留 “关键点 + 它们的 LCA (保留节点的祖辈关系)”，
并用 路径属性 (最小边 / 最大边) 压缩成一棵小树，使 DP / 查询复杂度降为 O (k log n)。
关键点稀疏，整树太大没法全遍历；
需要保留 关键点之间的路径信息（通过 LCA 连接）；
常见题型：消耗战、点集 Steiner Tree、K 点覆盖、路径 DP 等

**min_on_path** ：决定路径聚合什么信息（min /max/sum / 自定义）。
**addVEdge** ：虚树边是否带权，权值怎么定义。

#include <bits/stdc++.h>
using namespace std;

const int N = 250000 + 5;
struct Edge { int to, w; };
vector<Edge> G[N];   // 原树

int n, m;
int dep[N], fa[N][20], minEdge[N][20], dfn[N], timer;
int LOG = 19;

// ========== 原树 LCA 预处理 ==========
void dfs0(int u,int p,int w){
    dfn[u] = ++timer;
    dep[u] = dep[p] + 1;
    fa[u][0] = p;
    minEdge[u][0] = (p ? w : INT_MAX); // 到父亲的边权
    for(int i=1;i<=LOG;i++){
        fa[u][i] = fa[fa[u][i-1]][i-1];
        minEdge[u][i] = min(minEdge[u][i-1], minEdge[fa[u][i-1]][i-1]);
    }
    for(auto e:G[u]) if(e.to!=p) dfs0(e.to,u,e.w);
}

int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=LOG;i>=0;i--)
        if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    if(u==v) return u;
    for(int i=LOG;i>=0;i--)
        if(fa[u][i]!=fa[v][i]) u=fa[u][i], v=fa[v][i];
    return fa[u][0];
}

// 求 u 到 v 路径上的最小边权   根据题目来，需要这个边有什么属性
int min_on_path(int u,int v){
    int res = INT_MAX;
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=LOG;i>=0;i--)
        if(dep[fa[u][i]]>=dep[v]){
            res = min(res, minEdge[u][i]);
            u = fa[u][i];
        }
    if(u==v) return res;
    for(int i=LOG;i>=0;i--){
        if(fa[u][i]!=fa[v][i]){
            res = min(res, min(minEdge[u][i], minEdge[v][i]));
            u = fa[u][i], v = fa[v][i];
        }
    }
    res = min(res, min(minEdge[u][0], minEdge[v][0]));
    return res;
}

// ========== 虚树部分 ==========
vector<Edge> vG[N];  // 虚树
bool isKey[N];       // 是否关键点

void addVEdge(int u,int v){ // u 和 v 中间的东西交给 min_on_path 来解决
    int w = min_on_path(u,v);
    vG[u].push_back({v,w});
    vG[v].push_back({u,w});
}

int stk[N], top;

vector<int> nodes; // 本次虚树节点

void build_virtual_tree(vector<int>& h){
    sort(h.begin(), h.end(), [&](int a,int b){ return dfn[a]<dfn[b]; });
    stk[top=1] = 1; // 保证根在虚树里
    nodes.push_back(1);
    vG[1].clear();

    for(int x:h){
        if(x==1) continue;
        int l = lca(x, stk[top]);
        if(l != stk[top]){
            while(dep[l] < dep[stk[top-1]]){
                addVEdge(stk[top-1], stk[top]);
                top--;
            }
            if(l == stk[top-1]){
                addVEdge(l, stk[top]); top--;
            } else {
                vG[l].clear();
                addVEdge(l, stk[top]);
                stk[top] = l;
                nodes.push_back(l);
            }
        }
        vG[x].clear();
        stk[++top] = x;
        nodes.push_back(x);
    }
    for(int i=1;i<top;i++) addVEdge(stk[i], stk[i+1]);
}

// ========== 在虚树上 DP ==== 在虚树上解决问题
long long dp(int u,int p){
    long long res = 0;
    for(auto e:vG[u]){
        if(e.to==p) continue;
        long long child = dp(e.to,u);
        if(isKey[e.to]) res += e.w;
        else res += min(1LL*e.w, child);
    }
    return res;
}

// ========== 主函数 ==========
int main(){

    cin >> n;
    for(int i=1;i<n;i++){
        int u,v,w; cin>>u>>v>>w;
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }
    dfs0(1,0,0);

    cin >> m;
    while(m--){
        int k; cin>>k;
        vector<int> h(k);
        for(int i=0;i<k;i++) cin>>h[i], isKey[h[i]]=true;
        nodes.clear();
        build_virtual_tree(h);
        cout << dp(1,0) << "\n";
        for(int x:nodes) isKey[x]=false; // 清理标记
    }
}

# 树的分治

# 点分治
树的直径、点对距离类问题，大多可以用 点分治。 O (n log n)
原理：树是一种 无环连通图，所以 ** 两点间的路径唯一， **
考虑某个重心 c，那么路径 (u,v) 有两种可能：经过 c，不经过 c（在某个子树内）
** 做法： **
选出树的重心，计算所有经过重心的点对距离。
然后递归到子树去处理。
在处理 “经过重心的点对” 时：
枚举每个子树，算出从子树点到重心的距离；
用一个 set/hash 存储已出现的距离，检查是否存在两子树拼起来的点对距离等于 k 。

基本只改 collect 收集的 “路径属性” 和 solve 里 “查询 / 合并” 的逻辑

// 1) 图存储（链式或 vector 都行）
struct E{int to; int w;};
vector<E> g[N];
inline void addEdge(int u,int v,int w){ g[u].push_back({v,w}); g[v].push_back({u,w}); }

// 2) 求直径（可选：做 k>直径 的剪枝）
long long farDist[N]; int farNode;
void dfs_far(int u,int p,long long d){
    farDist[u]=d; if(d>farDist[farNode]) farNode=u;
    for(auto e:g[u]) if(e.to!=p) dfs_far(e.to,u,d+e.w);
}
long long tree_diameter(){
    farNode=1; memset(farDist,0,(n+1)*sizeof(long long)); dfs_far(1,0,0);
    int s=farNode; memset(farDist,0,(n+1)*sizeof(long long)); dfs_far(s,0,0);
    return farDist[farNode];
}

// 3) 点分治：子树大小 + 找重心
int sz[N], dead[N];
void getSize(int u,int p){
    sz[u]=1;
    for(auto e:g[u]) if(e.to!=p && !dead[e.to]) getSize(e.to,u), sz[u]+=sz[e.to];
}
int centroid(int u){                    // 返回以 u 为根的分治重心
    getSize(u,0); int tot=sz[u], p=0, cur=u; bool moved=true;
    while(moved){
        moved=false;
        for(auto e:g[cur]) if(e.to!=p && !dead[e.to] && sz[e.to]*2>tot){ p=cur; cur=e.to; moved=true; break; }
    }
    return cur;
}

// 4) 从某点向下“收集路径属性”（这里默认收集到重心的距离）
int MAXK;
void collect(int u,int p,int d, vector<int>& ds){
    if(d>MAXK) return;                 // 超界就剪枝（按题意改）
    ds.push_back(d);
    for(auto e:g[u]) if(e.to!=p && !dead[e.to]) collect(e.to,u,d+e.w,ds);
}

// 5) 动态桶（打标清零，不用 memset）
vector<int> tag; int CUR = 1;
inline void mark(int x){ if(0<=x && x<=MAXK) tag[x]=CUR; }
inline bool has (int x){ return (0<=x && x<=MAXK && tag[x]==CUR); }

// 6) 分治框架（“在重心这里做一次全局合并” + 递归子树）
void solve(int entry){
    int c = centroid(entry);
    dead[c]=1;

    // —— 在这里：写“经过重心的所有点对”的逻辑 ——
    // 例：存在恰好为 k 的距离？
    CUR++; mark(0);                 // 重心自身距离 0 入桶
    // 遍历每个子树，先查后并
    for(auto e:g[c]) if(!dead[e.to]){
        vector<int> ds; collect(e.to,c,e.w,ds);
        sort(ds.begin(),ds.end()); ds.erase(unique(ds.begin(),ds.end()),ds.end());

        // 查询阶段（用桶判断能否与之前子树凑出答案）
        // ……（按题写）……

        // 合并阶段（把本子树的值加入桶，供后续子树使用）
        for(int d:ds) mark(d);
    }
    // —— 重心处理结束 ——

    for(auto e:g[c]) if(!dead[e.to]) solve(e.to);
}

# 树同构

** （树哈希 / 树同构 / 子树去重） **
子树哈希：
「父亲的哈希值 = 儿子子树哈希的多重集的哈希」。
有根树问题：
根给定（通常根 = 1），只需要 DFS 一次，收集每个结点的哈希，扔集合里去重。
无根树同构问题：
找重心（最多 2 个），以重心为根算哈希，取这 1~2 个哈希的规范形式作为整棵树的哈希。

sum-of-shift，一遍 DFS, 给定根，求不同构子树

#include <bits/stdc++.h>
using namespace std;
using U64 = unsigned long long;

const int N = 1'000'000 + 5;
vector<int> g[N];
U64 H[N];

struct Shifter {
    U64 mask;
    Shifter(uint64_t seed=123456789){ mt19937_64 rng(seed); mask=rng(); }
    inline U64 operator()(U64 x) const {
        x ^= mask; x ^= x<<13; x ^= x>>7; x ^= x<<17; x ^= mask; return x;
    }
} S;

U64 dfs(int u,int p){
    U64 h = 1;
    for(int v:g[u]) if(v!=p) h += S(dfs(v,u));
    return H[u]=h;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin>>n;
    for(int i=1;i<n;i++){int u,v;cin>>u>>v; g[u].push_back(v); g[v].push_back(u);}
    dfs(1,0);
    unordered_set<U64> st; st.reserve(n*2);
    for(int u=1;u<=n;u++) st.insert(H[u]);
    cout<<st.size()<<"\n";
}

无根树，先找树心 + AHU 标签

#include <bits/stdc++.h>
using namespace std;

// 向量哈希，用于 unordered_map<vector<int>,int>
struct VHash {
  size_t operator()(const vector<int>& a) const noexcept {
    size_t h=0;
    for(int x:a) h = h*1315423911u + x + 0x9e3779b97f4a7c15ULL + (h<<6) + (h>>2);
    return h;
  }
};

struct TreeHash {
  int n;
  vector<vector<int>> g;
  TreeHash(int n=0):n(n),g(n){}
  void add_edge(int u,int v){ g[u].push_back(v); g[v].push_back(u); }

  // 找树的中心（1 个或 2 个）
  vector<int> centers() const {
    if(n==1) return {0};
    vector<int> deg(n); queue<int> q;
    for(int i=0;i<n;i++){deg[i]=g[i].size(); if(deg[i]<=1) q.push(i);}
    int rem=n;
    while(rem>2){
      int k=q.size(); rem-=k;
      while(k--){ int u=q.front(); q.pop();
        for(int v:g[u]) if(--deg[v]==1) q.push(v);
      }
    }
    vector<int> c; while(!q.empty()){c.push_back(q.front()); q.pop();}
    sort(c.begin(),c.end());
    return c;
  }

  // 递归计算以 u 为根的 AHU 哈希标签
  int rooted_hash(int u,int p,
      unordered_map<vector<int>,int,VHash>& dict,int& nxt) const {
    vector<int> ch;
    for(int v:g[u]) if(v!=p) ch.push_back(rooted_hash(v,u,dict,nxt));
    sort(ch.begin(),ch.end()); // 孩子标签排序
    auto it=dict.find(ch);
    if(it==dict.end()) return dict.emplace(ch,nxt++).first->second;
    return it->second;
  }

  int canonical_label() const {
    if(n==1) return 1;
    auto c = centers();
    unordered_map<vector<int>,int,VHash> dict; int nxt=1;
    int h1 = rooted_hash(c[0],-1,dict,nxt);
    if(c.size()==1) return h1;
    // 第二个中心要用独立 dict 计算，避免相互污染
    unordered_map<vector<int>,int,VHash> dict2; int nxt2=1;
    int h2 = rooted_hash(c[1],-1,dict2,nxt2);
    return min(h1,h2);
  }

  static bool isomorphic(const TreeHash& A,const TreeHash& B){
    return A.n==B.n && A.canonical_label()==B.canonical_label();
  }
};

TreeHash T(n);
for(int i=0,u,v;i<n-1;i++){cin>>u>>v; --u;--v; T.add_edge(u,v);}
cout << "Label = " << T.canonical_label() << "\n";

cout<<(TreeHash::isomorphic(A,B)?"YES":"NO")<<"\n";

# 区间 k-th

主席树

#include <bits/stdc++.h>
using namespace std;

struct PST {
    vector<int> lc, rc, sum, root; // 节点左右儿子、计数、每个前缀的根
    vector<int> vals;              // 离散化后的有序值域
    int V=0, tot=0;                // 值域大小、节点总数

    // 新节点 = 拷贝自 from
    int new_node(int from){
        lc.push_back(lc[from]);
        rc.push_back(rc[from]);
        sum.push_back(sum[from]);
        return ++tot;
    }

    // 在 prev 的基础上，把位置 pos 的计数 +1，返回新根
    int update(int prev, int l, int r, int pos){
        int now = new_node(prev);
        sum[now] = sum[prev] + 1;
        if(l < r){
            int mid = (l + r) >> 1;
            if(pos <= mid) { lc[now] = update(lc[prev], l, mid, pos); }
            else           { rc[now] = update(rc[prev], mid+1, r, pos); }
        }
        return now;
    }

    // 查询 [L,R] 的第 k 小（在 root[R] 与 root[L-1] 上二分下放）
    int kth(int uR, int uL, int l, int r, int k){
        if(l == r) return l;
        int mid = (l + r) >> 1;
        int cntLeft = sum[ lc[uR] ] - sum[ lc[uL] ];
        if(k <= cntLeft) return kth(lc[uR], lc[uL], l, mid, k);
        else             return kth(rc[uR], rc[uL], mid+1, r, k - cntLeft);
    }

    // 初始化并建所有前缀版本
    void build_all(const vector<int>& a){ // a: 1..n
        int n = (int)a.size() - 1;
        // 离散化
        vals.assign(a.begin()+1, a.end());
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
        V = (int)vals.size();

        lc.assign(1, 0); rc.assign(1, 0); sum.assign(1, 0); // 节点 0 为“空”
        tot = 0;
        root.assign(n+1, 0);
        for(int i=1;i<=n;i++){
            int rk = int(lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin()) + 1;
            root[i] = update(root[i-1], 1, V, rk);
        }
    }

    // 对外接口：查询 [L,R] 的第 k 小的“原值”
    int range_kth(int L, int R, int k){
        int rk = kth(root[R], root[L-1], 1, V, k);
        return vals[rk-1];
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,q; 
    if(!(cin>>n>>q)) return 0;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];

    PST pst;
    pst.build_all(a);

    while(q--){
        int L,R,k; cin>>L>>R>>k;
        cout << pst.range_kth(L,R,k) << "\n";
    }
    return 0;
}

动态修改查区间 k-th

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using ll = long long;
using pii = pair<ll,int>;
using namespace __gnu_pbds;

// 有序统计树（支持 order_of_key / find_by_order）
template<class T>
using ost = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct KthBIT {
    int n;
    vector<ost<pii>> bit; // BIT 的每个节点是一个有序统计树
    vector<ll> A;         // 当前数组（1-based）
    vector<ll> vals;      // 离线收集的所有可能值（离散后用于二分 kth）

    KthBIT(int n=0){ init(n); }
    void init(int n_){
        n = n_;
        bit.assign(n+1, {});
        A.assign(n+1, 0);
        vals.clear();
    }

    // 在 BIT 上插入/删除 (val, idx)
    void _add_point(int idx, ll val, int delta){ // delta=+1 插入，-1 删除
        for(int x=idx; x<=n; x+=x&-x){
            if(delta>0) bit[x].insert({val, idx});
            else        bit[x].erase ({val, idx});
        }
    }

    // 建树：传入初始数组 a[1..n]，以及（可选）值域 vals_all 用于 kth 二分
    void build(const vector<ll>& a, const vector<ll>& vals_all = {}){
        A = a;
        for(int i=1;i<=n;i++) _add_point(i, A[i], +1);
        if(!vals_all.empty()){
            vals = vals_all;
            sort(vals.begin(), vals.end());
            vals.erase(unique(vals.begin(), vals.end()), vals.end());
        }
    }

    // 点修改：把 A[i] 改为 newV
    void update(int i, ll newV){
        _add_point(i, A[i], -1);
        A[i] = newV;
        _add_point(i, A[i], +1);
    }

    // 前缀 [1..r] 中 ≤ x 的数量
    int _pref_count_le(int r, ll x) const {
        int res = 0;
        for(int y=r; y>0; y-=y&-y){
            // 计算 < (x+1, -INF) 的数量，即 ≤ x
            res += bit[y].order_of_key({x+1, INT_MIN});
        }
        return res;
    }

    // 区间 [L..R] 中 ≤ x 的数量
    int count_le(int L, int R, ll x) const {
        if(L>R) return 0;
        return _pref_count_le(R, x) - _pref_count_le(L-1, x);
    }

    // 区间第 k 小（基于预先准备好的 vals 离散值域进行二分）
    ll kth(int L, int R, int k) const {
        // 假设 1 <= k <= R-L+1
        int lo = 0, hi = (int)vals.size()-1;
        ll ans = vals.back();
        while(lo <= hi){
            int mid = (lo + hi) >> 1;
            ll x = vals[mid];
            if(count_le(L, R, x) >= k){ ans = x; hi = mid-1; }
            else lo = mid+1;
        }
        return ans;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q; cin >> n >> q;
    vector<ll> a(n+1);
    vector<tuple<int,int,ll>> ops; ops.reserve(q); // 记录操作用于离线收集值域
    vector<ll> allvals;

    for(int i=1;i<=n;i++){ cin >> a[i]; allvals.push_back(a[i]); }

    // 读操作：约定 op=1 点改，op=2 区间 kth；你也可以换自己的协议
    // 1 i v   : a[i] = v
    // 2 L R k : 查询 [L,R] 的第 k 小
    vector<tuple<int,int,int,int>> qry; // 保存查询 (L,R,k,id) 如果需要离线输出
    for(int i=0;i<q;i++){
        int op; cin >> op;
        if(op==1){
            int idx; ll v; cin >> idx >> v;
            ops.emplace_back(op, idx, v);
            allvals.push_back(v); // 离线收集可能出现的值
        }else{
            int L,R,k; cin >> L >> R >> k;
            ops.emplace_back(op, (L<<16)|(R&0xFFFF), k); // 简化存储
        }
    }

    // 初始化结构并把离散值域塞进去（用于 kth 的二分）
    KthBIT ds(n);
    ds.build(a, allvals);

    // 在线处理
    for(auto &tp : ops){
        int op = get<0>(tp);
        if(op==1){
            int i = get<1>(tp);
            ll v  = get<2>(tp);
            ds.update(i, v);
        }else{
            int LR = get<1>(tp), k = (int)get<2>(tp);
            int L = LR>>16, R = LR & 0xFFFF;
            cout << ds.kth(L, R, k) << "\n";
        }
    }
    return 0;
}

# 图

基本图构建

# BFS

图的遍历

bfs(s) {
  q = new queue()
  q.push(s), visited[s] = true
  while (!q.empty()) {
    u = q.pop()
    for each edge(u, v) {
      if (!visited[v]) {
        q.push(v)
        visited[v] = true
      }
    }
  }
}

# 01 BFS

# 基本上都是在求最短路时用到，边权有特点：有的边权为 0！边权为 0 的放到队首，多用这样的节点，边权为其他正数（常见为 1）的放到队尾，少用这样的节点。
# 01bfs：O (m) 堆优化 dijkstra：O (mlongn)

# DFS

vector<vector<int>> adj;  // 邻接表
vector<bool> vis;         // 记录节点是否已经遍历

void dfs(const int u) {
  vis[u] = true;
  for (int v : adj[u])
    if (!vis[v]) dfs(v)
}

# AOV 网 - 拓扑排序，AOE

拓扑排序的核心思想就是找入度为 0 的加进来然后把相关的边都删除，又有新叶子
注意只是输出一个拓扑序，不是实际执行序列，如果一个点没有前置依赖那么他就可以在 t=0 执行

int n, m;
vector<int> G[MAXN];
int in[MAXN];  // 存储每个结点的入度

bool toposort() {
  vector<int> L;
  queue<int> S;
  for (int i = 1; i <= n; i++)
    if (in[i] == 0) S.push(i);
  while (!S.empty()) {
    int u = S.front();
    S.pop();
    L.push_back(u);
    for (auto v : G[u]) {
      if (--in[v] == 0) {
        S.push(v);
      }
    }
  }
  if (L.size() == n) {
    for (auto i : L) cout << i << ' ';
    return true;
  }
  return false;
}

// 或者下面留一个可能的拓扑序在一个 topo 里

bool toposort(vector<int>& topo) {
  queue<int> q;
  for (int i = 1; i <= n; i++)
    if (in[i] == 0) q.push(i);   // 入度为 0 的点先入队

  while (!q.empty()) {
    int u = q.front(); q.pop();
    topo.push_back(u);
    for (auto v : G[u]) {
      if (--in[v] == 0) q.push(v);
    }
  }
  return topo.size() == n;
}

如果要字典序输出的话，用最大堆和最小堆

struct TopoSort {
    int n; // 节点数
    vector<vector<int>> g;  // 邻接表
    vector<int> indeg;      // 入度

    TopoSort(int n) : n(n), g(n + 1), indeg(n + 1, 0) {}

    // 添加有向边 u -> v
    void add_edge(int u, int v) {
        g[u].push_back(v);
        indeg[v]++;
    }

    // 返回字典序最小的拓扑序列；如果有环，返回空数组
    vector<int> sort() {
        vector<int> res;
        res.reserve(n);

        // 最小堆：保证每次取到最小编号
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int i = 1; i <= n; i++)
            if (indeg[i] == 0) pq.push(i);

        while (!pq.empty()) {
            int u = pq.top(); pq.pop();
            res.push_back(u);
            for (int v : g[u]) {
                if (--indeg[v] == 0) pq.push(v);
            }
        }

        if ((int)res.size() != n) return {}; // 有环
        return res;
    }
};

AOE 网（Activity On Edge Network) 即边表示活动的网。
计算每个活动的最早开始时间和最晚开始时间。两者相等的活动称为关键活动。
关键路径是指整个工程完成得最长时间，也就是在 AOE 中找最长路。

#include <bits/stdc++.h>
using namespace std;

// 1-based；边权 w 表示活动时长（AOE）
struct Edge { int u, v; long long w; };

struct CriticalPathAOE {
    int n;
    vector<vector<pair<int,int>>> g;   // g[u] -> {(v, edge_id)}
    vector<Edge> E;                    // E[edge_id] = {u,v,w}
    vector<int> indeg;
    vector<int> topo;
    vector<long long> ve, vl;          // 事件最早/最迟发生时间

    explicit CriticalPathAOE(int n)
        : n(n),
          g(n + 1),
          indeg(n + 1, 0),
          ve(n + 1, LLONG_MIN / 4),
          vl(n + 1, LLONG_MAX / 4) {}

    void add_edge(int u, int v, long long w){
        int id = (int)E.size();
        E.push_back({u, v, w});
        g[u].push_back({v, id});
        indeg[v]++;
    }

    bool topo_sort() {
        queue<int> q;
        for (int i = 1; i <= n; i++) {
            if (indeg[i] == 0) { // 多源
                q.push(i);
                ve[i] = 0;       // 源事件最早发生时间设为 0
            }
        }
        topo.clear();
        topo.reserve(n);

        while (!q.empty()) {
            int u = q.front(); q.pop();
            topo.push_back(u);
            for (auto [v, id] : g[u]) {
                ve[v] = max(ve[v], ve[u] + E[id].w); // 正向推 ve
                if (--indeg[v] == 0) q.push(v);
            }
        }
        return (int)topo.size() == n; // 有环则拓扑失败
    }

    // 返回：{总工期，关键活动的 edge_id 列表}
    pair<long long, vector<int>> solve() {
        if (!topo_sort()) return {-1, {}}; // 有环

        long long T = 0;
        // 汇事件（出度为 0）的 ve 最大值即总工期
        for (int i = 1; i <= n; i++) {
            if (g[i].empty()) T = max(T, ve[i]);
        }

        // 逆推 vl：汇事件 vl = T
        for (int i = 1; i <= n; i++) {
            if (g[i].empty()) vl[i] = T;
        }
        for (int k = (int)topo.size() - 1; k >= 0; --k) {
            int u = topo[k];
            for (auto [v, id] : g[u]) {
                vl[u] = min(vl[u], vl[v] - E[id].w);
            }
            // 对仅作为源、无后继且未被设置的点，令 vl[u] = ve[u]
            if (vl[u] == LLONG_MAX / 4) vl[u] = ve[u];
        }

        // 关键活动：e == l
        vector<int> critical_edges;
        for (int id = 0; id < (int)E.size(); id++) {
            int u = E[id].u, v = E[id].v;
            long long w = E[id].w;
            long long e = ve[u];
            long long l = vl[v] - w;
            if (e == l) critical_edges.push_back(id); // 0-based 的边编号
        }
        return {T, critical_edges};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    CriticalPathAOE cp(n);
    for (int i = 0; i < m; i++) {
        int u, v; long long w;
        cin >> u >> v >> w;   // 1-based
        cp.add_edge(u, v, w);
    }

    auto [T, crit] = cp.solve();
    if (T < 0) {
        cout << "Graph has a cycle\n";
        return 0;
    }

    cout << "Project time: " << T << "\n";
    cout << "Critical activities (edge ids 0-based):";
    for (int id : crit) cout << " " << id;
    cout << "\n";

    // 可选：把关键活动的 (u,v,w) 也打印出来
    for (int id : crit) {
        auto e = cp.E[id];
        cout << "(" << e.u << "->" << e.v << ", w=" << e.w << ")\n";
    }

    return 0;
}

# 环检测

下面是无向图的做法
对于负环检测看 Bell-ford
对于有向图检测看强连通分量
环计数看 Johnson

// ---------- 基础：建图 ----------
vector<vector<int>> build_adj(int n, const vector<pair<int,int>>& edges, bool directed = false) {
    vector<vector<int>> adj(n);
    adj.reserve(n);
    for (auto [u, v] : edges) {
        adj[u].push_back(v);
        if (!directed && u != v) adj[v].push_back(u);
    }
    return adj;
}

// ---------- 1) DFS 环检测（无向图） ----------
bool has_cycle_dfs(int n, const vector<pair<int,int>>& edges) {
    auto adj = build_adj(n, edges, /*directed=*/false);
    vector<int> parent(n, -1);
    vector<char> vis(n, 0);

    function<bool(int)> dfs = [&](int u) -> bool {
        vis[u] = 1;
        for (int v : adj[u]) {
            if (!vis[v]) {
                parent[v] = u;
                if (dfs(v)) return true;
            } else if (parent[u] != v) {
                // 遇到已访问且不是父亲节点 => 有环
                return true;
            }
        }
        return false;
    };

    for (int i = 0; i < n; ++i) {
        if (!vis[i] && dfs(i)) return true;
    }
    return false;
}
// 无向图 DSU 加速
bool has_cycle_union_find(int n, const vector<pair<int,int>>& edges) {
    DSU dsu(n);
    for (auto [u, v] : edges) {
        int ru = dsu.find(u), rv = dsu.find(v);
        if (ru == rv) return true;   // 同一集合再连边 => 有环
        dsu.unite(ru, rv);
    }
    return false;
}

// ---------- 3) 独立环个数（cyclomatic number = m - n + k） ----------
int cyclomatic_number(int n, const vector<pair<int,int>>& edges) {
    auto adj = build_adj(n, edges, /*directed=*/false);
    int m = 0;
    for (int i = 0; i < n; ++i) m += (int)adj[i].size();
    m /= 2; // 无向边数

    vector<char> vis(n, 0);
    int k = 0;
    for (int i = 0; i < n; ++i) if (!vis[i]) {
        k++;
        // 迭代 DFS/BFS 统计连通分量
        stack<int> st; st.push(i); vis[i] = 1;
        while (!st.empty()) {
            int u = st.top(); st.pop();
            for (int v : adj[u]) if (!vis[v]) vis[v] = 1, st.push(v);
        }
    }
    return m - n + k;
}

# DAG 有向无环图

能拓扑排序的图，一定是有向无环图；

在 DAG 上用 DP 求最短路 O (n+m)

struct edge {
  int v, w;
};

int n, m;
vector<edge> e[MAXN];
vector<int> L;                               // 存储拓扑排序结果
int max_dis[MAXN], min_dis[MAXN], in[MAXN];  // in 存储每个节点的入度

void toposort() {  // 拓扑排序
  queue<int> S;
  memset(in, 0, sizeof(in));
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < e[i].size(); j++) {
      in[e[i][j].v]++;
    }
  }
  for (int i = 1; i <= n; i++)
    if (in[i] == 0) S.push(i);
  while (!S.empty()) {
    int u = S.front();
    S.pop();
    L.push_back(u);
    for (int i = 0; i < e[u].size(); i++) {
      if (--in[e[u][i].v] == 0) {
        S.push(e[u][i].v);
      }
    }
  }
}

void dp(int s) {  // 以 s 为起点求单源最长（短）路
  toposort();     // 先进行拓扑排序
  memset(min_dis, 0x3f, sizeof(min_dis));
  memset(max_dis, 0, sizeof(max_dis));
  min_dis[s] = 0;
  for (int i = 0; i < L.size(); i++) {
    int u = L[i];
    for (int j = 0; j < e[u].size(); j++) {
      min_dis[e[u][j].v] = min(min_dis[e[u][j].v], min_dis[u] + e[u][j].w);
      max_dis[e[u][j].v] = max(max_dis[e[u][j].v], max_dis[u] + e[u][j].w);
    }
  }
}

# 最短路

# Dijkstra 单源最短

BFS 算法 + 贪心思想
一个点集，视为一个整体，更新其他点的距离（松弛）
然后加入距离最小的到点集
重复 1，2，直到所有点都确定

struct Edge { int to, w; };

struct Dijkstra {
    int n;
    vector<vector<Edge>> g;
    vector<long long> dist;
    vector<bool> vis;
    vector<int> parent;   // 记录前驱

Dijkstra(int n): n(n), g(n+1), dist(n+1, LLONG_MAX), vis(n+1,false), parent(n+1,-1) {}

    void add_edge(int u,int v,int w) {
        g[u].push_back({v,w});
    }

    void run(int s) {
        priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
        dist[s]=0; pq.push({0,s});
        while(!pq.empty()) {
            auto [d,u]=pq.top(); pq.pop();
            if(vis[u]) continue;
            vis[u]=true;
            for(auto [v,w]: g[u]) {
                if(dist[v] > d + w) {
                    dist[v] = d + w;
                    parent[v] = u;     // 记录前驱
                    pq.push({dist[v], v});
                }
            }
        }
    }

    // 从 s 到 t 的最短路径（包含起点和终点）
    vector<int> get_path(int t) {
        vector<int> path;
        if (dist[t] == LLONG_MAX) return path; // 不可达
        for(int v=t; v!=-1; v=parent[v])
            path.push_back(v);
        reverse(path.begin(), path.end());
        return path;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m,s;
    cin >> n >> m >> s;

    Dijkstra dj(n); // n 为源，到所有可达点的最短
    for(int i=0;i<m;i++) {
        int u,v,w; cin>>u>>v>>w;
        dj.add_edge(u,v,w);   // 有向
    }

    dj.run(s);

    // 输出从源点到每个点的最短路和路径
    for(int i=1;i<=n;i++) {
        if(dj.dist[i]==LLONG_MAX) {
            cout << "Node " << i << ": unreachable\n";
        } else {
            cout << "Node " << i << ": dist=" << dj.dist[i] << " path=";
            auto path = dj.get_path(i);
            for(int j=0;j<(int)path.size();j++){
                if(j) cout<<"->";
                cout<<path[j];
            }
            cout<<"\n";
        }
    }
    return 0;
}

# Bellman_ford 单源负权最短

** **O(N * E)
算法的核心思想是对所有边进行松弛 n-1 次操作（n 为节点数量），从而求得目标最短路
注意如果要检测负环，那么进行第 n 次松弛时，发现还可以更新的，那么就是负环了

// Bellman-Ford with path recovery (minimal reusable)
// - 图默认 1..n 编号
// - 有向图；若是无向图请对每条边 add 两次 (u->v, v->u)
// - 返回：true=无可达负环；false=存在从 s 可达的负环
// - dist[v] = INF 表示不可达
// - 用 pre[] 反向回溯恢复路径
#include <bits/stdc++.h>
using namespace std;

struct Edge { int u, v; long long w; };

const long long INF = (1LL<<62);

bool bellman_ford(int n, int s, const vector<Edge>& edges,
                  vector<long long>& dist, vector<int>& pre) {
    dist.assign(n + 1, INF);
    pre.assign(n + 1, -1);
    dist[s] = 0;

    // 进行 n-1 轮松弛
    for (int i = 1; i <= n - 1; ++i) {
        bool any = false;
        for (const auto& e : edges) {
            if (dist[e.u] == INF) continue;
            if (dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
                pre[e.v] = e.u;
                any = true;
            }
        }
        if (!any) break; // 提前退出
    }

    // 第 n 轮检测是否仍能松弛（是否存在从 s 可达的负环）
    for (const auto& e : edges) {
        if (dist[e.u] == INF) continue;
        if (dist[e.u] + e.w < dist[e.v]) {
            return false; // 有可达负环
        }
    }
    return true;
}

// 从 s 到 t 的最短路径（若不可达返回空向量）
vector<int> get_path(int s, int t, const vector<int>& pre) {
    vector<int> path;
    if (t < 0 || t >= (int)pre.size()) return path;
    if (pre[t] == -1 && s != t) return path; // 不可达（且不是 s 自身）
    for (int v = t; v != -1; v = pre[v]) path.push_back(v);
    reverse(path.begin(), path.end());
    if (!path.empty() && path.front() == s) return path;
    return {}; // 保险：首点不是 s 则判为不可达
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s; 
    cin >> n >> m >> s;

    vector<Edge> edges;
    edges.reserve(m);
    for (int i = 0; i < m; ++i) {
        int u, v; long long w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
        // 无向图：再加一条 edges.push_back({v, u, w});
    }

    vector<long long> dist;
    vector<int> pre;
    bool ok = bellman_ford(n, s, edges, dist, pre);

    int t; cin >> t; // 想查询的终点
    if (dist[t] == INF) {
        cout << "No path\n";
        return 0;
    }
    if (!ok) {
        // 存在从 s 可达的负环：最短路不良定义，下面仍可给出一次回溯的“某条路”
        // 但严格来说不应报告为最短路，视题意处理。
        cout << "Negative cycle reachable from source\n";
    }

    auto path = get_path(s, t, pre);
    for (int v : path) cout << v << (v==t?'\n':' ');
    cout << "dist=" << dist[t] << "\n";
}

SFPA, 用队列来优化，但不稳定，适合稀疏图

bool spfa(int n, int s, const vector<Edge>& edges,
          vector<long long>& dist, vector<int>& pre) {
    // 建邻接表（在保持 Edge 数组输入不变的前提下，内部一次性构建）
    vector<vector<pair<int,long long>>> adj(n + 1);
    adj.reserve(n + 1);
    for (const auto& e : edges) adj[e.u].push_back({e.v, e.w});

    dist.assign(n + 1, INF);
    pre.assign(n + 1, -1);
    vector<int> cnt(n + 1, 0);     // 入队次数
    vector<char> inq(n + 1, 0);    // 是否在队列中

    queue<int> q;
    dist[s] = 0;
    q.push(s);
    inq[s] = 1;
    cnt[s] = 1;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = 0;

        for (auto &p : adj[u]) {
            int v = p.first;
            long long w = p.second;
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pre[v] = u;
                if (!inq[v]) {
                    q.push(v);
                    inq[v] = 1;
                    if (++cnt[v] > n) {
                        // 从 s 可达的负环
                        return false;
                    }
                }
            }
        }
    }
    return true; // 无从 s 可达的负环
}

// 从 s 到 t 的最短路径（若不可达返回空向量）
vector<int> get_path(int s, int t, const vector<int>& pre) {
    vector<int> path;
    if (t < 0 || t >= (int)pre.size()) return path;
    if (pre[t] == -1 && s != t) return path; // 不可达（且不是 s 自身）
    for (int v = t; v != -1; v = pre[v]) path.push_back(v);
    reverse(path.begin(), path.end());
    if (!path.empty() && path.front() == s) return path;
    return {}; // 保险：首点不是 s 则判为不可达
}

# 单源有限最短路

限制最多经过 k 个 (不算起点终点) 城市，也就是最多 k+1 条边，对于 BF 算法，进行 k+1 次松弛就可
但是一定要注意，对于 dist [] 数组，每次要复制，不能在同一层中使用别人已经更新过的来计算
** 第 **i** 轮松弛应该只允许用 “恰好 ≤ i 条边” 的路径信息 **

// - 图编号 1..n
// - 有向图；无向图请双向加边
// - 约束：路径最多使用 K+1 条边（中间最多 K 个城市）
// - 通过双数组实现“层次化松弛”，避免同层传递
// - 返回 dist, pre；用 get_path(s,t,pre) 恢复路径
// - INF 表示不可达

#include <bits/stdc++.h>
using namespace std;

struct Edge { int u, v; long long w; };
const long long INF = (1LL<<62);

// 进行“至多 K+1 条边”的层次化 Bellman-Ford
// 输出：dist, pre（pre[v] 为到达 v 的前驱；不可达保持 -1）
void limited_bf_with_path(int n, int s, const vector<Edge>& edges, int K,
                          vector<long long>& dist, vector<int>& pre) {
    vector<long long> dist_old(n+1, INF), dist_new(n+1, INF);
    vector<int> pre_old(n+1, -1), pre_new(n+1, -1);

    dist_old[s] = 0;
    pre_old[s]  = -1;

    // 逐层扩展，每层增加 1 条可用边，最多 K+1 条边
    for (int i = 1; i <= K + 1; ++i) {
        dist_new = dist_old;   // 关键：先复制，防止同层再传递
        pre_new  = pre_old;

        for (const auto& e : edges) {
            if (dist_old[e.u] == INF) continue;                // 上一层不可达
            long long cand = dist_old[e.u] + e.w;              // 只能用上一层的值
            if (cand < dist_new[e.v]) {
                dist_new[e.v] = cand;
                pre_new[e.v]  = e.u;                           // 记录前驱（来自上一层）
            }
        }
        dist_old.swap(dist_new);
        pre_old.swap(pre_new);
    }

    dist = move(dist_old);
    pre  = move(pre_old);
}

// 从 s 到 t 恢复路径（若不可达返回空向量）
vector<int> get_path(int s, int t, const vector<int>& pre) {
    vector<int> path;
    if (t < 0 || t >= (int)pre.size()) return path;
    if (s == t) return {s};
    if (pre[t] == -1) return path;                 // 不可达
    for (int v = t; v != -1; v = pre[v]) path.push_back(v);
    reverse(path.begin(), path.end());
    if (!path.empty() && path.front() == s) return path;
    return {};                                     // 保险：首点不是 s 则判不可达
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  
    int n, m, s, t, K;
    // 输入：n 点，m 边，起点 s, 终点 t, 中转城市上限 K（即最多 K+1 条边）
    // 例：n m s t K
    //     m 行：u v w
    if (!(cin >> n >> m >> s >> t >> K)) return 0;

    vector<Edge> edges;
    edges.reserve(m);
    for (int i = 0; i < m; ++i) {
        int u, v; long long w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
        // 无向图：edges.push_back({v, u, w});
    }

    vector<long long> dist;
    vector<int> pre;
    limited_bf_with_path(n, s, edges, K, dist, pre);

    if (t < 1 || t > n || dist[t] == INF) {
        cout << "No path within " << (K+1) << " edges\n";
        return 0;
    }

    auto path = get_path(s, t, pre);

    // 输出路径与距离
    for (int i = 0; i < (int)path.size(); ++i) {
        cout << path[i] << (i + 1 == (int)path.size() ? '\n' : ' ');
    }
    cout << "dist=" << dist[t] << "\n";

    // 如果你想核对“边数是否不超过 K+1”
    // 可检查： (int)path.size() - 1 <= K + 1
    return 0;
}

# 单源最小瓶颈路

最小化路径 “最大边权” 的问题

/*
时间复杂度：O(n^2 log n)
空间复杂度：O(n + m)
适用：寻找路径中"最大边权"最小的路径
*/
#include <vector>
#include <queue>
#include <limits>
using namespace std;

int minimaxPath(const vector<vector<int>>& graph, int start, int end) {
    int n = graph.size() - 1;
    const int INF = INT_MAX / 2;
  
    // 从邻接矩阵构建邻接表
    vector<vector<pair<int,int>>> g(n + 1);
    for (int u = 1; u <= n; ++u) {
        for (int v = 1; v <= n; ++v) {
            if (graph[u][v] != 0) {
                g[u].push_back({v, graph[u][v]});
                g[v].push_back({u, graph[u][v]}); // 无向图
            }
        }
    }
  
    vector<int> bottleneck(n + 1, INF);
    using P = pair<int,int>;
    priority_queue<P, vector<P>, greater<P>> pq;
  
    bottleneck[start] = 0;
    pq.push({0, start});
  
    while (!pq.empty()) {
        auto [maxEdge, u] = pq.top(); pq.pop();
        if (maxEdge != bottleneck[u]) continue;
        if (u == end) break;
      
        for (auto [v, w] : g[u]) {
            int newBottleneck = max(maxEdge, w);
            if (newBottleneck < bottleneck[v]) {
                bottleneck[v] = newBottleneck;
                pq.push({newBottleneck, v});
            }
        }
    }
  
    return (bottleneck[end] >= INF) ? INT_MAX : bottleneck[end];
}

# 多源最短路 Floyd

多个起点到多个终点的多条最短路径：
无负权，跑 n 次 dijkstra
有负权，没有负环，图稀疏，n<1e3, m < 1e5, Johnson (nelogn)
将负权图转化为正权图。
我们新建一个虚拟节点（在这里我们就设它的编号为 0）。从这个点向其他所有点连一条边权为 0 的边。
接下来用 Bellman-Ford 算法求出从 0 号点到其他所有点的最短路，记为 h_i。
假如存在一条从 u 点到 v 点，边权为 w 的边，则我们将该边的边权重新设置为 w + h_u - h_v。
接下来以每个点为起点，跑 n 轮 Dijkstra 算法即可求出任意两点间的最短路了。

// - 结点编号：1..n
// - 有向图；无向图请双向加边
// - 允许负权边；若存在负环则返回 false
// - 输出：dist[i][j] 为 i->j 的最短路；不可达为 INF
// - 复杂度：BF O(n*m) + n 次 Dijkstra O(n*m log n)（稀疏图优选）
//

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = (1LL << 62);

struct Edge {
    int u, v; ll w;
};

struct Johnson {
    int n;
    vector<Edge> edges;

    explicit Johnson(int n): n(n) {}

    inline void addEdge(int u, int v, ll w) {
        edges.push_back({u, v, w});
    }

    // 运行 Johnson
    // 返回 false 表示存在负环；true 表示 dist 填好
    bool run(vector<vector<ll>>& dist) {
        // 1) Bellman-Ford 求势能 h（虚拟源 0 -> 所有点 0 权边的等价做法：将 d[] 初始为 0）
        vector<ll> h(n + 1, 0);
        if (!bellmanFordPotential(h)) return false;  // 负环

        // 2) 重标权：w' = w + h[u] - h[v]  (保证非负)
        vector<vector<pair<int, ll>>> adj(n + 1);
        adj.assign(n + 1, {});
        adj.reserve(n + 1);
        for (const auto& e : edges) {
            ll wprime = e.w + h[e.u] - h[e.v];
            // wprime 应 >= 0
            adj[e.u].push_back({e.v, wprime});
        }

        // 3) n 次 Dijkstra（在重标图上），并还原原图距离
        dist.assign(n + 1, vector<ll>(n + 1, INF));
        vector<ll> drow(n + 1);
        for (int s = 1; s <= n; ++s) {
            dijkstra(s, adj, drow);
            for (int v = 1; v <= n; ++v) {
                if (drow[v] < INF/2) {
                    dist[s][v] = drow[v] + h[v] - h[s];  // 还原
                }
            }
        }
        return true;
    }

private:
    // Bellman-Ford 势能：等价于在超级源 0（到所有点 0 权）下的最短路
    bool bellmanFordPotential(vector<ll>& h) {
        vector<ll> d(n + 1, 0); // 全 0 初始化 == 超级源 0 连到所有点的效果
        for (int it = 1; it <= n; ++it) {
            bool any = false;
            for (const auto& e : edges) {
                if (d[e.u] + e.w < d[e.v]) {
                    d[e.v] = d[e.u] + e.w;
                    any = true;
                }
            }
            if (!any) break;
        }
        // 第 n+1 轮检查负环
        for (const auto& e : edges) {
            if (d[e.u] + e.w < d[e.v]) return false; // 存在可达负环
        }
        h = move(d);
        return true;
    }

    // 堆 Dijkstra（重标后非负）
    void dijkstra(int s, const vector<vector<pair<int, ll>>>& adj, vector<ll>& dist) {
        dist.assign(n + 1, INF);
        priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
        dist[s] = 0;
        pq.push({0, s});
        while (!pq.empty()) {
            auto [du, u] = pq.top(); pq.pop();
            if (du != dist[u]) continue;
            for (auto [v, w] : adj[u]) {
                if (dist[v] > du + w) {
                    dist[v] = du + w;
                    pq.push({dist[v], v});
                }
            }
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    Johnson J(n);
    for (int i = 0; i < m; ++i) {
        int u, v; ll w;
        cin >> u >> v >> w;
        J.addEdge(u, v, w);
    }

    vector<vector<ll>> dist;
    if (!J.run(dist)) {
        cout << "Negative cycle\n";
        return 0;
    }

    // 示例：回答若干查询（s, t）
    int q; 
    if (cin >> q) {
        while (q--) {
            int s, t; cin >> s >> t;
            ll ans = dist[s][t];
            cout << (ans >= INF/2 ? -1 : ans) << "\n";
        }
    } else {
        // 或者直接打印整张距离矩阵：
        // for (int i = 1; i <= n; ++i) {
        //     for (int j = 1; j <= n; ++j) {
        //         cout << (dist[i][j] >= INF/2 ? -1 : dist[i][j]) << (j==n?'\n':' ');
        //     }
        // }
    }
    return 0;
}

稠密图，且 n 小于 1000 左右，Floyd O (n^3):
动态规划思想
grid [i][j][k] = m，表示 节点 i 到节点 j 以 [1...k] 集合中的一个节点为中间节点的最短距离为 m
递推公式：
节点 i 到节点 j 的最短路径经过节点 k
节点 i 到节点 j 的最短路径不经过节点 k
对于第一种情况， grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]
第二种情况， grid[i][j][k] = grid[i][j][k - 1]
但实际上，我们可以省略一维度， grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j])

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    const long long INF = (1LL<<60);
    vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF));
    vector<vector<int>> nxt(n + 1, vector<int>(n + 1, -1));

    // 自环距离为 0
    for (int i = 1; i <= n; ++i) {
        dist[i][i] = 0;
        nxt[i][i] = i; // 恢复 i->i 时用得到（可选）
    }

    // 读入无向边
    for (int i = 0; i < m; ++i) {
        int u, v; long long w;
        cin >> u >> v >> w;
        if (w < dist[u][v]) {              // 若有重边取更小
            dist[u][v] = dist[v][u] = w;
            nxt[u][v] = v;
            nxt[v][u] = u;
        }
    }

    // Floyd–Warshall with path reconstruction
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            if (dist[i][k] == INF) continue;
            for (int j = 1; j <= n; ++j) {
                if (dist[k][j] == INF) continue;
                long long cand = dist[i][k] + dist[k][j];
                if (cand < dist[i][j]) {
                    dist[i][j] = cand;
                    nxt[i][j]  = nxt[i][k];  // 关键：第一跳来自 i->k 的第一跳
                }
            }
        }
    }

    // 查询：既返回距离也能打印路径
    int q;
    cin >> q;
    while (q--) {
        int s, t;
        cin >> s >> t;

        if (dist[s][t] >= INF || nxt[s][t] == -1) {
            cout << -1 << "\n";  // 距离不可达
            continue;
        }

        // 还想要路径的话：
        vector<int> path;
        int cur = s;
        path.push_back(cur);
        // 防御：最多走 n 步避免意外环
        for (int step = 0; cur != t && step <= n; ++step) {
            cur = nxt[cur][t];
            if (cur == -1) break;
            path.push_back(cur);
        }

        // 输出距离
        cout << dist[s][t] << "\n";

        // 如需打印路径，取消注释：
        // for (int i = 0; i < (int)path.size(); ++i) {
        //     cout << path[i] << (i + 1 == (int)path.size() ? '\n' : ' ');
        // }
    }

    return 0;
}

# A_star 启发式算法

利用启发式函数，让 BFS 寻路中优先选择终点方向的点。
下面只是一个示例，可以解决方格图，两点的寻路

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
int moves[1001][1001];
int dir[8][2]={-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};
int b1, b2;
// F = G + H
// G = 从起点到该节点路径消耗
// H = 该节点到终点的预估消耗

struct Knight{
    int x,y;
    int g,h,f;
    bool operator < (const Knight & k) const{  // 重载运算符，从小到大排序
     return k.f < f;
    }
};

priority_queue<Knight> que;

int Heuristic(const Knight& k) { // 欧拉距离
    return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2); // 统一不开根号，这样可以提高精度
}
void astar(const Knight& k)
{
    Knight cur, next;
	que.push(k);
	while(!que.empty())
	{
		cur=que.top(); que.pop();
		if(cur.x == b1 && cur.y == b2)
		break;
		for(int i = 0; i < 8; i++)
		{
			next.x = cur.x + dir[i][0];
			next.y = cur.y + dir[i][1];
			if(next.x < 1 || next.x > 1000 || next.y < 1 || next.y > 1000)
			continue;
			if(!moves[next.x][next.y])
			{
				moves[next.x][next.y] = moves[cur.x][cur.y] + 1;

                // 开始计算 F
				next.g = cur.g + 5; // 统一不开根号，这样可以提高精度，马走日，1 * 1 + 2 * 2 = 5
                next.h = Heuristic(next);
                next.f = next.g + next.h;
                que.push(next);
			}
		}
	}
}

int main()
{
    int n, a1, a2;
    cin >> n;
    while (n--) {
        cin >> a1 >> a2 >> b1 >> b2;
        memset(moves,0,sizeof(moves));
        Knight start;
        start.x = a1;
        start.y = a2;
        start.g = 0;
        start.h = Heuristic(start);
        start.f = start.g + start.h;
		astar(start);
        while(!que.empty()) que.pop(); // 队列清空
		cout << moves[b1][b2] << endl;
	}
	return 0;
}

# 差分系统

x_i - x_j ≤ c → 加边 j → i 、权重 c
x_i - x_j ≥ c → 等价 x_j - x_i ≤ -c → 加边 i → j 、权重 -c
x_i = x_j → 两条边： j → i (0) 与 i → j (0)
乘法： x_i / x_j ≤ c → 取对数： log x_i - log x_j ≤ log c 再按上面处理（注意 x_i>0 ）
那么整个系统是否有解就是看存不存在负环，有负环那就无解了。
注意区分拓扑排序，拓扑排序不允许有环，这个可以有正环。

// - 变量编号：1..n；额外使用 0 号点表示常量 0
// - 统一把约束写成 x_v <= x_u + w 形式：用一条有向边 u -> v (w)
// - solve()：有解返回 true，并在 x[0..n] 给出一组可行解（x[0]=0）；无解 (负环) 返回 false
// - 复杂度：O(n*m)；若要更快可改成 SPFA，但 BF 更稳

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = (1LL << 60);

struct Edge { int u, v; ll w; }; // 表示 x[v] <= x[u] + w

struct DiffConstraints {
    int n;                  // 变量个数（不含 0）
    vector<Edge> es;

    explicit DiffConstraints(int n): n(n) {}

    // x_i - x_j <= c   →  j -> i (c)
    void add_le(int i, int j, ll c) { es.push_back({j, i, c}); }

    // x_i - x_j >= c   →  i -> j (-c)
    void add_ge(int i, int j, ll c) { es.push_back({i, j, -c}); }

    // x_i == x_j       →  两条 0 边
    void add_eq(int i, int j) { add_le(i, j, 0); add_le(j, i, 0); }

    // 绝对上界/下界（用 0 当常量 0）
    // x_i <= U         →  0 -> i (U)
    void add_upper(int i, ll U) { es.push_back({0, i, U}); }
    // x_i >= L         →  i -> 0 (-L)
    void add_lower(int i, ll L) { es.push_back({i, 0, -L}); }

    // 求解（Bellman–Ford）。返回：是否可行；若可行，x 为一组解
    bool solve(vector<ll>& x) {
        int V = n + 1;                 // 顶点 0..n
        vector<ll> dist(V, 0);         // 关键：全 0 初始化 == 超级源连 0 权边到所有点
        for (int it = 1; it <= V - 1; ++it) {
            bool any = false;
            for (const auto& e : es) {
                if (dist[e.v] > dist[e.u] + e.w) {
                    dist[e.v] = dist[e.u] + e.w;
                    any = true;
                }
            }
            if (!any) break;
        }
        // 第 V 轮检测负环：可达负环 ⇒ 无解
        for (const auto& e : es) {
            if (dist[e.v] > dist[e.u] + e.w) return false;
        }
        x = move(dist);
        return true;
    }
};

// 输入：n m；接着 m 行，每行 (type a b c)
// type=1: x_a - x_b <= c
// type=2: x_a - x_b >= c
// type=3: x_a == x_b（c 可忽略）
// 需要额外“绝对上/下界”时，可自行调用 add_upper/add_lower。
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; 
    if (!(cin >> n >> m)) return 0;

    DiffConstraints dc(n);
    while (m--) {
        int type, a, b; long long c;
        cin >> type >> a >> b >> c;
        if (type == 1) dc.add_le(a, b, c);
        else if (type == 2) dc.add_ge(a, b, c);
        else if (type == 3) dc.add_eq(a, b);
    }

    vector<long long> x;
    if (!dc.solve(x)) {
        cout << "No\n";      // 无解（存在负环）
    } else {
        cout << "Yes\n";
        // 一组可行解（可整体平移，不唯一）。如需输出：
        // for (int i = 1; i <= n; ++i) cout << x[i] << (i==n?'\n':' ');
    }
    return 0;
}

# 最短环

给出一个图，问其中的由 n 个节点构成的边权和最小的环是多大。

// 图的点数为 n
int val[MAXN + 1][MAXN + 1];  // 原图的邻接矩阵
int cnt, path[MAXN + 5];      // 记录最小环的路径和长度

void get_path(int u, int v) {  // 获得 u 到 v 之间的路径
  if (pos[u][v] == 0) return;

  int k = pos[u][v];
  get_path(u, k);
  path[++cnt] = k;
  get_path(k, v);
}

void Floyd(const int &n) {
  static int dis[MAXN + 1][MAXN + 1];  // 最短路矩阵
  static int pos[MAXN + 1][MAXN + 1];
  memcpy(dis, val, sizeof(val));
  memset(pos, 0, sizeof(pos));
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; i < k; ++i)
      for (int j = 1; j < i; ++j)
        if (ans >
            (long long)val[i][k] + val[k][j] + dis[i][j]) {  // 发现了更短的环
          // 由于这里保证了 j<i<k，所以三个点不同，不会出现零环。
          ans = val[i][k] + val[k][j] + dis[i][j], cnt = 0;
          path[++cnt] = i, path[++cnt] = k,
          path[++cnt] = j;  // 依次加入 i,k,j 三点
          get_path(j, i);   // 加入 j 到 i 的路径
        }

    for (int i = 1; i <= n; ++i)  // 正常 Floyd 更新最短路
      for (int j = 1; j <= n; ++j) {
        if (dis[i][j] > dis[i][k] + dis[k][j]) {
          dis[i][j] = dis[i][k] + dis[k][j];
          pos[i][j] = k;  // 当前路径可以由 k 更新得到
        }
      }
  }
}

# k 短路

# MST 最小生成树

我们定义无向连通图的 最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树

# Kruskal 加边（mlogm）

该算法的基本思想是从小到大加入边，是个贪心算法
抽象一点地说，维护一堆集合，查询两个元素是否属于同一集合，合并两个集合。
其中，查询两点是否连通和连接两点可以使用并查集维护

struct DSU{};
struct Edge{
    int u, v;
    long long w;
    bool operator<(const Edge& other) const { return w < other.w; } // 升序=最小生成树
};

// Kruskal：n 个点（1..n），edges 为无向边（u,v,w）
// 选中的边写入 picked；返回总权值；图不连通返回 -1
long long kruskal(int n, vector<Edge> edges, vector<Edge>& picked){
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    picked.clear();
    picked.reserve(n-1);
    long long sum = 0;
    for (const auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            sum += e.w;
            picked.push_back(e);
            if ((int)picked.size() == n - 1) break;
        }
    }
    if ((int)picked.size() != n - 1) { picked.clear(); return -1; }
    return sum;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; 
    cin >> n >> m;
    vector<Edge> es(m);
    for (int i=0;i<m;++i) cin >> es[i].u >> es[i].v >> es[i].w;

    vector<Edge> picked;
    long long ans = kruskal(n, es, picked);
    if (ans < 0) { cout << "Impossible\n"; return 0; }

    cout << ans << "\n";                // MST 总权值
    // 打印树的边（u v w）
    for (auto &e : picked) cout << e.u << " " << e.v << " " << e.w << "\n";
    return 0;
}

# Prim 加点（稠密图）

类似于 Dijkstra，判断最终是不是所有点都在了

struct Adj { int v; ll w; };              // 邻接表里的边
// g[u] 是 u 的邻接边集合：vector<vector<Adj>> g(n+1)

struct Cand { ll w; int u, parent; };     // 候选边（准备接入的点 u 通过 parent 接入，权 w）
struct Cmp { bool operator()(const Cand& a, const Cand& b) const { return a.w > b.w; } };

// 输入：n、图 g、root
// 输出：picked 为 MST 边；返回总权值；不连通返回 -1
ll prim_heap(int n, const vector<vector<Adj>>& g, vector<Edge>& picked, int root=1){
    vector<char> vis(n+1, 0);
    priority_queue<Cand, vector<Cand>, Cmp> pq;
    picked.clear(); picked.reserve(n-1);

    pq.push({0, root, 0});
    ll total = 0; int got = 0;

    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        int u = cur.u;
        if (vis[u]) continue;
        vis[u] = 1; ++got;

        if (cur.parent != 0) { // 接入树
            total += cur.w;
            picked.push_back({cur.parent, u, cur.w});
        }
        for (auto e : g[u]) if (!vis[e.v]) pq.push({e.w, e.v, u});
    }
    if (got != n) { picked.clear(); return -1; }
    return total;
}


// 复杂度 O(n^2 + m) 暴力在稠密图有奇效
ll prim_bruteforce(int n, const vector<vector<Adj>>& g, vector<Edge>& picked, int root=1){
    const ll INF = (1LL<<62);
    vector<ll>  dis(n+1, INF);
    vector<int> par(n+1, 0);
    vector<char> vis(n+1, 0);
    picked.clear(); picked.reserve(n-1);

    dis[root] = 0;
    ll total = 0;

    for (int it = 1; it <= n; ++it) {
        int u = -1; ll best = INF;
        for (int v = 1; v <= n; ++v) if (!vis[v] && dis[v] < best) { best = dis[v]; u = v; }
        if (u == -1 || best == INF) { picked.clear(); return -1; } // 不连通
        vis[u] = 1; total += dis[u];
        if (par[u] != 0) picked.push_back({par[u], u, dis[u]});
        for (auto e : g[u]) if (!vis[e.v] && e.w < dis[e.v]) { dis[e.v] = e.w; par[e.v] = u; }
    }
    return total;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;
    vector<Edge> es(m);
    vector<vector<Adj>> g(n+1);
    for (int i=0;i<m;++i){
        int u,v; ll w; cin >> u >> v >> w;
        g[u].push_back({v,w});           // 给 Prim
        g[v].push_back({u,w});
    }

    vector<Edge> picked;

    // 1) Prim（堆）
    // ll ans = prim_heap(n, g, picked, 1);

    // 2) Prim（暴力）
    ll ans = prim_bruteforce(n, g, picked, 1);

    if (ans < 0) { cout << "No MST.\n"; return 0; }
    cout << ans << "\n";
    for (auto &e : picked) cout << e.u << " " << e.v << " " << e.w << "\n";
    return 0;
}

# MST 个数

基尔霍夫 (kirchhoff) 矩阵树定理
给 n 个点 m 条边的图，求该图的 MST 个数

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007LL;

struct DSU{
    vector<int> p,r;
    DSU(int n=0):p(n+1),r(n+1,0){ iota(p.begin(),p.end(),0); }
    int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
    void unite(int a,int b){
        a=find(a); b=find(b); if(a==b) return;
        if(r[a]<r[b]) swap(a,b);
        p[b]=a; if(r[a]==r[b]) r[a]++;
    }
};

struct Edge{ int u,v; ll w; };
bool operator<(const Edge& a, const Edge& b){ return a.w < b.w; }

static inline ll mod_pow(ll a, ll e){
    ll r=1%MOD; a%=MOD;
    while(e){ if(e&1) r=r*a%MOD; a=a*a%MOD; e>>=1; }
    return r;
}
static inline ll mod_inv(ll x){ return mod_pow((x%MOD+MOD)%MOD, MOD-2); } // MOD 为素数

// 高斯消元求行列式（模数为素数）
ll det_mod(vector<vector<ll>> a){
    int n = (int)a.size();
    ll res = 1;
    for(int i=0;i<n;i++){
        int piv = i;
        for(int r=i;r<n;r++) if(a[r][i]%MOD) { piv=r; break; }
        if(a[piv][i]%MOD==0) return 0;          // 奇异
        if(piv!=i){ swap(a[piv], a[i]); res = (MOD - res)%MOD; } // 交换行 → 乘以 -1
        ll inv = mod_inv(a[i][i]);
        res = res * (a[i][i]%MOD+MOD)%MOD;
        for(int r=i+1;r<n;r++){
            if(a[r][i]%MOD==0) continue;
            ll f = a[r][i]%MOD * inv % MOD;
            for(int c=i;c<n;c++){
                a[r][c] = (a[r][c] - f * a[i][c]) % MOD;
            }
        }
    }
    return (res%MOD+MOD)%MOD;
}

// 统计 MST 个数（若图不连通则返回 0）
// 同时可顺手算 MST 的权值（如需，可在 Kruskal 那里累加最小权，不影响计数）
ll count_MST(int n, vector<Edge> es){
    sort(es.begin(), es.end());
    DSU dsu(n);
    ll ways = 1;

    for (int i = 0; i < (int)es.size(); ){
        int j = i;
        while (j < (int)es.size() && es[j].w == es[i].w) ++j; // [i, j) 为同权组

        // 1) 只保留连接“当前不同并查集块”的边，并把块映射到 0..K-1
        unordered_map<int,int> id; id.reserve((j-i)*2);
        vector<pair<int,int>> pairs; pairs.reserve(j-i);
        for (int k=i; k<j; ++k){
            int a = dsu.find(es[k].u), b = dsu.find(es[k].v);
            if (a==b) continue;
            if (!id.count(a)) id[a] = (int)id.size();
            if (!id.count(b)) id[b] = (int)id.size();
            pairs.push_back({ id[a], id[b] });
        }

        int K = (int)id.size();
        if (K > 0){
            // 2) 用这些边在 K 个点上建多重图的拉普拉斯矩阵
            vector<vector<ll>> L(K, vector<ll>(K, 0));
            vector<vector<int>> adj(K);
            for (auto [x,y] : pairs){
                L[x][x]++; L[y][y]++;
                L[x][y]--; L[y][x]--;
                adj[x].push_back(y); adj[y].push_back(x);
            }

            // 3) 分解为连通分量；对每个分量用 Kirchhoff 求生成树数，累计乘积
            vector<int> comp(K, -1);
            for (int s=0; s<K; ++s) if (comp[s]==-1){
                // BFS 抓一个分量
                vector<int> nodes;
                queue<int> q; q.push(s); comp[s]=1;
                while(!q.empty()){
                    int u=q.front(); q.pop();
                    nodes.push_back(u);
                    for(int v: adj[u]) if(comp[v]==-1){ comp[v]=1; q.push(v); }
                }
                int S = (int)nodes.size();
                if (S >= 2){
                    // 取 (S-1)x(S-1) 的任意主子式（这里去掉最后一行一列）
                    vector<vector<ll>> A(S-1, vector<ll>(S-1, 0));
                    for (int r=0; r<S-1; ++r)
                        for (int c=0; c<S-1; ++c)
                            A[r][c] = (L[nodes[r]][nodes[c]]%MOD+MOD)%MOD;
                    ll add = det_mod(A);
                    ways = ways * add % MOD;
                }
                // S==1 时该分量只有一个点，贡献因子为 1
            }
        }

        // 4) 把这一权值组的边全部并起来（把分量收缩，供下一组使用）
        for (int k=i; k<j; ++k) dsu.unite(es[k].u, es[k].v);
        i = j;
    }

    // 最后检查是否整体连通：不连通则没有 MST
    int root = dsu.find(1);
    for (int v=2; v<=n; ++v) if (dsu.find(v)!=root) return 0;
    return (ways%MOD+MOD)%MOD;
}

/* 用法示例
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m; cin>>n>>m;
    vector<Edge> es(m);
    for(int i=0;i<m;++i) cin>>es[i].u>>es[i].v>>es[i].w;

    cout << count_MST(n, es) << "\n"; // MST 个数（mod 1e9+7）
    return 0;
}
*/

# 最小斯坦纳树，连接 k 个点

要花费最小的代价，连通给定的 k 个关键点，这是一个组合优化问题
允许引入新的点，但是要把 k 个点连起来

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Edge { int to; ll w; };

const ll INF = (1LL<<60);

// n: 点数 (1..n)
// g: 无向图邻接表
// key: 关键点编号（大小 k）
ll steiner_tree(int n, const vector<vector<Edge>>& g, const vector<int>& key) {
    int k = (int)key.size();
    int FULL = (1<<k) - 1;

    // 映射关键点 -> 位
    vector<int> id(n+1, -1);
    for (int j = 0; j < k; ++j) id[key[j]] = j;

    // dp[i][S]: 以 i 为根连通 S 的最小代价
    vector<vector<ll>> dp(n+1, vector<ll>(1<<k, INF));

    // 初始化：关键点自身的单点集合
    for (int j = 0; j < k; ++j) dp[key[j]][1<<j] = 0;

    // 枚举所有非空子集
    for (int S = 1; S <= FULL; ++S) {
        // 1) 在同一根 i 上合并子集（S 的真子集 T）
        for (int i = 1; i <= n; ++i) {
            // 枚举 S 的真子集 T（T != 0 && T != S），允许重复考虑，取 min 即可
            // T = (T-1) & S 是经典子集枚举
            for (int T = (S-1)&S; T; T = (T-1)&S) {
                dp[i][S] = min(dp[i][S], dp[i][T] + dp[i][S^T]);
            }
        }

        // 2) 固定 S，做一遍「多源 Dijkstra」传播到整图
        priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
        for (int i = 1; i <= n; ++i) {
            if (dp[i][S] < INF) pq.emplace(dp[i][S], i);
        }
        while (!pq.empty()) {
            auto [du, u] = pq.top(); pq.pop();
            if (du != dp[u][S]) continue; // 过期
            for (auto e : g[u]) {
                if (dp[e.to][S] > du + e.w) {
                    dp[e.to][S] = du + e.w;
                    pq.emplace(dp[e.to][S], e.to);
                }
            }
        }
    }

    // 答案：min_i dp[i][FULL]
    ll ans = INF;
    for (int i = 1; i <= n; ++i) ans = min(ans, dp[i][FULL]);
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m,k; cin>>n>>m>>k;
    vector<vector<Edge>> g(n+1);
    for(int i=0;i<m;++i){
        int u,v; ll w; cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    vector<int> key(k);
    for(int i=0;i<k;++i) cin>>key[i];

    ll ans = steiner_tree(n, g, key);
    cout << ans << "\n";
    return 0;
}

// 记录路径的
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Edge { int to; ll w; };
struct UE { int u,v; ll w; };
const ll INF = (1LL<<60);

enum PT: unsigned char { NONE=0, BASE=1, MERGE=2, MOVE=3 };

// 返回最小代价，同时通过 used 输出树边（无向，去重）
ll steiner_tree(int n, const vector<vector<Edge>>& g, const vector<int>& key,
                vector<UE>& used) {
    int k = (int)key.size(), FULL = (1<<k) - 1;
    vector<vector<ll>> dp(n+1, vector<ll>(1<<k, INF));
    vector<vector<PT>> pt(n+1, vector<PT>(1<<k, NONE));
    vector<vector<int>> pn(n+1, vector<int>(1<<k, -1)), ps(n+1, vector<int>(1<<k, 0));
    vector<vector<ll>>  pw(n+1, vector<ll>(1<<k, 0));

    for (int j=0;j<k;++j){ dp[key[j]][1<<j]=0; pt[key[j]][1<<j]=BASE; }

    for (int S=1; S<=FULL; ++S){
        // 合并
        for (int i=1;i<=n;++i)
            for (int T=(S-1)&S; T; T=(T-1)&S){
                ll cand = dp[i][T] + dp[i][S^T];
                if (cand < dp[i][S]){ dp[i][S]=cand; pt[i][S]=MERGE; pn[i][S]=i; ps[i][S]=T; }
            }
        // 多源 Dijkstra 扩散
        priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
        for (int i=1;i<=n;++i) if (dp[i][S]<INF) pq.emplace(dp[i][S], i);
        while(!pq.empty()){
            auto [du,u]=pq.top(); pq.pop();
            if (du!=dp[u][S]) continue;
            for (auto e: g[u]){
                ll nd = du + e.w;
                if (nd < dp[e.to][S]){
                    dp[e.to][S]=nd; pt[e.to][S]=MOVE; pn[e.to][S]=u; ps[e.to][S]=0; pw[e.to][S]=e.w;
                    pq.emplace(nd, e.to);
                }
            }
        }
    }

    // 选根
    ll ans=INF; int root=-1;
    for (int i=1;i<=n;++i) if (dp[i][FULL]<ans) ans=dp[i][FULL], root=i;
    if (ans>=INF) { used.clear(); return -1; }

    // 回溯边
    vector<UE> raw; raw.reserve(n*2);
    function<void(int,int)> rec = [&](int u,int S){
        PT t = pt[u][S];
        if (t==BASE) return;
        if (t==MERGE){ int T=ps[u][S]; rec(u,T); rec(u,S^T); return; }
        if (t==MOVE){ int p=pn[u][S]; if (p!=-1){ int a=min(u,p), b=max(u,p); raw.push_back({a,b,pw[u][S]}); rec(p,S); } }
    };
    rec(root, FULL);

    // 去重
    sort(raw.begin(), raw.end(), [](const UE& A,const UE& B){
        if (A.u!=B.u) return A.u<B.u;
        if (A.v!=B.v) return A.v<B.v;
        return A.w<B.w;
    });
    used.clear();
    for (auto &e: raw)
        if (used.empty() || used.back().u!=e.u || used.back().v!=e.v || used.back().w!=e.w) used.push_back(e);

    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m,k; cin>>n>>m>>k;
    vector<vector<Edge>> g(n+1);
    for(int i=0;i<m;++i){ int u,v; ll w; cin>>u>>v>>w; g[u].push_back({v,w}); g[v].push_back({u,w}); }
    vector<int> key(k); for(int i=0;i<k;++i) cin>>key[i];

    vector<UE> used;
    ll ans = steiner_tree(n, g, key, used);
    if (ans<0){ cout<<"Impossible\n"; return 0; }
    cout<<ans<<"\n"<<used.size()<<"\n";
    for (auto &e: used) cout<<e.u<<" "<<e.v<<" "<<e.w<<"\n";
    return 0;
}

# 连通分量

# 强连通分量

有向图的两个点都可以互相到达叫 SCC
Tarjan：一趟 DFS + 栈 + lowlink，不建反图；省内存、实现稍 “技术型”。
Kosaraju：建反图，先 “完成序”，后 “反图染色”；直观、代码清晰、占内存。

#include <bits/stdc++.h>
using namespace std;

const int N = 200000 + 5;
const int M = 400000 + 5;  // 有向边数上界

struct E { int to, nxt; } e[M];
int head[N], ecnt;

void add_edge(int u, int v){
    e[++ecnt] = {v, head[u]};
    head[u] = ecnt;
}

// Tarjan
int dfn[N], low[N], idx;
int stk[N], top;
bool in_stk[N];
int scc_id[N], scc_cnt;
int scc_sz[N];

void tarjan(int u){
    dfn[u] = low[u] = ++idx;
    stk[++top] = u; in_stk[u] = true;

    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (low[u] == dfn[u]) { // u 是当前 SCC 的根
        ++scc_cnt;
        while (true){
            int x = stk[top--];
            in_stk[x] = false;
            scc_id[x] = scc_cnt;
            scc_sz[scc_cnt]++;
            if (x == u) break;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; 
    cin >> n >> m;
    for (int i = 0; i < m; ++i){
        int u, v; cin >> u >> v;   // 有向边 u -> v
        add_edge(u, v);
    }

    // 跑 Tarjan
    for (int u = 1; u <= n; ++u)
        if (!dfn[u]) tarjan(u);

    // 1) 强连通分量个数
    cout << scc_cnt << "\n";

    // 2) 每个点属于哪个 SCC（如需）
    // for (int u = 1; u <= n; ++u) cout << scc_id[u] << (u==n?'\n':' ');

    // 3) （可选）凝聚图入度/出度统计示例
    // vector<int> indeg(scc_cnt+1), outdeg(scc_cnt+1);
    // for (int u = 1; u <= n; ++u)
    //   for (int i = head[u]; i; i = e[i].nxt){
    //       int v = e[i].to;
    //       int a = scc_id[u], b = scc_id[v];
    //       if (a != b){ outdeg[a]++; indeg[b]++; }
    //   }
    // // 例：判断整图是否强连通：if (scc_cnt == 1) ...

    return 0;
}

# 有向环检测

struct TarjanSCC {
    int n, timer = 0;
    vector<vector<int>> g;
    vector<int> dfn, low, st;
    vector<char> in_st;
    bool has_cycle = false;  // result
    bool seen_self_loop = false;

    TarjanSCC(int n): n(n), g(n), dfn(n, -1), low(n, 0), in_st(n, 0) {}

    void add_edge(int u, int v) {
        g[u].push_back(v);
        if (u == v) seen_self_loop = true; // 自环即有环
    }

    void dfs(int u) {
        dfn[u] = low[u] = ++timer;
        st.push_back(u);
        in_st[u] = 1;

        for (int v : g[u]) {
            if (dfn[v] == -1) {            // tree edge
                dfs(v);
                low[u] = min(low[u], low[v]);
            } else if (in_st[v]) {         // back/forward/cross to stack => shrink
                low[u] = min(low[u], dfn[v]);
            }
        }

        // u is root of an SCC
        if (low[u] == dfn[u]) {
            int sz = 0;
            while (true) {
                int x = st.back(); st.pop_back();
                in_st[x] = 0;
                ++sz;
                if (x == u) break;
            }
            if (sz >= 2) has_cycle = true; // 一个 SCC 含 ≥2 个点 ⇒ 必有环
        }
    }

    bool run_and_check_cycle() {
        if (seen_self_loop) return true;  // 提前剪枝
        for (int i = 0; i < n && !has_cycle; ++i)
            if (dfn[i] == -1) dfs(i);
        return has_cycle;
    }
};

# 2-SAT

#include <bits/stdc++.h>
using namespace std;

struct TwoSAT {
    int n;                         // 变量个数：x0..x{n-1}
    vector<vector<int>> g;         // 蕴含图 (2n 节点)
    vector<int> dfn, low, comp, st;
    vector<char> ins, val;         // val[i] = 变量 i 的布尔解
    int dfsTime, compCnt;

    // 映射：literal -> 节点编号
    // node(i, 1) 表示 x_i 为真；node(i, 0) 表示 x_i 为假
    static inline int node(int i, int isTrue){ return (i<<1) | (isTrue?1:0); }
    static inline int neg(int x){ return x ^ 1; } // 反字面：最后一位取反

    TwoSAT(int n=0): n(n) {
        g.assign(2*n, {});
        dfn.assign(2*n, 0);
        low.assign(2*n, 0);
        comp.assign(2*n, -1);
        ins.assign(2*n, 0);
        val.assign(n, 0);
        dfsTime = compCnt = 0;
    }

    // 基本加边
    void add_imp(int u, int v){ g[u].push_back(v); }            // u -> v
    void add_or(int a, int b){ add_imp(neg(a), b); add_imp(neg(b), a); } // (a ∨ b)
    void add_true(int a){ add_imp(neg(a), a); }                 // a 为真
    void add_false(int a){ add_imp(a, neg(a)); }                // a 为假
    void add_eq(int a, int b){ add_imp(a,b); add_imp(b,a); add_imp(neg(a),neg(b)); add_imp(neg(b),neg(a)); }
    void add_xor(int a, int b){ add_or(a,b); add_or(neg(a),neg(b)); } // a ⊕ b

    // Tarjan
    void tarjan(int u){
        dfn[u]=low[u]=++dfsTime; st.push_back(u); ins[u]=1;
        for(int v: g[u]){
            if(!dfn[v]){ tarjan(v); low[u]=min(low[u], low[v]); }
            else if(ins[v]) low[u]=min(low[u], dfn[v]);
        }
        if(low[u]==dfn[u]){
            while(true){
                int x = st.back(); st.pop_back(); ins[x]=0;
                comp[x]=compCnt;
                if(x==u) break;
            }
            ++compCnt;
        }
    }

    // 求解：返回是否可满足；若可满足，val[i] 为解
    bool solve(){
        for(int u=0; u<2*n; ++u) if(!dfn[u]) tarjan(u);
        // 冲突判定
        for(int i=0;i<n;++i){
            if(comp[node(i,0)] == comp[node(i,1)]) return false;
        }
        // 赋值规则：分量拓扑序越“靠后”的优先为真
        // Tarjan 里的 comp 编号是按出栈顺序累增，通常可用：
        for(int i=0;i<n;++i){
            val[i] = (comp[node(i,1)] > comp[node(i,0)]); // true 分量拓扑更靠后 => 取真
        }
        return true;
    }
};

// 变量 x0, x1, x2
TwoSAT sat(3);
int x0 = TwoSAT::node(0,1);  // x0 为真这个字面
int nx0= TwoSAT::neg(x0);    // ¬x0

// 子句：(x0 ∨ ¬x1), (¬x0 ∨ x2)
sat.add_or( TwoSAT::node(0,1), TwoSAT::node(1,0) );
sat.add_or( TwoSAT::node(0,0), TwoSAT::node(2,1) );

// 约束：x1 = x2
sat.add_eq( TwoSAT::node(1,1), TwoSAT::node(2,1) );

// 指定 x0 为真
sat.add_true( TwoSAT::node(0,1) );

bool ok = sat.solve();
if(!ok) { /* 无解 */ }
else {
    // sat.val[i] 是 x_i 的布尔解
}

#include <bits/stdc++.h>
using namespace std;

struct TwoSAT {
    int n;
    vector<vector<int>> g;
    vector<int> dfn, low, comp, st;
    vector<char> ins, val;
    int tim, scc_cnt;

    static inline int node(int i, bool isTrue){ return (i<<1) | (isTrue?1:0); }
    static inline int neg(int x){ return x ^ 1; }

    TwoSAT(int n=0): n(n) {
        g.assign(2*n, {});
        dfn.assign(2*n, 0);
        low.assign(2*n, 0);
        comp.assign(2*n, -1);
        ins.assign(2*n, 0);
        val.assign(n, 0);
        tim = scc_cnt = 0;
    }
    void add_imp(int u,int v){ g[u].push_back(v); }                 // u -> v
    void add_or(int a,int b){ add_imp(neg(a), b); add_imp(neg(b), a); } // (a ∨ b)

    void tarjan(int u){
        dfn[u]=low[u]=++tim; st.push_back(u); ins[u]=1;
        for(int v: g[u]){
            if(!dfn[v]){ tarjan(v); low[u]=min(low[u], low[v]); }
            else if(ins[v]) low[u]=min(low[u], dfn[v]);
        }
        if(low[u]==dfn[u]){
            while(true){
                int x=st.back(); st.pop_back(); ins[x]=0;
                comp[x]=scc_cnt;
                if(x==u) break;
            }
            ++scc_cnt;
        }
    }
    bool solve(){
        for(int u=0;u<2*n;++u) if(!dfn[u]) tarjan(u);
        for(int i=0;i<n;++i) if(comp[node(i,0)]==comp[node(i,1)]) return false;
        for(int i=0;i<n;++i) val[i] = (comp[node(i,1)] > comp[node(i,0)]); // True(红) 优先
        return true;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k, n;                      // k 灯数，n 人数
    if(!(cin >> k >> n)) return 0;
    TwoSAT sat(k);

    auto lit = [&](int id, char c){ // id: 1..k; c in {'R','B'}
        return TwoSAT::node(id-1, c=='R'); // R=Xi(true), B=¬Xi(false)
    };

    for(int i=0;i<n;++i){
        int a,b,c; char ca,cb,cc;
        cin >> a >> ca >> b >> cb >> c >> cc;
        int L1 = lit(a, ca), L2 = lit(b, cb), L3 = lit(c, cc);
        sat.add_or(L1, L2);
        sat.add_or(L1, L3);
        sat.add_or(L2, L3);
    }

    if(!sat.solve()){ cout << -1 << "\n"; return 0; }

    // 输出一种着色方案：长度 k 的字符串（R/B）
    for(int i=0;i<k;++i) cout << (sat.val[i] ? 'R' : 'B');
    cout << "\n";
    return 0;
}

# 欧拉图与欧拉回路

一笔画问题

#include <bits/stdc++.h>
using namespace std;

// 统一欧拉路模板：directed=true 有向；false 无向
struct Euler {
    int n; bool directed;
    vector<vector<pair<int,int>>> adj; // (to, eid)
    vector<int> indeg, outdeg, deg, it;
    vector<char> used;
    vector<int> path;
    int M; // 边计数（无向边算 1 条；有向边算 1 条）

    Euler(int n, bool directed): n(n), directed(directed),
        adj(n+1), indeg(n+1,0), outdeg(n+1,0), deg(n+1,0), it(n+1,0), M(0) {}

    // 加边：有向=单向；无向=双向（共享同一 eid）
    void addEdge(int u, int v){
        int id = M++;
        if ((int)used.size() < M) used.resize(M, 0);
        adj[u].push_back({v,id});
        if (directed){
            outdeg[u]++; indeg[v]++;
        } else {
            adj[v].push_back({u,id});
            deg[u]++; deg[v]++;
        }
    }

    void sort_adj(){
        for (int u=1; u<=n; ++u)
            sort(adj[u].begin(), adj[u].end(),
                [](const auto& A, const auto& B){ return A.first < B.first; });
    }

    bool feasible(){ // 度数可行性快速判断
        if (directed){
            int plus1=0, minus1=0;
            for (int u=1; u<=n; ++u){
                int d = outdeg[u]-indeg[u];
                if (d==1) ++plus1;
                else if (d==-1) ++minus1;
                else if (d!=0) return false;
            }
            return (M==0) || (plus1==0&&minus1==0) || (plus1==1&&minus1==1);
        } else {
            int odd=0;
            for (int u=1; u<=n; ++u) if (deg[u]&1) ++odd;
            return (M==0) || (odd==0 || odd==2);
        }
    }

    int pick_start(){ // 选起点（字典序最小）
        if (directed){
            for (int u=1; u<=n; ++u) if (outdeg[u]-indeg[u]==1) return u;
            for (int u=1; u<=n; ++u) if (outdeg[u]>0) return u;
        } else {
            for (int u=1; u<=n; ++u) if (deg[u]&1) return u;
            for (int u=1; u<=n; ++u) if (deg[u]>0) return u;
        }
        return 1; // 无边时随便
    }

    void dfs(int u){
        auto &i = it[u];
        while (i < (int)adj[u].size()){
            auto [v,id] = adj[u][i++];
            if (used[id]) continue;
            used[id] = 1;          // 无向图两方向共用同一 eid → 一次标记解决
            dfs(v);
        }
        path.push_back(u);
    }

    // 返回顶点序列；空=不存在或未覆盖所有边（不连通等）
    vector<int> run(bool lex_smallest=true){
        path.clear(); fill(it.begin(), it.end(), 0);
        if (!feasible()) return {};
        if (lex_smallest) sort_adj();
        if (M==0) return {}; // 没有边时按题意自己处理
        int s = pick_start();
        dfs(s);
        if ((int)path.size() != M+1) return {}; // 没走完所有边
        reverse(path.begin(), path.end());
        return path;
    }
};

int n = 500; // 或者“读到的最大点号”
int m; cin >> m;
Euler G(n, /*directed=*/false);
for (int i=0;i<m;++i){ int u,v; cin>>u>>v; G.addEdge(u,v); }
auto ans = G.run(true);             // 字典序最小
for (int v: ans) cout << v << "\n"; // 每行一个点

# 网络流

# Edmonds–Karp 思想

边上有流量限制，有源点和汇点，如何分配才能让流到汇点的流最大？
Ford–Fulkerson 增广思路，大概是先确定一条路径，然后以路径的最小边为限制，再找增广路；增广路一旦加入就涉及到流量回退和调整。
残量网络：真正在跑的是 “还能走多少” 的图；每加一条正向边就配一条反向边（退流）。
增广到不能增为止：有路就把流量推过去，没路 = 最大流 = 能从源到达的一侧就是最小割 S。
模板首选 Dinic：BFS 分层 + DFS 推阻塞流

若节点也有流量限制，可拆点（A 拆为 A1 --> A2，流量限制转移到边上），从而转化为纯最大流。

# Dinic (n^2*m)

最大流 = 最小割，若每条边容量均为 1，则等价于返回割边数量。

addEdge(u,v,c) 有向边；无向边用 addUndirected(u,v,c)
maxflow(s,t) 求最大流
mincut_reachable(s) 返回最大流后割的 S 集合（可用来取最小割）

#include <bits/stdc++.h>
using namespace std;

struct Dinic {
    struct Edge { int to, rev; long long cap; };
    int n;
    vector<vector<Edge>> g;
    vector<int> level, ptr;

    Dinic(int n=0){ init(n); }
    void init(int n_){
        n = n_;
        g.assign(n, {});
        level.assign(n, 0);
        ptr.assign(n, 0);
    }

    // 有向边 u->v 容量 c；返回前向边在 g[u] 的下标（可留作以后改容量）
    int addEdge(int u, int v, long long c){
        Edge a{v, (int)g[v].size(), c};
        Edge b{u, (int)g[u].size(), 0};
        g[u].push_back(a); g[v].push_back(b);
        return (int)g[u].size()-1;
    }
    // 无向边（双向同容量）
    void addUndirected(int u, int v, long long c){
        Edge a{v, (int)g[v].size(), c};
        Edge b{u, (int)g[u].size(), c};
        g[u].push_back(a); g[v].push_back(b);
    }

    bool bfs(int s, int t){
        fill(level.begin(), level.end(), -1);
        queue<int> q; level[s]=0; q.push(s);
        while(!q.empty()){
            int u=q.front(); q.pop();
            for(const auto& e: g[u]){
                if(e.cap>0 && level[e.to]==-1){
                    level[e.to]=level[u]+1;
                    q.push(e.to);
                }
            }
        }
        return level[t]!=-1;
    }

    long long dfs(int u, int t, long long pushed){
        if(!pushed) return 0;
        if(u==t)     return pushed;
        for(int &i=ptr[u]; i<(int)g[u].size(); ++i){
            auto &e = g[u][i];
            if(e.cap>0 && level[e.to]==level[u]+1){
                long long tr = dfs(e.to, t, min(pushed, e.cap));
                if(tr){
                    e.cap -= tr;
                    g[e.to][e.rev].cap += tr;   // 反向边加容量 = 退流
                    return tr;
                }
            }
        }
        return 0;
    }

    long long maxflow(int s, int t){
        long long flow = 0;
        const long long INF = (1LL<<62);
        while(bfs(s,t)){
            fill(ptr.begin(), ptr.end(), 0);
            while(true){
                long long pushed = dfs(s,t,INF);
                if(!pushed) break;
                flow += pushed;
            }
        }
        return flow;
    }

    // 在最大流之后，返回从 s 在残量图可达的点（S 集合）；用它即可拿最小割
    vector<int> mincut_reachable(int s){
        vector<int> vis(n,0);
        queue<int> q; q.push(s); vis[s]=1;
        while(!q.empty()){
            int u=q.front(); q.pop();
            for(auto &e: g[u]) if(e.cap>0 && !vis[e.to]){
                vis[e.to]=1; q.push(e.to);
            }
        }
        return vis; // vis[u]=1 属于 S；否则属于 T
    }
};

int nL, nR; // 左右部点数
Dinic D(nL + nR + 2);
int S = nL + nR, T = S + 1;
for(int u=1; u<=nL; ++u) D.addEdge(S, u-1, 1);
for(int v=1; v<=nR; ++v) D.addEdge(nL+v-1, T, 1);
// 有边的 (u in L, v in R): 
// D.addEdge(u-1, nL+v-1, 1);
long long M = D.maxflow(S,T); // 即最大匹配数

auto side = D.mincut_reachable(S);
// (u in S and edge u->v 满流) 即是最小割边

指定了源点 s 和汇点 t，要你 “切断 s 到 t 的最小代价”，用 Dinic 就行。
把题目抽象成 “切断 s 和 t 的最小代价”，确定是 边代价 还是 点代价（点代价→拆点）。
容量 = 代价；需要 “不可通过” 的地方用 ∞。
多源多汇 → 加超级源 / 汇。
maxflow(s,t) 得数值； mincut_reachable(s) 拿到 S 集合，从而恢复 “要切的边 / 点”。

# 全局最小割，区分 s-t 最小割

定义无向图 G 的最小割为：一个去掉后可以使 G 变成两个连通分量，且边权和最小的边集的边权和。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 输入：1..n，无向图，邻接矩阵 w（对称，w[i][i]=0，重复边需累加）
// 返回：全局最小割的权值；如需割的一侧节点集合，传入 outS
ll stoer_wagner(int n, vector<vector<ll>>& w, vector<int>* outS = nullptr) {
    const ll INF = (1LL<<60);
    vector<int> exist(n+1, 1), added(n+1), prev(n+1);
    ll best = INF;
    vector<int> bestS;

    for (int phase = 1; phase < n; ++phase) {
        fill(added.begin(), added.end(), 0);
        vector<ll> dist(n+1, 0);
        int s = -1, t = -1;

        for (int it = 1; it <= n - phase + 1; ++it) {
            int sel = -1;
            for (int v = 1; v <= n; ++v)
                if (exist[v] && !added[v] && (sel == -1 || dist[v] > dist[sel])) sel = v;

            if (it == n - phase + 1) {           // 最后加入的点 = t，倒数第二个 = s
                t = sel; s = prev[sel];

                // 本轮 s-t 最小割值 = dist[t]
                if (dist[t] < best) {
                    best = dist[t];
                    if (outS) {                   // 记录此轮的 A\{t} 作为一侧
                        vector<int> S;
                        for (int v = 1; v <= n; ++v)
                            if (exist[v] && added[v] && v != t) S.push_back(v);
                        bestS.swap(S);
                    }
                }

                // 合并 t -> s
                if (s == -1) { exist[t] = 0; break; } // n=1 时
                exist[t] = 0;
                for (int v = 1; v <= n; ++v) if (exist[v] && v != s) {
                    w[s][v] += w[t][v];
                    w[v][s] += w[v][t];
                }
            } else {
                added[sel] = 1;
                for (int v = 1; v <= n; ++v) if (exist[v] && !added[v]) {
                    dist[v] += w[sel][v];
                    prev[v] = sel;
                }
            }
        }
    }
    if (outS) *outS = bestS;
    return (best == (1LL<<60) ? 0 : best); // 不连通时答案为 0
}

# 最小费用最大流

#include <bits/stdc++.h>
using namespace std;

struct MCMF {
    struct Edge {
        int to, rev;           // rev = 反向边在 g[to] 中的下标
        long long cap, cost;   // 残量容量、单位费用
    };
    int n;
    vector<vector<Edge>> g;

    explicit MCMF(int n=0): n(n), g(n) {}

    void reset(int n_) { n = n_; g.assign(n, {}); }

    // 有向边 u->v，容量 cap，单位费用 cost
    void addEdge(int u, int v, long long cap, long long cost) {
        Edge a{v, (int)g[v].size(), cap,  cost};
        Edge b{u, (int)g[u].size(), 0,   -cost};
        g[u].push_back(a);
        g[v].push_back(b);
    }

    // 最小费用最大流（SPFA 版）
    // 返回 pair<最大流量，最小费用>。可以用 max_need 限制需要的流量（默认尽量多）
    pair<long long,long long> minCostMaxFlow(int s, int t, long long max_need = LLONG_MAX) {
        const long long INF = (long long)4e18;
        long long flow = 0, cost = 0;

        vector<long long> dist(n);
        vector<int> inq(n), pre_v(n), pre_e(n); // 记录前驱顶点与边下标

        while (flow < max_need) {
            // SPFA 寻找单位费用最短增广路（允许负边但需无可达负圈）
            fill(dist.begin(), dist.end(), INF);
            fill(inq.begin(),  inq.end(),  0);
            fill(pre_v.begin(), pre_v.end(), -1);

            queue<int> q;
            dist[s] = 0;
            q.push(s);
            inq[s] = 1;

            while (!q.empty()) {
                int u = q.front(); q.pop();
                inq[u] = 0;
                for (int i = 0; i < (int)g[u].size(); ++i) {
                    const Edge &e = g[u][i];
                    if (e.cap <= 0) continue;
                    if (dist[e.to] > dist[u] + e.cost) {
                        dist[e.to] = dist[u] + e.cost;
                        pre_v[e.to] = u;
                        pre_e[e.to] = i;
                        if (!inq[e.to]) { q.push(e.to); inq[e.to] = 1; }
                    }
                }
            }

            if (pre_v[t] == -1) break; // 无增广路，结束

            // 计算本次可增广量
            long long aug = max_need - flow;
            for (int v = t; v != s; v = pre_v[v]) {
                const Edge &e = g[pre_v[v]][pre_e[v]];
                aug = min(aug, e.cap);
            }
            // 沿路增广 & 更新费用
            for (int v = t; v != s; v = pre_v[v]) {
                Edge &e  = g[pre_v[v]][pre_e[v]];
                Edge &re = g[e.to][e.rev];
                e.cap  -= aug;
                re.cap += aug;
            }
            flow += aug;
            cost += aug * dist[t];
        }
        return {flow, cost};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s, t; 
    cin >> n >> m >> s >> t;
    MCMF mf(n+1); // 点编号 1..n
    for (int i=0;i<m;i++){
        int u,v; long long cap, cost;
        cin >> u >> v >> cap >> cost;
        mf.addEdge(u,v,cap,cost); // 有向
    }
    auto [maxflow, mincost] = mf.minCostMaxFlow(s,t);
    cout << maxflow << " " << mincost << "\n";
}

例题：G 公司有 n 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 n 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。

# 其他图

# 二分图判别

二分图，又称二部图，是一类结构特殊的图。它的顶点集可以划分为两个互不相交的子集，使得图中的每条边都连接这两个集合之间的一对点，而不会连接同一集合内部的点。
染色判别法

#include <bits/stdc++.h>
using namespace std;

struct BipartiteCheck {
    int n;
    vector<vector<int>> g;
    vector<int> color;          // -1=未染色，0/1 两色
    vector<int> partL, partR;   // 染色成功后分组

    BipartiteCheck(int n=0): n(n), g(n+1), color(n+1,-1) {}
    void addEdge(int u,int v){ g[u].push_back(v); g[v].push_back(u); }

    bool run(){
        queue<int> q;
        for(int s=1;s<=n;++s) if(color[s]==-1 && !g[s].empty()){
            color[s]=0; q.push(s);
            while(!q.empty()){
                int u=q.front(); q.pop();
                for(int v: g[u]){
                    if(color[v]==-1){ color[v]=color[u]^1; q.push(v); }
                    else if(color[v]==color[u]) return false; // 奇环
                }
            }
        }
        partL.clear(); partR.clear();
        for(int i=1;i<=n;++i) if(color[i]!=-1)
            (color[i]?partR:partL).push_back(i);
        return true;
    }
};

# 二分图匹配匈牙利 Kuln 算法

只要 “匹配对数最多” → Kuhn（匈牙利不带权）；大图更快用 Hopcroft–Karp。
要 “总收益最大 / 总成本最小（完美指派）” → KM 匈牙利（带权）；矩阵规模 n≤n\len≤ 几千以内常用。

无权匹配，只关心匹配对数最大（不看权重）：例如 “最多能安排多少门实验进不同实验室”、“最多能让多少任务被不同机器接收” 等。

#include <bits/stdc++.h>
using namespace std;

struct HungarianKuhn {
    int nL, nR;
    vector<vector<int>> g;     // g[u] : u(1..nL) 可连到的右部点集合 (1..nR)
    vector<int> matchR, seen;  // matchR[v]=与右部 v 匹配的左部 u(无则 0)
    int visToken = 1;

    HungarianKuhn(int nL, int nR) : nL(nL), nR(nR), g(nL+1), matchR(nR+1, 0), seen(nR+1, 0) {}

    void addEdge(int u, int v) { g[u].push_back(v); }

    bool dfs(int u) {
        for (int v : g[u]) if (seen[v] != visToken) {
            seen[v] = visToken;
            if (matchR[v] == 0 || dfs(matchR[v])) { matchR[v] = u; return true; }
        }
        return false;
    }

    // 返回最大匹配数，以及匹配对 (u,v)
    pair<int, vector<pair<int,int>>> maxMatching() {
        int match = 0;
        for (int u = 1; u <= nL; ++u) {
            ++visToken;
            if (dfs(u)) ++match;
        }
        vector<pair<int,int>> pairs;
        for (int v = 1; v <= nR; ++v) if (matchR[v]) pairs.push_back({matchR[v], v});
        return {match, pairs};
    }
};

/* 用法
int nL,nR,m; cin>>nL>>nR>>m;
HungarianKuhn hk(nL,nR);
while(m--){ int u,v; cin>>u>>v; hk.addEdge(u,v); }
auto [cnt, pairs] = hk.maxMatching();
cout<<cnt<<"\n";
*/

最大权，带权值了，比如工人指派任务的最大收益

#include <bits/stdc++.h>
using namespace std;

// KM 求二分图最大权匹配（指派问题），1..n 索引
// w[i][j] : 左 i 到 右 j 的权值（可为 0/正；若有负，建议整体平移）
// 返回 {最大权值，matchR[1..n] } 其中 matchR[j]=与右部 j 匹配的左部 i
struct HungarianKM {
    int n;
    vector<vector<long long>> w;
    vector<long long> lx, ly, slack;
    vector<int> matchR, pre;
    vector<bool> vx, vy;

    HungarianKM(int n): n(n), w(n+1, vector<long long>(n+1, 0)),
        lx(n+1, 0), ly(n+1, 0), slack(n+1, 0),
        matchR(n+1, 0), pre(n+1, 0), vx(n+1, false), vy(n+1, false) {}

    void setWeight(int i, int j, long long val) { w[i][j] = val; }

    // 主过程：O(n^3)
    pair<long long, vector<int>> solve() {
        // 初始化顶标 lx 为该行最大权，ly=0
        for (int i = 1; i <= n; ++i) {
            lx[i] = w[i][1];
            for (int j = 2; j <= n; ++j) lx[i] = max(lx[i], w[i][j]);
        }
        for (int i = 1; i <= n; ++i) {
            fill(slack.begin(), slack.end(), (long long)4e18);
            fill(vx.begin(), vx.end(), false);
            fill(vy.begin(), vy.end(), false);
            fill(pre.begin(), pre.end(), 0);

            int y0 = 0;      // 当前“未匹配的右部点”指针
            matchR[0] = i;   // 让 0 当作虚拟右点
            do {
                vx[ matchR[y0] ] = true;
                long long delta = (long long)4e18;
                int x0 = matchR[y0], y1 = 0;
                for (int y = 1; y <= n; ++y) if (!vy[y]) {
                    long long gap = lx[x0] + ly[y] - w[x0][y];
                    if (gap < slack[y]) { slack[y] = gap; pre[y] = y0; }
                    if (slack[y] < delta) { delta = slack[y]; y1 = y; }
                }
                // 调整顶标
                for (int y = 0; y <= n; ++y) {
                    if (vx[ matchR[y] ]) lx[ matchR[y] ] -= delta;
                    if (vy[y]) ly[y] += delta;
                    else slack[y] -= delta;
                }
                y0 = y1;
                vy[y0] = true;
            } while (matchR[y0] != 0); // 找到一条到未匹配右点的增广路

            // 回溯增广
            while (y0) {
                int yPrev = pre[y0];
                matchR[y0] = matchR[yPrev];
                y0 = yPrev;
            }
        }
        long long best = 0;
        for (int y = 1; y <= n; ++y) best += w[ matchR[y] ][ y ];
        return {best, matchR}; // matchR[j] = i
    }
};

/* 用法（最小化成本示例）
int n; cin>>n;
HungarianKM km(n);
long long C = 0; // 若有负值，可先遍历找最小值 minW，再令 C = -minW，填 w'=w+C
for (int i=1;i<=n;i++)
  for (int j=1;j<=n;j++){
    long long cost; cin>>cost;
    km.setWeight(i,j, -cost); // 直接取负做“最大化”，或做平移后取负
  }
auto [maxW, matchR] = km.solve();
long long minCost = -maxW;
cout << minCost << "\n";
// 配对：右部 j 匹配左部 matchR[j]
*/

# 图着色

现在除了 a. 二分图这种，还有可能，给定一个无向图，要求每个点相邻的点要求不一样染色。例题如下。

// ====== Welsh–Powell（度降序贪心，增强版）======
// 复杂度 ~ O(n^2 + m)
// - col[1..n]: 输入可全 0；若有预染色 (>0) 会被保留，不会再改
// - groups: 可选输出，每个颜色对应的点集合；传 nullptr 则不填
// - custom_order: 可选自定义顶点顺序（长度为 n，元素为 1..n 且互异）
// 返回：使用到的颜色数
int WelshPowell(int n,
                const vector<vector<int>>& g,
                vector<int>& col,
                vector<vector<int>>* groups = nullptr,
                const vector<int>* custom_order = nullptr) {
    if ((int)col.size() < n+1) col.assign(n+1, 0);

    // 决定顺序：默认按度数降序；若提供 custom_order 就用它
    vector<int> ord;
    if (custom_order && (int)custom_order->size() == n) {
        ord = *custom_order;
    } else {
        ord.resize(n);
        iota(ord.begin(), ord.end(), 1);
        sort(ord.begin(), ord.end(), [&](int a, int b){
            if (g[a].size() != g[b].size()) return g[a].size() > g[b].size();
            return a < b;
        });
    }

    vector<char> forbid(n+1, 0); // 本轮颜色的禁用标记
    vector<char> taken(n+1, 0);  // 是否已被本算法刷新/确认过（含预染色）
    int painted = 0;

    // 统计预染色数量
    for (int v = 1; v <= n; ++v) if (col[v] > 0) {
        taken[v] = 1;
        ++painted;
    }

    int used_colors = 0;

    // 先把已有颜色的最大值作为起点（兼容预染色）
    for (int v = 1; v <= n; ++v) if (col[v] > 0)
        used_colors = max(used_colors, col[v]);

    // 主循环：每一轮铺一种新颜色
    for (int idx = 0; idx < n; ++idx) {
        int v = ord[idx];
        if (taken[v]) continue; // 预染色或已上色

        int c = ++used_colors;
        fill(forbid.begin(), forbid.end(), 0);

        // 先把所有已是颜色 c 的点（可能来自预染色）标注 forbid 邻居
        for (int x = 1; x <= n; ++x) if (col[x] == c) {
            for (int u : g[x]) forbid[u] = 1;
        }

        // 选第一个点 v（若它不被 forbid）
        if (!forbid[v]) {
            col[v] = c;
            taken[v] = 1;
            ++painted;
            for (int u : g[v]) forbid[u] = 1;
        } else {
            // v 不能用本色，跳过；让后续点来铺这一色
        }

        // 扫后续，能上 c 的都上
        for (int j = idx + 1; j < n; ++j) {
            int w = ord[j];
            if (taken[w] || forbid[w]) continue;
            col[w] = c;
            taken[w] = 1;
            ++painted;
            for (int u : g[w]) forbid[u] = 1;
        }
        if (painted == n) break;
    }

    // 可选：汇总颜色分组
    if (groups) {
        groups->assign(used_colors + 1, {});
        for (int v = 1; v <= n; ++v) if (col[v] > 0)
            (*groups)[col[v]].push_back(v);
    }
    return used_colors;
}

// ====== 合法性校验：所有边的两端颜色不同 ======
bool CheckColoring(int n, const vector<vector<int>>& g, const vector<int>& col) {
    for (int u = 1; u <= n; ++u) for (int v : g[u]) if (u < v) {
        if (col[u] == 0 || col[v] == 0) return false;
        if (col[u] == col[v]) return false;
    }
    return true;
}

# 三元环，四元环计数

#include <iostream>
using namespace std;

int n, m, total;
int deg[200001], u[200001], v[200001];
bool vis[200001];

struct Edge {
  int to, nxt;
} edge[200001];

int cntEdge, head[100001];

void addEdge(int u, int v) {
  edge[++cntEdge] = {v, head[u]}, head[u] = cntEdge;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) cin >> u[i] >> v[i], deg[u[i]]++, deg[v[i]]++;
  for (int i = 1; i <= m; i++) {
    if ((deg[u[i]] == deg[v[i]] && u[i] > v[i]) || deg[u[i]] < deg[v[i]])
      swap(u[i], v[i]);
    addEdge(u[i], v[i]);
  }
  for (int u = 1; u <= n; u++) {
    for (int i = head[u]; i; i = edge[i].nxt) vis[edge[i].to] = true;
    for (int i = head[u]; i; i = edge[i].nxt) {
      int v = edge[i].to;
      for (int j = head[v]; j; j = edge[j].nxt) {
        int w = edge[j].to;
        if (vis[w]) total++;
      }
    }
    for (int i = head[u]; i; i = edge[i].nxt) vis[edge[i].to] = false;
  }
  cout << total << '\n';
  return 0;
}

四元环

#include <iostream>
#include <vector>
using namespace std;

int n, m, deg[100001], cnt[100001];
vector<int> E[100001], E1[100001];

long long total;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    E[u].push_back(v);
    E[v].push_back(u);
    deg[u]++, deg[v]++;
  }
  for (int u = 1; u <= n; u++)
    for (int v : E[u])
      if (deg[u] > deg[v] || (deg[u] == deg[v] && u > v)) E1[u].push_back(v);
  for (int a = 1; a <= n; a++) {
    for (int b : E1[a])
      for (int c : E[b]) {
        if (deg[a] < deg[c] || (deg[a] == deg[c] && a <= c)) continue;
        total += cnt[c]++;
      }
    for (int b : E1[a])
      for (int c : E[b]) cnt[c] = 0;
  }
  cout << total << '\n';
  return 0;
}

#

# 博弈与概率

# 其他技巧

# 异或大法

异或就是相同为 0，不同为 1

统计二进制串 1 的个数

int e ;
int cnt = 0;
while(e>0){
  e = e&(e-1); //每一次消除一个 1，两种情况，10，01
  cnt++;
}

统计一个数字出现的次数是奇数次还是偶数次

# 双指针看链表是否有环

bool hasCycle(ListNode *head) {
    // 快慢指针初始化指向 head
    ListNode *slow = head, *fast = head;
    // 快指针走到末尾时停止
    while (fast != nullptr && fast->next != nullptr) {
        // 慢指针走一步，快指针走两步
        slow = slow->next;
        fast = fast->next->next;
        // 快慢指针相遇，说明含有环
        if (slow == fast) {
            return true;
        }
    }
    // 不包含环
    return false;
}

# 莫队离线区间查询

#include <bits/stdc++.h>
using namespace std;

struct MoQuery {
    int l, r, id;
};

struct Mo {
    int block;
    explicit Mo(int n) : block(max(1, (int)std::sqrt(max(1,n)))) {}

    template<class Query, class Add, class Remove, class Answer>
    void run(vector<Query>& qs, Add add, Remove remove, Answer answer) {
        auto cmp = [&](const Query& A, const Query& B){
            int ba = A.l / block, bb = B.l / block;
            if (ba != bb) return ba < bb;
            // 奇偶优化
            return (ba & 1) ? (A.r > B.r) : (A.r < B.r);
        };
        sort(qs.begin(), qs.end(), cmp);

        int curL = 0, curR = -1;  // 当前区间为空
        for (auto &q : qs) {
            while (curL > q.l) add(--curL);
            while (curR < q.r) add(++curR);
            while (curL < q.l) remove(curL++);
            while (curR > q.r) remove(curR--);
            answer(q);
        }
    }
};

一个使用例子，查任意区间出现频次最多的数字：

我们要动态维护一个区间 [L, R] ，能随时知道：
cnt[x]：某个值 x 在当前区间出现了多少次。
相当于一个 “词频表”。
bucket[f]：所有出现了 恰好 f 次 的值，存在一个有序集合里（ set<int> ）。
为什么要有序？因为如果多个值并列最高频，还要选最小值，那就直接取 *bucket[f].begin() 。
curMaxFreq：当前区间的最高频是多少。
答案就是 bucket[curMaxFreq] 里的最小值；如果 curMaxFreq < threshold ，返回 -1 。

#include <bits/stdc++.h>
using namespace std;

struct QEx { int l, r, t, id; };  // 扩展查询，包含阈值

vector<int> subarrayMajority(vector<int>& nums, vector<vector<int>>& queries) {
    int n = (int)nums.size(), q = (int)queries.size();
    vector<QEx> qs; qs.reserve(q);
    for (int i = 0; i < q; ++i) {
        int l = queries[i][0], r = queries[i][1], t = queries[i][2];
        if (l > r) swap(l, r);
        qs.push_back({l, r, t, i});
    }

    // —— 维护结构 —— //
    unordered_map<int,int> cnt;                 // 值 -> 频次
    cnt.reserve((size_t)min(n, 1<<20));
    cnt.max_load_factor(0.7f);

    vector< set<int> > bucket(n + 1);          // 频次 f -> 值集合 (升序)
    int curMaxFreq = 0;

    auto add_pos = [&](int pos){
        int x = nums[pos];
        int f = cnt[x];
        if (f > 0) {
            auto &S = bucket[f];
            auto it = S.find(x);
            if (it != S.end()) S.erase(it);
        }
        int nf = f + 1;
        cnt[x] = nf;
        bucket[nf].insert(x);
        if (nf > curMaxFreq) curMaxFreq = nf;
    };

    auto remove_pos = [&](int pos){
        int x = nums[pos];
        int f = cnt[x];             // f >= 1
        auto &S = bucket[f];
        auto it = S.find(x);
        if (it != S.end()) S.erase(it);

        int nf = f - 1;
        cnt[x] = nf;
        if (nf > 0) bucket[nf].insert(x);

        while (curMaxFreq > 0 && bucket[curMaxFreq].empty()) curMaxFreq--;
    };

    vector<int> ans(q, -1);

    // —— 套用莫队板子 —— //
    struct MoQuery { int l, r, id; };
    vector<MoQuery> baseQs; baseQs.reserve(q);
    for (auto &e : qs) baseQs.push_back({e.l, e.r, e.id});

    Mo mo(n);
    mo.run(baseQs,
           add_pos,
           remove_pos,
           [&](const MoQuery& bq){
               const QEx &orig = qs[bq.id];  // 取回带阈值的原查询
               if (curMaxFreq >= orig.t) {
                   ans[orig.id] = *bucket[curMaxFreq].begin(); // 并列取最小
               } else {
                   ans[orig.id] = -1;
               }
           });

    return ans;
}

# 模拟

# 枚举

子集枚举

void print_subset(int n, bool* B, int cur){
    if(cur == n) { // 递归完毕
        for(int i = 0; i < cur; ++i) // 打印当前集合
            if(B[i]) printf("%d ", i);
        printf("\n");
        return ;
    }
    B[cur] = 1; // 选第 cur 个元素
    print_subset(n ,B, cur+1);
    B[cur] = 0; // 不选第 cur 个元素
    print_subset(n ,B, cur+1);
 }

# 日期

#define _for(i,a,b) for(int i=(a); i<=(b); ++i)

struct Date {
    int year, month, day;
    Date(int y, int m, int d): year(y), month(m), day(d) {}

    int week(){   // 今天是星期几？基姆拉尔森公式
        int y = year, m = month, d = day;
        if(m==1||m==2) m+=12,y--;
        int w = (d+2*m+3*(m+1)/5 + y + y/4 - y/100 + y/400) % 7;
        return ++w; // w：0:星期一...依此类推
    }

    int MONTH[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    int kthDay(){  // 给定一个日期，输出这个日期是该年的第几天
        if(year % 4 == 0 && (year % 100 || year % 400 == 0))
            MONTH[2] = 29;
        int days = 0;
        _for(i, 1, month-1) days += MONTH[i];
        return days + day;
    }
};

# 区间查询 - 统计类

给一个数组 nums 和若干询问 queries ，每个询问是 [l, r, thr] 。
对于子数组 nums[l..r] ，找出出现次数最多的值 bestVal ，若它的出现次数 bestCnt >= thr 就返回 bestVal ，否则返回 -1 。
若有并列最多，代码里取数值更小的那个。

class Solution {
public:
    vector<int> subarrayMajority(vector<int>& nums, vector<vector<int>>& queries) {
        vector<int> ans;
        ans.reserve(queries.size());

        unordered_map<int,int> freq;
        for (const auto& q : queries) {
            int l = q[0], r = q[1], thr = q[2];
            if (l > r) swap(l, r);
            freq.clear();
            freq.reserve(r - l + 1);
            for (int i = l; i <= r; ++i) {
                ++freq[nums[i]];
            }
            int bestVal = -1, bestCnt = -1;
            for (auto& kv : freq) {
                int val = kv.first, cnt = kv.second;
                if (cnt > bestCnt || (cnt == bestCnt && val < bestVal)) {
                    bestCnt = cnt;
                    bestVal = val;
                }
            }

            ans.push_back(bestCnt >= thr ? bestVal : -1);
        }
        return ans;
    }
};

# 括号匹配

bool stack_char(string str){
    // 括号匹配
    stack<char> s;
    for (char c : str) {
        if (c == '(' || c == '[' || c == '{') {
            s.push(c);
        } else {
            if (s.empty() || !(s.top()==c)) return false;
            s.pop();
        }
    }
    return s.empty();
}

# 霍夫曼树 - 编码

例子一：最小带权编码（k 叉霍夫曼）

// k-ary Huffman template
// 功能：给定权重（出现次数）weights 与进制 k，返回：
// 1) 最小总长度（带权路径和）sum_i (weights[i] * code_len_i)
// 2) 最长码长（最大 code_len_i）
// 说明：当 n==1 时，默认 code_len=0（常见竞赛设定）

#include <bits/stdc++.h>
using namespace std;

struct HuffmanResult {
    long long total_len; // 最小总长度（带权路径和）
    int max_len;         // 最长码长
};

HuffmanResult huffman_k_ary(const vector<long long>& weights, int k) {
    const int n = (int)weights.size();
    if (n == 0) return {0, 0};
    // 最小堆：按 (权值升序，深度升序)
    using P = pair<long long,int>;
    priority_queue<P, vector<P>, greater<P>> pq;
    for (auto w : weights) pq.emplace(w, 0);

    // 补 0：使 (n' - 1) % (k - 1) == 0，才能合成一棵 k 叉树
    // 注：题目保证 k >= 2
    while ((int(pq.size()) - 1) % (k - 1) != 0) pq.emplace(0LL, 0);

    __int128 total = 0; // 用 128 位累加更安全
    int max_depth = 0;

    while ((int)pq.size() > 1) {
        long long sum = 0;
        int dep = 0;
        for (int i = 0; i < k; ++i) {
            auto [w, d] = pq.top(); pq.pop();
            sum += w;
            dep = max(dep, d);
        }
        total += sum;
        pq.emplace(sum, dep + 1);
    }
    if (!pq.empty()) max_depth = pq.top().second;

    return {(long long)total, max_depth};
}

# 数学

# 常见数学 STL 函数

vector<int> nums = {1, 2, 3, 4, 5};
long long sum = accumulate(nums.begin(), nums.end(), 0LL);
long long product = accumulate(nums.begin(), nums.end(), 1LL, [](long long acc, int x){return acc * x;});

sqrt(x) // 开方，非负数
cbrt(x) // 开立方


ceil(x) //x 为浮点数；向上取整到最近整数，3.2->4.0, -3.8->-3.0
floor(x) // 向下取整 3.8 -> 4.0
round(x) //四舍五入
trunc(x) // 保留整数

fmod(x, y) //x,y 为浮点数；计算 x 除以 y 的余数，
fmod(7.5, 2.5) = 2.5

hypot(x, y) // x,y 为坐标值；计算√(x²+y²)
x,y为坐标值；计算√(x²+y²)	hypot(3, 4) = 5.0

# 判断素数

// 判断整数 n 是否是素数
bool isPrime(int n) {
    for (int i = 2; i * i < n; i++)
        if (n % i == 0) return false;
    return true;
}

# 快速幂 /gcd/ 逆元

ll M = 1e9 + 7; 
template<typename T>T MO(T x){return (x%M+M)%M;} 

// 取模快速幂
int qPower(int a, int n, int mod){ // 按位展开
    int ans = 1, base = a;
    while(n){
        if(n & 1) ans *= base; // 若位为 1，说明有权重，需要乘上
        base *= base;
        ans %= mod; base %= mod;
        n >>= 1; // 右移 1 位
    }
    return ans;
 }

// 费马小定理
 int qBigPower(int a, int n, int p){  
     // n 为大规模指数，注意这里可能需要改为高精度取模形式
    return qPower(a, n % (p - 1), p);
 }


using int64 = long long;
using i128 = __int128_t;

// a*b % mod，64 位安全
static inline uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t mod){
    return (uint64_t)((i128)a * b % mod);
}

static inline int64 mod_pow(int64 a, int64 e, int64 mod){
    uint64_t x = (a%mod+mod)%mod, r = 1%mod;
    while(e){ if(e&1) r = mul_mod(r, x, mod); x = mul_mod(x, x, mod); e >>= 1; }
    return (int64)r;
}

static inline int64 exgcd(int64 a, int64 b, int64 &x, int64 &y){
    if(!b){ x= (a>=0?1:-1); y=0; return llabs(a); }
    int64 x1,y1; int64 g=exgcd(b,a%b,x1,y1); x=y1; y=x1-(a/b)*y1; return g;
}

// 逆元：若 gcd(a,mod)=1 返回 inv，否则返回 -1
static inline int64 mod_inv(int64 a, int64 mod){
    int64 x,y; int64 g=exgcd(a,mod,x,y);
    if(g!=1) return -1;
    x%=mod; if(x<0) x+=mod; return x;
}


int C[N + 10][N + 10];

// 使用杨辉三角预处理组合数，对 M-1 取模
void init() {
    for (int i = 0; i <= N; ++i) {
        C[i][0] = (1 >= M-1) ? 0 : 1;
        for (int j = 1; j <= i; ++j) {
            C[i][j] = trim_pow(C[i - 1][j - 1] + C[i - 1][j]);
        }
    }
}

# gcd，lcm

// 最大公约数
long gcd(long a, long b) {
    if (a < b) {
        // 保证 a > b
        return gcd(b, a);
    }
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// 最小公倍数
long lcm(long a, long b) {
    // 最小公倍数就是乘积除以最大公因数
    return a * b / gcd(a, b);
}

# 1-n 整除 a,b,c 的个数

// 计算 [1..num] 之间有多少个能够被 a 或 b 或 c 整除的数字
long f(int num, int a, int b, int c) {
    long setA = num / a, setB = num / b, setC = num / c;
    long setAB = num / lcm(a, b);
    long setAC = num / lcm(a, c);
    long setBC = num / lcm(b, c);
    long setABC = num / lcm(lcm(a, b), c);
    // 集合论定理：A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C
    return setA + setB + setC - setAB - setAC - setBC + setABC;
}

# 统计二进制字符串 1 的个数

Brian Kernighan

int e ;
int cnt = 0;
while(e>0){
  e = e&(e-1); //每一次消除一个 1，两种情况，10，01
  cnt++;
}

# 组合数

int C[MAXN][MAXN];
 int cal_c(int n, int m){
    for(int i = 0; i <= n; ++i) C[i][0] = C[i][i] = 1; // 初始化
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j < i; ++j)
            C[i][j] = C[i-1][j-1] + C[i-1][j];
    return C[n][m];
 }

# 错排组合（不在原来位置上）

int F[MAXN];
 int f(int n) {
    F[1] = 0; F[2] = 1;
    for(int i = 3; i <= n; ++i)
        F[i] = (n-1) * F[i-1] + (n-1) * F[n-2];
    return F[n];
 }

# 卡特兰数（前缀不越界问题）

n 对括号，任何前缀中 “右括号数 ≤ 左括号数”。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;

long long qpow(long long a,long long e){
    long long r=1;
    while(e){ if(e&1) r=r*a%MOD; a=a*a%MOD; e>>=1; }
    return r;
}
struct Comb {
    vector<long long> fac, ifac;
    Comb(int N){ 
        fac.resize(N+1); ifac.resize(N+1);
        fac[0]=1; for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%MOD;
        ifac[N]=qpow(fac[N], MOD-2);
        for(int i=N;i>0;i--) ifac[i-1]=ifac[i]*i%MOD;
    }
    long long C(int n,int k){
        if(k<0||k>n) return 0;
        return fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;
    }
};
long long catalan(int n, Comb& cb){
    if(n==0) return 1;
    long long cn = cb.C(2*n,n);
    long long inv = qpow(n+1, MOD-2);
    return cn*inv%MOD;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    Comb cb(2*n);
    cout<<catalan(n, cb)<<"\n";
}

# 快速求行列式（高斯消元）

// 行列式计算 (高斯消元法)
// 输入：n×n 矩阵 a
// 输出：det(a) mod MOD
int det_mod(vector<vector<int>> a, int MOD) {
    int n = (int)a.size();
    long long det = 1;
    for (int i = 0; i < n; i++) {
        // 找到当前列的主元（非零）
        int pivot = -1;
        for (int j = i; j < n; j++) {
            if (a[j][i] % MOD != 0) {
                pivot = j; break;
            }
        }
        if (pivot == -1) return 0; // 该列全 0 → det=0

        // 如果主元不在第 i 行，交换行
        if (pivot != i) {
            swap(a[pivot], a[i]);
            det = (MOD - det) % MOD; // 交换行 → det 取负
        }

        // 当前主元
        int inv_pivot = 1;
        {
            long long base = a[i][i];
            // 模逆元（费马小定理，MOD 必须是质数）
            long long exp = MOD - 2, res = 1;
            base = (base % MOD + MOD) % MOD;
            while (exp) {
                if (exp & 1) res = res * base % MOD;
                base = base * base % MOD;
                exp >>= 1;
            }
            inv_pivot = (int)res;
        }

        det = det * (a[i][i] % MOD + MOD) % MOD;

        // 消去下面的行
        for (int j = i + 1; j < n; j++) {
            if (a[j][i] == 0) continue;
            long long factor = 1LL * a[j][i] * inv_pivot % MOD;
            for (int k = i; k < n; k++) {
                a[j][k] = (a[j][k] - factor * a[i][k]) % MOD;
                if (a[j][k] < 0) a[j][k] += MOD;
            }
        }
    }
    return (det % MOD + MOD) % MOD;
}

# 往年题目

# 理发师（全排）

一个序列决定，另一个序列决定

struct P { 
    int a; 
    int b; 
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T; 
    cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<P> cus(n);
        for (int i = 0; i < n; ++i) {
            cin >> cus[i].a >> cus[i].b;
        }
        vector<int> order(n);
        for (int i = 0; i < n; ++i) {
            order[i] = i; 
        }
        ll minTotalTime = INT_MAX;
        do {
            ll Global_washTime = 0; 
            ll Global_cutTime = 0; 
            for (int i = 0; i < n; ++i) {
                // 洗发：直接累加
                Global_washTime += cus[order[i]].a;
                // 剪发：必须等顾客洗完 (washTime)，同时剪发机也要空闲 (cutTime)
                Global_cutTime = max(Global_washTime, Global_cutTime) + cus[order[i]].b;
            }
            if (Global_cutTime < minTotalTime) {
                minTotalTime = Global_cutTime;
            }
        } while (next_permutation(order.begin(), order.end())); // 生成下一个排列，
        cout << minTotalTime << endl;
    }
    return 0;
}

# 数数 - 线性二维 DP

对于每个数据点你需要处理 T 组查询。每次查询输入 n ，求长度为 n 的字符串个数，要求：
 每一位为 1 , 2 或 3 ;
 不得连续出现 3 个相同的数字。

#include <bits/stdc++.h>
using namespace std;

using u64 = unsigned long long;
const u64 MOD = 10000000000ULL;        // 1e10, 末 10 位
const u64 LIM = 10000000000000000ULL;  // 1e16
const u64 HALF_LIM = LIM / 2;          // 5e15

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    if (!(cin >> T)) return 0;
    vector<int> q(T);
    int maxn = 0;
    for (int i = 0; i < T; ++i) { cin >> q[i]; maxn = max(maxn, q[i]); }

    if (maxn == 0) { // 保险：如果有 n=0（一般不会），按 0 处理
        for (int i = 0; i < T; ++i) cout << 0 << '\n';
        return 0;
    }

    vector<u64> tail(maxn + 2, 0);      // f mod 1e10
    vector<u64> small(maxn + 2, 0);     // 仅当 f < 1e16 时保存完整值
    vector<char> small_ok(maxn + 2, 0); // 是否保存了完整值

    // 初值
    if (maxn >= 1) { tail[1] = 3; small[1] = 3; small_ok[1] = 1; }
    if (maxn >= 2) { tail[2] = 9; small[2] = 9; small_ok[2] = 1; }

    // 递推：f[n] = 2*f[n-1] + 2*f[n-2]
    for (int n = 3; n <= maxn; ++n) {
        tail[n] = (2 * tail[n - 1] + 2 * tail[n - 2]) % MOD;

        if (small_ok[n - 1] && small_ok[n - 2]) {
            u64 s = small[n - 1] + small[n - 2]; // 至多约 1e16，u64 够
            if (s < HALF_LIM) {                  // 2*s < 1e16
                small[n] = 2 * s;
                small_ok[n] = 1;
            }
        }
    }

    // 输出
    for (int n : q) {
        if (small_ok[n]) {
            cout << small[n] << '\n';
        } else {
            cout << "......" << setw(10) << setfill('0') << tail[n] << '\n';
        }
    }
    return 0;
}

# 论文 - 拓扑排序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1'000'000'007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<ll> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<vector<int>> G(n + 1);
    vector<int> indeg(n + 1, 0), outdeg(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;     // u 是 v 的前置：u -> v
        G[u].push_back(v);
        ++indeg[v];
        ++outdeg[u];
    }

    // ---------- 拓扑排序（Kahn） ----------
    queue<int> q;
    for (int i = 1; i <= n; ++i) if (indeg[i] == 0) q.push(i);

    vector<int> topo; topo.reserve(n);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (int v : G[u]) {
            if (--indeg[v] == 0) q.push(v);
        }
    }
    // 题目保证有解：topo.size()==n

    // ---------- 正向 DP：最早开始时间 f ----------
    vector<ll> f(n + 1, 0);
    for (int u : topo) {
        for (int v : G[u]) {
            f[v] = max(f[v], f[u] + a[u]);
        }
    }
    ll T = 0;  // 最早完成时间
    for (int i = 1; i <= n; ++i) T = max(T, f[i] + a[i]);

    // ---------- 逆向 DP：最晚开始时间 g（不拖慢 T） ----------
    const ll INF = (ll)4e18;
    vector<ll> g(n + 1, INF);
    // 无后继的点：最晚开始 = T - a[i]
    for (int i = 1; i <= n; ++i) if (outdeg[i] == 0) g[i] = T - a[i];

    // 逆拓扑序传递：g[u] = min_{v in succ(u)} g[v] - a[u]
    for (int idx = (int)topo.size() - 1; idx >= 0; --idx) {
        int u = topo[idx];
        if (outdeg[u] > 0) {
            ll LF = INF;
            for (int v : G[u]) LF = min(LF, g[v]);
            g[u] = min(g[u], LF - a[u]);
        }
        // 保证区间 [f[i], g[i]] 非空
        if (g[u] < f[u]) g[u] = f[u];
    }

    // ---------- 结果 ----------
    cout << T << "\n";

    long long ans = 1;
    for (int i = 1; i <= n; ++i) {
        long long ways = (g[i] - f[i] + 1) % MOD;
        if (ways < 0) ways += MOD;
        ans = (ans * ways) % MOD;
    }
    cout << ans << "\n";
    return 0;
}

# 依赖 DP - 考试

这其实就是一个 状态转移 / 动态规划 问题，甚至可以看成是一个 有向图路径计数。
把科目编号：
0 = 计原 (C)
1 = 网原 (N)
2 = 信原 (I)
3 = 操统 (O)
转移规则：
C → N
I → O
N → C 或 O
O → N 或 I
于是我们可以写一个 DP：
设 dp[i][s] = 第 i 次考试时是科目 s 的方案数。

清华机考

# 通用

# 算法复杂度

# 内存预算大小

# 优乐美

# 边

# 优先队列 / 大顶堆

# 并查集

# 前缀和

# ST 表

# 全排列

# 单调栈

# 滑动窗口

# 二分查找

# 线段树

# add - max/min/sum

# chmax/chmin - max/min/sum

# k-th 问题

# STL

# vector

# Stack, Queue

# 排序

# map 使用方法

# 字符串与转换

# KMP

# 大暴力

# 回溯算法

# 树枝剪枝

# 同层剪枝

# 组合问题

# n 皇后（n!）

# DFS

# 岛屿与染色问题

# 迷宫路径

# 贪心

# 区间问题

# 不相交区间

# 区间选点

# 区间覆盖

# 线性基 (异或和最大）

# 动态规划

# 朴素的子问题思考法 DFS+ 记忆化

# 背包 DP

# 01 背包

# 完全背包

# 多重背包

# 线性 DP

# 最大子段和

# 最大两段子段和

# 最大 m 段子序和

# 受限子序列最大和

# 环状最大和

# 环状最大双子段和

# 环最大合并

# 最大子矩阵和

# 最长上升子序列

# 最长公共子序列

# 树状 DP

# 其他题目

# 树

# 基本定义和构树

# 树的直径，中心，重心

# 最近公共祖先

# 虚树

# 树的分治

# 点分治

# 树同构

# 区间 k-th

# 图

# BFS

# 01 BFS

# 基本上都是在求最短路时用到，边权有特点：有的边权为 0！边权为 0 的放到队首，多用这样的节点，边权为其他正数（常见为 1）的放到队尾，少用这样的节点。

# 01bfs：O (m) 堆优化 dijkstra：O (mlongn)

# DFS

# AOV 网 - 拓扑排序，AOE

# 环检测

# DAG 有向无环图

# 最短路

# Dijkstra 单源最短

# Bellman_ford 单源负权最短

# 单源有限最短路

# 二分图匹配匈牙利 Kuln 算法