---
title: "02-题目模板"
created: 2025-11-28
tags:
  - 算法
---


> 📚 考场速抄的总模板：`#include <bits/stdc++.h>` 开头，typedef、方向数组、inf 一应俱全，往下是 30 级算法的模板代码，按注释分节。完整 .cpp 文件见本组 assets/template.cpp。无穷大取 0x3f3f3f3f 的原理见 [[04-刷题小贴士]]。
# template

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long 蓝桥杯用不了signed main
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;

//----------------------- 30 级算法模板 ----------------------
// dfs | bfs

//------------- dfs三种枚举 -------------
// 1、指数型枚举（子集枚举）
void dfs_subset(int u,int n,vector<int>& nums,vector<int>& st){
	if(u==n){
		for(int i=0;i<n;i++)
			if(st[i]==1)	cout<<nums[i]<<" ";
		cout<<endl; 
		return;
	}
	
	st[u]=2;//不选 
	dfs_subset(u+1,n,nums,st);
	st[u]=0;
	
	st[u]=1;//选 
	dfs_subset(u+1,n,nums,st);
	st[u]=0;
} 

// 2、全排列枚举
void dfs_permutation(vector<int>& nums){
	sort(nums.begin(), nums.end()); //（需預先排序）
	do{
		for(auto v:nums) cout<<v<<" ";
        cout << endl;
	}while(next_permutation(nums.begin(),nums.end()));
}

// 3、组合型枚举(C(n, m)) 
void dfs_combination(int u,int start,int n,int m,vector<int>& nums,vector<int>& way){
	if(u+(n-start)<m)	return;
	if(u==m){
		for(int i=0;i<m;i++)	cout<<way[i]<<" ";
		cout<<endl;
		return;
	}
	for(int i=start;i<n;i++){
		way[u]=nums[i];
		dfs_combination(u+1,i+1,n,m,nums,way);
		way[u]=0;
	}
}

//----------------- 简单图 ----------------
//--------- 方向数组定义 -----------
const int dx4[] = {-1, 0, 1, 0};  // 上右下左
const int dy4[] = {0, 1, 0, -1};

const int dx8[] = {-1,-1,0,1,1,1,0,-1};  // 8方向
const int dy8[] = {0,1,1,1,0,-1,-1,-1};

const int dxKnight[] = {-2,-1,1,2,2,1,-1,-2};  // 日字形
const int dyKnight[] = {1,2,2,1,-1,-2,-2,-1};

//----------- 合法性检查 -----------
template<int n, int m>
bool isValid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
//    return x >= 1 && x <= n && y >= 1 && y <= m; // 1起
//	  return x >= 0 && x <= n+1 && y >= 0 && y <= m+1; //染色括一圈 
}

//-------------- 读图 --------------
template<int N, int M>
void readGrid(int n,int m,char (&g)[N][M]) {
    for(int i=0;i<n;++i) {
        string s;cin>>s;
        for(int j=0;j<m;++j)
            g[i][j]=s[j];
    }
}

template<int N, int M>
void readGridWithSpace(int n,int (&g)[N][M]) {
    cin.ignore();
    for(int i=0;i<n;++i){
        string s; getline(cin,s);
        for(int k=0,j=0;k<s.size();k++){
            if(s[k]!=' '){
            	g[i][j++]=s[k]-'0';
			}
        }
    }
}

//------------- DFS模板 -------------
template<int N, int M>
class DFSSolver {
    char g[N][M];
    bool vis[N][M];
    int n, m;
    
    void dfs(int x, int y) {
        // 终止条件处理
        // ...
        
        for(int i=0;i<4;++i) {
            int nx=x+dx4[i],ny=y+dy4[i];
            if(isValid<N, M>(nx, ny) && !vis[nx][ny] && g[nx][ny] == '.') {
                vis[nx][ny] = true;
                dfs(nx,ny);
                vis[nx][ny] = false;  // 根据需求决定是否回溯
            }
        }
    }
    
public:
    void solve() {
        cin>>n>>m;
        readGrid(n, m, g);
        memset(vis,0, sizeof vis);

        vis[0][0]=true;
        dfs(0,0);
    }
};

//------------- BFS模板 -------------
template<int N, int M>
class BFSSolver {
    int g[N][M], d[N][M], pre[N][M];
    const char dirs[4] = {'U','R','D','L'};
    int n,m;
    
    void printPath(int x, int y) {
        if(x==0 && y==0) return;
        int p=pre[x][y];
        int px=x-dx4[p],py=y-dy4[p];
        printPath(px, py);
        cout<<dirs[p];
    }
    
public:
    void solve() {
        cin >> n >> m;
        readGridWithSpace(n, g);
        memset(d, -1, sizeof d);
        queue<PII> q;
        
        q.push({0, 0});
        d[0][0] = 0;
        
        while(!q.empty()) {
            auto cur = q.front(); q.pop();
            int x=cur.first,y=cur.second;
            
//            if(x==targetx && y==targety){
//            	//dosomething
//            }
            
            for(int i = 0; i < 4; ++i) {
                int nx=x+dx4[i],ny=y+dy4[i];
                if(isValid<N, M>(nx, ny) && d[nx][ny] == -1 && g[nx][ny] == 0) {
                    d[nx][ny] = d[x][y] + 1;
                    pre[nx][ny] = i;
                    q.push({nx, ny});
                }
            }
        }
        printPath(n-1, m-1);
    }
};

//---------- 洪水填充模板 ------------
template<int N, int M>
class FloodFill {
    char g[N][M];
    bool vis[N][M];
    int n, m, cnt;
    
    void dfs(int x, int y) {
        for(int i = 0; i < 8; ++i) {  // 8方向填充
            int nx = x + dx8[i], ny = y + dy8[i];
            if(isValid<N, M>(nx, ny) && !vis[nx][ny] && g[nx][ny] == '#') {
                vis[nx][ny] = true;
                dfs(nx, ny);
            }
        }
    }
    
public:
    void solve() {
        cin >> n >> m;
        readGrid(n, m, g);
        cnt = 0;
        memset(vis, 0, sizeof vis);
        
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                if(g[i][j] == '#' && !vis[i][j]) {
                    vis[i][j] = true;
                    dfs(i, j);
                    ++cnt;
                }
        cout << "连通块数量: " << cnt << endl;
    }
};

//---------------------- 八皇后问题 -------------------------
/*
x,y
(0,0) (0,1) (0,2) (0,3) (0,4)
(1,0) (1,1) (1,2) (1,3) (1,4)
(2,0) (2,1) (2,2) (2,3) (2,4)
(3,0) (3,1) (3,2) (3,3) (3,4)
(4,0) (4,1) (4,2) (4,3) (4,4)

x+y
(0) (1) (2) (3) (4)
(1) (2) (3) (4) (5)
(2) (3) (4) (5) (6)
(3) (4) (5) (6) (7)
(4) (5) (6) (7) (8)

n-x+y
(5) (6) (7) (8) (9)
(4) (5) (6) (7) (8)
(3) (4) (5) (6) (7)
(2) (3) (4) (5) (6)
(1) (2) (3) (4) (5)

正对角线 x+y  反对角线： n-x+y或者x-y+n 
*/
class NQueens {
    static const int N = 20;
    char g[N][N];
    bool col[N], dg[2*N], udg[2*N];
    int n;
    
    void dfs(int u) {
        if(u == n) {
            for(int i = 0; i < n; ++i) puts(g[i]);
            puts("");
            return;
        }
        
        for(int i = 0; i < n; ++i) {
            if(!col[i] && !dg[u+i] && !udg[n - u + i]) {
                g[u][i] = 'Q';
                col[i] = dg[u+i] = udg[n - u + i] = true;
                dfs(u + 1);
                col[i] = dg[u+i] = udg[n - u + i] = false;
                g[u][i] = '.';
            }
        }
    }
    
public:
    void solve() {
        cin >> n;
        for(int i = 0; i < n; ++i)
            fill(g[i], g[i]+n, '.');
        dfs(0);
    }
};

/*
	DFSSolver<100, 100>().solve();
    BFSSolver<100, 100>().solve();
    FloodFill<100, 100>().solve();
    NQueens().solve();
*/

//------------------------ 100 级算法模板 ---------------------
// dp 

// ----------------- 背包问题 -----------------
/*
	01背包	逆序枚举体积	f[0]=0	每个物品选一次
	完全背包	正序枚举体积	f[0]=0	物品无限选
	多重背包	拆解后逆序枚举	f[0]=0	二进制拆分优化
	二维费用	双逆序枚举	f[0][0]=0	双重限制条件
	分组背包	组→体积→物品	f[0]=0	每组选一个
	恰好装满(max)	常规顺序	f[0]=0, 其他-INF	确保状态合法性
	恰好装满(count)	常规顺序	g[0]=1, 其他0	空包为唯一初始合法状态
	至少装j(min)	常规顺序	f[0]=0, 其他INF	用max处理负数体积
*/

 /*---------- 01背包 ------------
特点：每个物品选一次
状态转移：f[j] = max(f[j], f[j-v]+w) (逆序枚举)

int f[MAXV];
memset(f, 0, sizeof f);
for(int i=1; i<=n; i++)
    for(int j=m; j>=v[i]; j--)
        f[j] = max(f[j], f[j-v[i]]+w[i]);
*/

/*---------- 完全背包 ----------
特点：物品无限选
状态转移：f[j] = max(f[j], f[j-v]+w) (正序枚举)

int f[MAXV];
memset(f, 0, sizeof f);
for(int i=1; i<=n; i++)
    for(int j=v[i]; j<=m; j++)
        f[j] = max(f[j], f[j-v[i]]+w[i]);
*/

/*---------- 二维费用背包 ---------- 
限制条件：体积+重量双重限制 → 三维状态

int f[MAXV1][MAXV2];
memset(f, 0, sizeof f);
for(int i=1; i<=n; i++)
    for(int j=m1; j>=v1[i]; j--)
        for(int k=m2; k>=v2[i]; k--)
            f[j][k] = max(f[j][k], f[j-v1[i]][k-v2[i]] + w[i]);
*/

/*---------- 分组背包 ---------- 
每组选一个 → 三重循环顺序：物品组→体积→组内物品

int f[MAXV], v[N][N], w[N][N], s[N];
memset(f, 0, sizeof f);
for(int i=1; i<=n; i++) // 枚举组
    for(int j=m; j>=0; j--) // 枚举体积
        for(int k=0; k<s[i]; k++) // 枚举组内物品
            if(j >= v[i][k])
                f[j] = max(f[j], f[j-v[i][k]] + w[i][k]);
*/           

/*----------方案数统计 ----------
属性：count → 注意初始化和转移条件

int f[MAXV] = {0}, g[MAXV] = {0};
g[0] = 1; // 初始状态方案数为1

for(int i=1; i<=n; i++)
    for(int j=m; j>=v[i]; j--){
        int maxv = max(f[j], f[j-v[i]] + w[i]);
        int cnt = 0;
        if(maxv == f[j]) cnt += g[j];
        if(maxv == f[j-v[i]] + w[i]) cnt += g[j-v[i]];
        f[j] = maxv;
        g[j] = cnt % MOD;
    }

// 统计最大价值对应方案数
int res = 0, maxw = *max_element(f, f+m+1);
for(int j=0; j<=m; j++)
    if(f[j] == maxw) res = (res + g[j]) % MOD;
    
*/

/*----------- 具体方案追踪 -----------
逆序推导路径 → 通过状态转移反推选择

bool selected[N] = {false};
for(int i=n, j=m; i>=1; i--)
    if(j >= v[i] && f[i][j] == f[i-1][j-v[i]] + w[i]){
        selected[i] = true;
        j -= v[i];
    }
*/

//----------- 初始化策略 -----------
/*恰好装满（最大值）
初始：f[0]=0，其他为-INF → 确保状态合法性

int f[MAXV];
memset(f, 0xcf, sizeof f); // -INF
f[0] = 0;
for(int i=1; i<=n; i++)
    for(int j=m; j>=v[i]; j--)
        f[j] = max(f[j], f[j-v[i]] + w[i]);
*/

/*恰好装满（方案数）
初始：g[0]=1，其他为0 → 仅空包为合法初始状态

int g[MAXV] = {0};
g[0] = 1;
for(int i=1; i<=n; i++)
    for(int j=m; j>=v[i]; j--)
        g[j] = (g[j] + g[j-v[i]]) % MOD;
*/

/*至少装j（最小值）
允许j-v为负数 → 用max(j-v,0)处理

int f[MAXV];
memset(f, 0x3f, sizeof f); // INF
f[0] = 0;
for(int i=1; i<=n; i++)
    for(int j=m; j>=0; j--)
        f[j] = min(f[j], f[max(j-v[i], 0)] + w[i]);
*/   

// ----------------- 线性dp -----------------
/*
	数字三角形	逆序递推，取max/min	O(n2)	金字塔型路径规划
	矩形单路径	二维DP，右/下转移	O(nm)	网格路径最优化
	矩形双路径	三维状态压缩（步数k）	O(n3)	资源重复利用问题
	基本LIS	双重循环比较	O(n2)	序列特征分析
	权值和LIS	在长度基础上累加权值	O(n2)	带权序列优化
	双向LIS	正反两次DP求极值	O(n2)	山峰型序列分析
	贪心优化LIS	维护单调队列+二分查找	O(nlogn)	大规模序列处理
	最少划分上升子序列数	维护多个子序列的结尾值	O(nlogn)	任务调度问题
*/ 

/*-------- 正三角形路径最大值 -------- 
状态定义：f[i][j]表示从底边到(i,j)的最大路径和
转移方程：f[i][j] += max(左下值, 右下值)

for(int i = n-1; i >= 1; i--){ // 从底向上递推
    for(int j = 1; j <= i; j++){
        f[i][j] += max(f[i+1][j], f[i+1][j+1]);
    }
}
cout << f[1][1]; // 顶点即为最大值
*/

/*----------- 矩形路径处理 ----------- 
特点：只能向右或向下移动

// 单路径最大值
for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
        f[i][j] = max(f[i-1][j], f[i][j-1]) + w[i][j];
    }
}
cout << f[n][m];

// 双路径最大值（路径不重复）
int f[N*2][N][N]; // 使用步数k压缩状态
for(int k=2; k<=n+m; k++){ // 总步数从2开始（起点(1,1)算1步）
    for(int i=1; i<k && i<=n; i++){ // 第一条路径行号
        for(int j=1; j<k && j<=n; j++){ // 第二条路径行号
            int val = w[i][k-i];
            if(i != j) val += w[j][k-j]; // 非重复点才累加
            f[k][i][j] = max({
                f[k-1][i][j],     // 都向右
                f[k-1][i-1][j],   // 路径1向下，路径2向右
                f[k-1][i][j-1],   // 路径1向右，路径2向下
                f[k-1][i-1][j-1]  // 都向下
            }) + val;
        }
    }
}
cout << f[n+m][n][n]; // 终点状态
*/


/*----------- 基本LIS（长度） -----------
时间复杂度：O(n2) 朴素解法

int res = 0;
for(int i=1; i<=n; i++){
    f[i] = 1; // 初始化为自身长度
    for(int j=1; j<i; j++){
        if(a[j] < a[i]) 
            f[i] = max(f[i], f[j]+1);
    }
    res = max(res, f[i]);
}
cout << res;
*/

/*----------- 最大权和LIS -----------
状态定义：f[i]表示以a[i]结尾的最大子序列和

int res = 0;
for(int i=1; i<=n; i++){
    f[i] = w[i]; // 初始为自身权值
    for(int j=1; j<i; j++){
        if(a[j] < a[i])
            f[i] = max(f[i], f[j] + w[i]);
    }
    res = max(res, f[i]);
}
*/

/*---------- 双向LIS（山峰型） ----------- 
求：先上升后下降的最长子序列长度

// 正向LIS
for(int i=1; i<=n; i++){
    f_up[i] = 1;
    for(int j=1; j<i; j++)
        if(a[j] < a[i]) 
            f_up[i] = max(f_up[i], f_up[j]+1);
}

// 逆向LIS（处理下降部分）
for(int i=n; i>=1; i--){
    f_down[i] = 1;
    for(int j=n; j>i; j--)
        if(a[j] < a[i]) 
            f_down[i] = max(f_down[i], f_down[j]+1);
}

// 合并结果
int res = 0;
for(int i=1; i<=n; i++)
    res = max(res, f_up[i] + f_down[i] - 1);
*/

/*---------- 贪心+二分优化LIS ---------- 
时间复杂度：O(nlogn)

int len = 0; // 当前最大长度
int q[N]; // 维护上升序列
for(int i=1; i<=n; i++){
    int l=0, r=len;
    while(l < r){ // 找第一个>=a[i]的位置
        int mid = (l+r) >> 1;
        if(q[mid] >= a[i]) r = mid;
        else l = mid + 1;
    }
    q[r] = a[i]; // 替换或追加
    if(r == len) len++;
}
cout << len;
*/

/*---------- 最少划分上升子序列数 ---------- 
贪心策略：维护多个上升子序列的结尾值

已有的单调栈只需要用一个栈顶元素表示 可以组成一个数组(单调) 
每个数看能不能放在已有的栈里 且贪心的是栈顶离自己最近的
用二分找里自己最近的栈顶 若没有 就新开一个栈
最后看栈的数量 也就是数组的长度 
int q[N],cnt;
for(int i=1;i<=n;i++){
    int l=0,r=cnt;
    while(l<r){
        int mid=l+r>>1;
        if(q[mid]>=w[i])
            r=mid;
        else
            l=mid+1; 
    }
    if(q[r]<w[i]){
        r++;
    }
    cnt=max(cnt,r);
    q[r]=w[i];
} 
cout<<cnt;
*/


//----------------------- 1000 级算法模板 ----------------------
// dp ↑| 二分

//----- |-----  第一个 >= target 的位置 => lower_bound(nums.begin(), nums.end(), target)
int findLeft(vector<int>& nums,int target){
	int l=0,r=nums.size();
	while(l<r){
		int mid=l+r>>1;
		if(nums[mid]>=target)		r=mid;
		else	l=mid+1;
	}
	return r;
} 

//-----| -----  最后一个 <= target 的元素位置 => upper_bound(nums.begin(), nums.end(), target) - 1
int findRight(vector<int>& nums,int target){
	int l=0,r=nums.size();
	while(l<r){
		int mid=l+r+1>>1;
		if(nums[mid]<=target)		l=mid;
		else 	r=mid-1;
	}
	return r;
}

//------------------------ 1e5 级算法模板 -----------------------
// 贪心 | 排序 | set、map、heap | 二分 ↑

//------------- 排序与比较 -------------
//  单关键字 
/* 
	sort(v.begin(), v.end());
	sort(v.begin(), v.end(), greater<int>());
	
	priority_queue<int> maxheap;
	priority_queue<int,vector<int>,greater<int>> minheap;
*/

// 多关键字 
struct Task {
    int priority; // 优先级（值越大越重要）
    int duration; // 耗时（值越小越好）
    string name;

    // 方法1：重载运算符（固定排序规则）
    // 默认排序规则：先按优先级降序，再按耗时升序
    bool operator<(const Task& rhs) const {
        if(priority != rhs.priority) 
            return priority > rhs.priority; // 降序
        return duration < rhs.duration;  // 升序
    }
};

// 方法2：自定义比较器（灵活调整规则）
struct TaskComparator {
    bool operator()(const Task& a, const Task& b) {
        if(a.priority != b.priority)
            return a.priority < b.priority; // 升序
        return a.duration > b.duration;     // 降序
    }
};

/*
使用示例：
	vector<Task> tasks;
	
	// 使用重载运算符排序（默认规则）
	sort(tasks.begin(), tasks.end()); 
	
	// 使用自定义比较器排序（不同规则）
	sort(tasks.begin(), tasks.end(), TaskComparator());
	
	// 优先队列使用说明
	priority_queue<Task> pq1; // 使用operator<，大顶堆（高优先级在前）
	priority_queue<Task, vector<Task>, TaskComparator> pq2; // 使用自定义规则
*/

/*
	.push();
	
	.top();
	
	.pop();
	
	.size();
	
	.empty();
	
	while(!pq.empty()){
		cout<<pq.top()<<" ";
		pq.pop();
	}
*/ 


//--------------------------哈希相关 STL容器特性对比 -------------------------
/*
| 容器           | 排序 | 唯一性 | 查找复杂度 | 适用场景                     |
|----------------|------|--------|------------|------------------------------|
| set            | 有序 | 唯一   | O(logn)    | 需要有序且不重复的元素集合   |
| multiset       | 有序 | 可重复 | O(logn)    | 需要有序的可重复集合         |
| unordered_set  | 无序 | 唯一   | O(1)       | 快速查找且不关心顺序         |
| map            | 有序 | 键唯一 | O(logn)    | 键值对有序存储               |
| multimap       | 有序 | 键重复 | O(logn)    | 一键对应多值的有序存储       |
| unordered_map  | 无序 | 键唯一 | O(1)       | 快速键值查找                 |

set:
	// 基本用法：
		set<int> s;
		s.insert(3); 
		if(s.find(3) != s.end())
		s.erase(3); 
		s.size();
		s.empty();
		for(auto c:s) 	cout<<c； 
		for(auto it = s.begin();it != s.end();it++)	 cout<<*it; 
		
	// 更改排序方式：
		set<int, greater<int>> descending_set = {5, 2, 7, 1}; // {7,5,2,1}
		
		struct Student {
		    string name;
		    int score;
		    
		    // 重载 < 运算符（默认用于set排序）
		    bool operator<(const Student& rhs) const {
		        return score > rhs.score; // 分数降序排列
		    }
		};
		
		set<Student> student_set; // 自动使用operator<排序
		student_set.insert({"Alice", 90});
		student_set.insert({"Bob", 85});
		
	// 快速去重并获取有序结果： 
		vector<int> nums = {5,3,5,1,3,7};
		set<int> unique_sorted(nums.begin(), nums.end());
		vector<int> result(unique_sorted.begin(), unique_sorted.end());
		
		相当于：
		sort(nums.begin(),nums.end());
		nums.erase(unique(nums.begin(),nums.end()),nums.end()); 
		
		//sort + unique + erase 的组合在性能上更优
	
	// 范围查询： 
		set<int> data = {10,20,30,40,50};
		// 查找 [25,45) 范围内的元素
		auto low = data.lower_bound(25);  // 第一个 >=25 的元素（30）
		auto high = data.upper_bound(45); // 第一个 >45 的元素（50）
		for (auto it = low; it != high; ++it) {
		    cout << *it << " "; 	// 30 40
		}

unordered_map:
	//基本用法：
		unordered_map<string, int> age_map;
	
		// 插入元素
			age_map["Alice"] = 25;
			age_map.insert({"Bob", 30});
		
		// 访问元素（需注意键是否存在）
			if(age_map.count("Alice")) {
			    cout << age_map.at("Alice");
			    // cout<< age_map["Alice"];
			}
		
		// 遍历所有键值对
			for(auto& [name, age] : age_map) { //c++17 比赛应该用不了 
			    cout << name << ": " << age << endl;
			}
			
			for(auto x : age_map){
				cout << x.first << ": " << x.second << endl;
			}
	 
*/



//------------------------ 1e6 级算法模板 -----------------------
// 双指针 | 并查集 | hash | KMP × | bitset

//------------- 双指针模板 ----------------
// 1：同向双指针（滑动窗口）
int slidingWindow(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    int left = 0, max_len = 0;
    
    for (int right = 0; right < nums.size(); ++right) {
        freq[nums[right]]++;
    
        while (freq.size() > k) { 
            if (--freq[nums[left]] == 0)
                freq.erase(nums[left]);
            left++;
        }
        max_len = max(max_len, right - left + 1);
    }
    return max_len;
}

// 2：对撞指针（两数之和）
bool twoSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int left = 0, right = nums.size()-1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return true;
        if (sum < target) left++;
        else right--;
    }
    return false;
}

// 3：序列匹配（判断子序列）
bool isSubsequence(string s, string t) {
    int i = 0;
    for (int j = 0; j < t.size() && i < s.size(); j++) {
        if (s[i] == t[j]) i++;
    }
    return i == s.size();
}

//---------------- 并查集 ----------------
struct DSU{
	
	vector<int> parent;
	
	DSU(int n){
		parent.resize(n+1);
		for(int i=0;i<=n;i++){
			parent[i]=i;
		}
	}
	
	int find(int x){
		if(parent[x]!=x)	
			parent[x]=find(parent[x]);
		return parent[x];
	}
	
	void unite(int x, int y) {
        int fx = find(x);
        int fy = find(y);
		if(fx!=fy){
			parent[fx]=fy; 
		}
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }
	 
};

/* 使用示例：
	DSU dsu(n);
	dsu.unite(a, b);
	if (dsu.connected(x, y)) {...}
*/


//---------------- 字符串哈希 ---------------
const int N6 = 1e6+10;
const int P = 131; 
class StringHash{
	private:
		ull h[N6];
		ull p[N6];
		int n;
	public:
		void init(const char* str ,int length){
			n=length;
			p[0]=1;
			for(int i=1;i<=n;i++){
				h[i]=h[i-1]*P+str[i];
				p[i]=p[i-1]*P;
			}
		} 
		
		ull get_hash(int l,int r) const {
			if(l>r || l<1 || r>n)	return 0;
			return h[r]-h[l-1]*p[r-l+1];
		}
}; 

/* 使用示例：
 	char s[N6];cin>>s+1;
    int len=strlen(s+1);
    StringHash hasher;
    hasher.init(s,len);
    
    int l1,r1,l2,r2;
    cin>>l1>>r1>>l2>>r2;
    bool match(hasher.get_hash(l1,r1) == hasher.get_hash(l2,r2));
    cout<<(match?"Yes":"No")<<endl;
*/

//--------------- bitset  ---------------
/* 
 * 基础用法：
 *	 把十进制数变成n位的二进制数 不足用0补位
 *   bitset<N> bs;       // 初始化N位全0
 *   bitset<N> bs(val);  // 用整型val初始化（十进制/十六进制）
 *   bitset<N> bs(str);  // 用"0101"格式字符串初始化
 */

// 示例：8位bitset操作
void bitset_demo() {
    const int N = 8;
    bitset<N> bs1(0b11011010);    // 二进制初始化
    bitset<N> bs2(218);           // 十进制初始化
    bitset<N> bs3("11011010");    // 字符串初始化

    // 位操作
    bs1.set(0);                   // 第0位置1 (从右数)
    bs1.reset(1);                 // 第1位置0
    bs1.flip(2);                  // 第2位取反
    bool bit = bs1.test(3);       // 检查第3位

    // 统计与转换
    int cnt = bs1.count();        // 1的个数
    string s = bs1.to_string();   // 转"01101011"格式
    unsigned long num = bs1.to_ulong(); // 转数值

    // 运算符重载
    auto bs_and = bs1 & bs2;      // 按位与
    auto bs_or = bs1 | bs2;       // 按位或
    auto bs_xor = bs1 ^ bs2;      // 按位异或
    bs1 <<= 2;                    // 左移2位
    bs1 >>= 1;                    // 右移1位

    // 全量操作
    bs1.set();                    // 所有位置1
    bs1.reset();                  // 所有位置0
    bs1.flip();                   // 所有位取反
}


//------------------------ 1e7 级算法模板 -----------------------
// 双指针 ↑ | kmp ↑ | 筛法 

//---------------- 线性筛 ---------------
const int N7=1e7+10; 
int primes[N7];
bool st_isPrime[N7];
int primes_cnt=0;
void get_primes(int n){ // 获得n以内的所有素数 
	for(int i=2;i<=n;i++){
		if(!st_isPrime[i]) 	primes[primes_cnt++]=i;
		for(int j=0;primes[j]<=n/i;j++){
			st_isPrime[primes[j]*i]=true;
			if(i%primes[j]==0)	break;
		}
	}
}

//------------------------ 1e9 级算法模板 -----------------------
// 判断质数 | 约数

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

set<int> divisors;
void get_divisors(int n){ //获得n的所有约数 
	divisors.clear();
	for(int i=1;i<=n/i;i++){
		if(n%i==0){
			divisors.insert(i);
			divisors.insert(n/i);
		}
	}
}

unordered_map<int,int> weight;
int calc_divisors_cnt(int n){ //计算n的约数个数 相当于divisors.size() 但适用于n非常大 甚至无法存的情况 
	weight.clear();
	int res=1;
	for(int i=2;i<=n/i;i++){
		while(n%i==0){
			weight[i]++;
			n/=i;
		}
	}
	if(n>1)	weight[n]++;
	for(auto x:weight)	res=res*(x.second+1);
	return res;
}


//------------------------ 1e18 级算法模板 -----------------------
// gcd | lcm | 快速幂 
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a; 
}

ll lcm(ll a, ll b) {
	return a / gcd(a,b) * b; 
} 

ll gcd(ll a,ll b, ll c){
	return gcd(gcd(a,b),c);
}

ll lcm(ll a,ll b,ll c){
	return lcm(lcm(a,b),c);
}


ll qmi(ll a,ll k,ll p){ // 求 a^k mod p 
	ll res=1%p;
	while(k){
		if(k&1)	res=res*a%p;
		k>>=1;
		a=a*a%p;
	}
	return res;
}

//------------------------ 1e18往上 级算法模板 -----------------------
// int_128 | 高精度模拟

// int->2e10   ll->9e19   int_128->1e38 

bool big_cmp(const vector<int>& A,const vector<int>& B){
	if(A.size()!=B.size())	return A.size()>B.size();
	for(int i=A.size()-1;i>=0;i--){
		if(A[i]!=B[i])	return A[i]>B[i];
	}
	return true;
}

vector<int> big_add(vector<int> A,vector<int> B){
	vector<int> C;
	int t=0;
	for(int i=0;i<A.size() || i<B.size();i++){
		if(i<A.size())	t+=A[i];
		if(i<B.size())	t+=B[i];
		C.push_back(t%10);
		t/=10;
	}
	if(t)	C.push_back(1);
	return C;
}

// A>B if(big_cmp(A,B)) auto C=big_sub(A,B) else auto C=big_sub(B,A) 补充负号 
vector<int> big_sub(vector<int> A,vector<int> B){
	vector<int> C;
	int t=0;
	for(int i=0;i<A.size();i++){
		t=A[i]-t;
		if(i<B.size())	t-=B[i];
		C.push_back((t+10)%10);
		t = t < 0 ? 1 : 0;
	}
	while(C.size()>1 && C.back()==0)	C.pop_back();
	return C;
}

vector<int> big_mul(vector<int> A,int b){
	vector<int> C;
	int t=0;
	for(int i=0;i<A.size() || t;i++){
		if(i<A.size())	t+=A[i]*b;
		C.push_back(t%10);
		t/=10;
	}
	while(C.size()>1 && C.back()==0)	C.pop_back();
	return C;
} 

vector<int> big_div(vector<int> A,int b,int& r){
	vector<int> C;
	r=0;
	for(int i=A.size()-1;i>=0;i--){
		r=r*10+A[i];
		C.push_back(r/b);
		r%=b;
	}
	reverse(C.begin(),C.end());
	while(C.size()>1 && C.back()==0)	C.pop_back();
	return C;
}

vector<int> big_mul_big(const vector<int>& A, const vector<int>& B) {
    vector<int> C(A.size()+B.size(), 0);
    for(int i = 0; i < A.size(); i++)
        for(int j = 0; j < B.size(); j++)
            C[i+j] += A[i] * B[j];
    
    for(int i = 0, t = 0; i < C.size(); i++) {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

vector<int> str2big(const string& s){
	vector<int> res;
	for(int i=s.size()-1;i>=0;i--){
		if(isdigit(s[i]))	res.push_back(s[i]-'0');
		else if(s[i]=='-' && i==0)	break;
	}
	while(res.size()>1 && res.back()==0)	res.pop_back();
	return res;
}

string big2str(const vector<int>& A){
	string res;
	for(int i=A.size()-1;i>=0;i--)	
		res+=to_string(A[i]);
	return res.empty()?"0":res; 
}

//--------------------------- other --------------------------
//----------日期问题 ---------
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool is_leap(int y){
	return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);
}
int get_days(int y,int m){
	return days[m]+(m==2 && is_leap(y));
}
void next_day(int &y,int &m,int &d){
	d++;
	if(d>get_days(y,m)){
		d=1;
		m++;
		if(m>12){
			m=1;
			y++;
		}
	}
}
bool check_date(int y,int m,int d){
	if(m<1 || m>12)	return false;
	if(d<1 || d>get_days(y,m))	return false;
	return true; 
}

/*
while((curYear < targetYear) ||
	  (curYear == targetYear && curMonth < targetMonth) ||
	  (curYear == targetYear && curMonth == targetMonth && curDay < targetDay)){
	dosomething();
	next_day(curYear,curMonth,curDay);	  
}

char buffer[10];
sprintf(buffer,"%04d%02d%02d",curYear,curMonth,curDay);
string s(buffer);
*/

//---------- 前缀和与差分 -----------
/* 
一维前缀和：
	s[0] = 0;
	for(int i=1; i<=n; i++) 
		s[i] = s[i-1] + a[i];
	查询 [l,r]：s[r] - s[l-1]

二维前缀和：
	s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
	查询 (x1,y1)-(x2,y2)：s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]

一维差分：
	void insert(int l, int r, int c) {
	    b[l] += c;
	    b[r+1] -= c;
	}
	初始化：for i insert(i,i,a[i])
	区间加：insert(l,r,c)
	求原数组：b[i] += b[i-1]

二维差分：
	void insert(int x1,int y1,int x2,int y2,int c) {
	    b[x1][y1] += c;
	    b[x2+1][y1] -= c;
	    b[x1][y2+1] -= c;
	    b[x2+1][y2+1] += c;
	}
	初始化：for i,j insert(i,j,i,j,a[i][j])
	区域加：insert(x1,y1,x2,y2,c)
	求原数组：b[i][j] += b[i-1][j] + b[i][j-1] - b[i-1][j-1]
*/


//---------------- 单调栈 ------------------
//-------- 最近问题 --------
/*
左侧最近的小于当前元素
	遍历方向：左 →右
	单调性：递增栈（栈顶最小）
	操作：若当前元素≤栈顶，弹出栈顶，直到栈顶更小，此时栈顶为结果，入栈当前元素
int stk[N], tt = 0;
for (int i = 0; i < n; i++) {
    while (tt && a[i] <= stk[tt]) tt--;
    ans[i] = tt ? stk[tt] : -1; // 记录结果
    stk[++tt] = a[i];
}

左侧最近的大于当前元素
	遍历方向：左→右
	单调性：递减栈（栈顶最大）
	操作：类似上述，条件改为a[i] >= stk[tt]
int stk[N], tt = 0;
for (int i = 0; i < n; i++) {
    while (tt && a[i] >= stk[tt]) tt--;
    ans[i] = tt ? stk[tt] : -1;
    stk[++tt] = a[i];
}

右侧最近的小于当前元素
	遍历方向：右→左
	单调性：递增栈
for (int i = n-1; i >=0; i--) {
	while (tt && a[i] <= stk[tt]) tt--;
	ans[i] = tt ? stk[tt] : -1;
	stk[++tt] = a[i];
}

右侧最近的大于当前元素
	遍历方向：右→左
	单调性：递减栈
for (int i = n-1; i >=0; i--) {
	while (tt && a[i] >= stk[tt]) tt--;
	ans[i] = tt ? stk[tt] : -1;
	stk[++tt] = a[i];
}	
*/


//------ 最远问题（结合二分） ------
/*
左侧最远的大于当前元素
	构造一个单调递增的序列
	若这个新加的数能保持递增趋势 说明不存在比它更大的数 没必要去找了 直接加进去 供后面的数去找
	如果不能保持递增趋势 就说明左边有一个比它更大的数 在这个已有的单调序列中二分找到
	
vector<int> stk;
//需要注意的一点是 stk存的是下标 
for(int i=1;i<=n;i++){
    //a[i]>a[stk.back()] 还是 a[i]>=a[stk.back()] 
    //加不加等号看题意
    //找严格小于它的数的话 这里加等号 意味着找到它自己 
    //找前面小于等于它的数的话 这里不加等号 
    if(stk.empty() || a[i]>=a[stk.back()]){//发现该元素比栈顶元素还大（保持单调递增）
        stk.push_back(i);//直接入栈
        ans[i]=i;//记录答案 可能求长度等等
    }
    else{//发现该元素不是最大  那么原单调序列里肯定存在一些比他大的数 二分找到最远的那个 
        int l=1,r=stk.size()-1; 
        while(l<r){
            int mid=l+r>>1;
            if(a[stk[mid]]>a[i])
                r=mid;
            else
                l=mid+1;
        }
        ans[i]=stk[r];
    }
}

左边最远的小于当前元素
	找最小的数 如果本身已经是最小了 就没必要找 直接加入单调栈保持单调性 
	如果自身不是最小 也不做什么踢出操作 直接在单调栈里找答案就行 只不过它也没必要加进去

vector<int> stk;
for(int i=1;i<=n;i++){
    if(stk.empty() || a[i]<a[stk.back()]){//只要改两处
        stk.push_back(i);
        ans[i]=i;
    }
    else{
        int l=0,r=stk.size()-1; 
        while(l<r){
            int mid=l+r>>1;
            if(a[stk[mid]]<a[i]) //只要改两处
                r=mid;
            else
                l=mid+1;
        }
        ans[i]=stk[r];
    }
}

右边 最远的 大于它的数
	从右边开始枚举罢了 1-n变成n-1即可
	找最远的大于 若该数是最大的 直接加入栈中 如果不是 再二分找一下

for(int i=n;i>=1;i--){//只需改循环
    if(stk.empty() || a[i]>a[stk.back()]){
        stk.push_back(i);
        ans[i]=i;
    }
    else{
        int l=0,r=stk.size()-1; 
        while(l<r){
            int mid=l+r>>1;
            if(a[stk[mid]]>a[i])
                r=mid;
            else
                l=mid+1;
        }
        ans[i]=stk[r];
    }
}

右边 最远的 小于它的数
	n-1 最小 若该数为最小 直接加入 否则 二分找
for(int i=n;i>=1;i--){
    if(stk.empty() || a[i]<a[stk.back()]){
        stk.push_back(i);
        ans[i]=i;
    }
    else{
        int l=0,r=stk.size()-1; 
        while(l<r){
            int mid=l+r>>1;
            if(a[stk[mid]]<a[i])
                r=mid;
            else
                l=mid+1;
        }
        ans[i]=stk[r];
    }
}

*/

//---------------- 单调队列 ------------------

/*
窗口的最小值
deque<int> q;
vector<int> res;
for (int i = 0; i < n; i++) {
    if (!q.empty() && i - q.front() >= k) q.pop_front();
    while (!q.empty() && a[i] <= a[q.back()]) q.pop_back(); //求最小 递增区间 若出现向下 出队
    q.push_back(i);
    if (i >= k-1) res.push_back(a[q.front()]);  //当前区间的最大值为队头
}

窗口最大值
while (!q.empty() && a[i] >= a[q.back()]) q.pop_back();

*/



//-------------- 区间合并 ---------------
/*
多次要对一个大区间的某些段做标记 可以暴力对每一段做标记 最后枚举整个区间 看是否有没标记过的 
很多时候也可以用差分 某段处理后就在该段++ 不过我们要的结果不在乎具体是多少 只是有值就1 没值就0 
然后对于暴力对每段做标记和差分的话 都会存在一个问题 有很多地方做了重复操作 
这个时候就可以使用区间合并进行优化 把能合并的区间都合并起来 再对他们去做操作 就可以省去一些重复功
对于合并操作 得分析一个问题 题目中诸如：13 45 这样的能不能合并 如果能 模版处就改成ed+1<range.first

核心步骤
	区间排序：按左端点升序排列。
	遍历合并：依次判断当前区间是否可合并到当前维护区间中，否则开启新区间

typedef pair<int,int> PII;
PII range[N];
int cnt;

range[cnt++]={l,r}; 
sort(range,range+cnt);

vector<PII> merged; // 存储合并后的区间
if (cnt == 0) {
    // 无区间处理
} else {
    int st = range[0].first, ed = range[0].second;
    for (int i = 1; i < cnt; i++) {
        // 判断是否可合并（允许相邻区间合并）
        if (range[i].first <= ed + 1) { 
            ed = max(ed, range[i].second);
        } else {
            merged.push_back({st, ed});
            st = range[i].first;
            ed = range[i].second;
        }
    }
    merged.push_back({st, ed}); // 加入最后一个区间
}
*/

//----------------- 数学 ----------------
// 转double -> a*1.0/b  
// 除法尽量变乘法
  
// 等差数列 
// a_n = a_1 + (n-1)d
// s_n = (n/2)(a_1+a_n) = (n/2)(2a_1 + (n-1)d) = na_1 + n(n-1)/2d

// 等比数列 
// a_n = a_1 * r^(n-1)
// s_n = a_1 * (1 - r^n) / 1-r   (r!=1)

// 计算几何
// 点斜式：y-y1=k(x-x1) 
// 截距式：y=kx+b
// double k = (double) (y2-y1) / (x2-x1);
// double b = (double) y1-k*x1
// double x = (double) (b2-b1) / (k1-k2);  

// round() 	四舍五入
// floor()	向下取整
// ceil()  	向上取整
// pow()   	指数幂   ldexp() 浮点数幂运算 
// sqrt()  	平方根
// log2() log10	对数

//----------------- 位运算 ----------------
// & 同真为真 其余为假 x&1相当于看x为多少
// if(x&1) 奇数    if((X&1)==0) 偶数
// | 同假为假 其余为真
// ^ 相同为0，不同为1    x^y^y等于什么都没做  若x==y 则x^y=0
// >>  x>>=1 相当于 x/=2   x>>=n 相当于 x/=2^n
// <<  x<<y 相当于x*2^y   3<<5 相当于 3*2^5    1<<y 相当于 2^y 


int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
   	
  
	return 0;
} 
```

---
⬅️ [[01-根据时间复杂度选择算法]] 🏠 [[00-算法]] ➡️ [[00-项目筑基|00-项目筑基]]