模板总结

CSP -j 复赛模板复习

一、 排序

1 快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
int n,a[100000+10];
int rannd(int l,int r){
	srand(rand());
	return rand()%(r-l+1)+l;
}
void qsort(int l,int r){
	int x=l,y=r,num=a[rannd(l,r)];
	while(x<=y){
		while(a[x]<num) ++x;
		while(a[y]>num) --y;
		if(x<=y) swap(a[x],a[y]),++x,--y;
	}
	if(x<r) qsort(x,r);
	if(y>l) qsort(l,y);
}
int main(){
	ios_base::sync_with_stdio(false);
	srand(time(0));
	cin>>n;
	for_each(&a[1],&a[n+1],[&](int &k){cin>>k;});
	qsort(1,n);
	for_each(&a[1],&a[n+1],[&](int &k){cout<<k<<' ';});
}

2 归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
int n,a[100000+10];
void msort(int l,int r){
	if(l>=r) return;
	msort(l,l+r>>1);
	msort((l+r>>1)+1,r);
	vector<int>v1,v2;
	for(int i=l;i<=l+r>>1;++i) v1.emplace_back(a[i]);
	for(int i=(l+r>>1)+1;i<=r;++i) v2.emplace_back(a[i]);
	vector<int> v3;
	int i,j;
	for(i=0,j=0;i<v1.size()&&j<v2.size();){
		if(v1[i]<v2[j]) v3.push_back(v1[i++]);
		else v3.push_back(v2[j++]);
	}
	while(i<v1.size()) v3.push_back(v1[i++]);
	while(j<v2.size()) v3.push_back(v2[j++]);
	for(int i=l,k=0;i<=r;++i,++k) a[i]=v3[k];
	return;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n;
	for_each(&a[1],&a[n+1],[&](int &k){cin>>k;});
	msort(1,n);
	for_each(&a[1],&a[n+1],[&](int &k){cout<<k<<' ';});
}

二、二分模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int a[114514],ans,n;
bool check(int k){
	return ans<k;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>ans;
	for(int i=1;i<=n;++i) cin>>a[i];
	int l=1,r=n,mid;
	while(l<r){
		mid=l+r>>1;
		if(check(mid)) l=mid+1;
		else r=mid;
	}
	cout<<l<<endl;
}

三、前缀和与差分

1 一维前缀和

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
int a[114514],n,q[114514];
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i],q[i]=a[i]+q[i-1];
	
}

2 二维前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//S[i, j] = 第i行j列格子左上部分所有元素的和
//以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：?
#include<bits/stdc++.h>
using namespace std;
int a[114][514],n,m,S[114][514],x1,x2,y1_,y2;
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>a[i][j];
			S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+a[i][j];
		}
	}
	cin>>x1>>x2>>y1_>>y2;
	cout<<S[x2][y2]-S[x1][y2]-S[x2][y1_]+S[x1][y1_]<<endl;
}

3 一维差分

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
int a[114514],s[114514],n;
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i],s[i]=a[i]-a[i-1];
}


4 二维差分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
#include<bits/stdc++.h>
using namespace std;
int a[114][514],n,m,s[114][514];
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		s[i][0]=s[i-1][m];
		for(int j=1;j<=m;++j){
			cin>>a[i][j];
			s[i][j]+=a[i][j];
			s[i][j+1]-=a[i][j];
			s[i+1][j]-=a[i][j];
			s[i+1][j+1]+=a[i][j];
		}
	}
	int x1,y1,x2,y2,c;
	cin>>x1>>y1>>x2>>y2>>c;
	s[x1][y1]+=c;
	s[x1][y2+1]-=c;
	s[x2+1][y1]-=c;
	a[x2+1][y2+1]+=c;
}


四、位运算

1
2
求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

五、离散化

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;
#define int long long
map<int,int>mp;
int n,a[114514];
signed main(){
	ios_base::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i],++mp[a[i]];
}

六、单调栈 单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//单调栈：P2947
#include<bits/stdc++.h>
#define N 114514
using namespace std;
struct node{
	int id,val;
}s[114514];
int n,a[114514],b[114514],top;
signed main(){
	ios_base::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		while(top>0&&s[top].val<a[i]){
			b[s[top].id]=i;
			top--;
		}
		s[++top].id=i;
		s[top].val=a[i];
	}
	while(top>0) b[s[top--].id]=0;
	for(int i=1;i<=n;++i) cout<<b[i]<<endl;
//	cout<<endl;
	return 0;
} 



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//单调队列：P1886 60pts
#include<bits/stdc++.h>
using namespace std;
const int maxn=114514;
struct node{
	int id,v;
}qwqwq1[maxn],qwqwq2[maxn];//qwqwq1:max qwqwq2:min \
queue -> qwqwq 应该也没什么问题吧qwq
int a[maxn],l1,l2,r1,r2,n,k;//l1,r1:qwqwq1 l2,r2:qwqwq2
signed main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>k;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=n;i++){
		while(l2<r2&&qwqwq2[r2-1].v>=a[i]) r2--;
		qwqwq2[r2].v=a[i];
		qwqwq2[r2].id=i;
		r2++;
		if(l2<r2&&i-qwqwq2[l2].id>=k) l2++;
		if(i>=k) cout<<qwqwq2[l2].v<<' ';
	}
	cout<<endl;
	for(int i=1;i<=n;i++){
		while(l1<r1&&qwqwq1[r1-1].v<=a[i]) r1--;
		qwqwq1[r1].v=a[i];
		qwqwq1[r1].id=i;
		r1++;
		if(l1<r1&&i-qwqwq1[l1].id>=k) l1++;
		if(i>=k) cout<<qwqwq1[l1].v<<' ';
	}
	cout<<endl;
	return 0;
}



七、树与图

1 邻接矩阵

1
2
3
4
5
6
//g[a][b]//存储边a→b
void add(int u,int v,int w){
	g[u][v]=g[v][u]=w;
}


2 邻接表

1
2
3
4
5
int h[N], e[N], ne[N], idx;//双向边*2 
//h头节点，e编号，ne下一节点下标  
void add(int a, int b) {//连接a,b 
    e[++idx] = b, ne[idx] = h[a], h[a] = idx;//采用头插法 
}

3 DFS

1
2
3
4
5
6
7
8
9
10
11
12
int h[N], e[N], idx, ne[N];
bool st[N];// 需要标记数组st[N]
void dfs(int u) {
    st[u] = true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            dfs(j);
        }
    }
}

4 BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int h[N], e[N], idx, ne[N];
bool st[N];
// int q[N];//模拟队列 
queue<int>q;
int bfs()
{
    // int hh=0,tt=0;//头节点 尾节点 
    while(q.size())//当我们的队列不为空时
    {
        int t=q.front();//取出队列头部节点
        for(int i=h[t];i;i=ne[i])//遍历t节点的每一个邻边
        {
            int j=e[i];
            if(!st[j])
            {
                q.push(j);//把j结点 压入队列
            }
        }
    }
}

5 dijkstra/堆优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
struct Edge{
	int to,next,val;
}edge[1919810];
int head[114514],n,m,s,idx;
inline void add(int u,int v,int val){
	++idx;
	edge[idx]={v,head[u],val};
	head[u]=idx;
}
array<int,114514> dijkstra(){
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
	q.push({0,s});
	array<int,114514> dis;
	dis.fill(0x3f3f3f3f);
	bool vis[114514];
	memset(vis,0,sizeof vis);
	dis[s]=0;
	while(!q.empty()){
		pair<int,int> now=q.top();
		q.pop();
		int now_num=now.second,now_val=now.first;
		if(dis[now_num]<now_val||vis[now_num]) continue;
		vis[now_num]=true;
		for(int to_idx=head[now_num];to_idx;to_idx=edge[to_idx].next){
			int new_val=edge[to_idx].val+now_val;
			if(new_val<dis[edge[to_idx].to]){
				dis[edge[to_idx].to]=new_val;
				q.push({new_val,edge[to_idx].to});
			}
		}
	}
	return dis;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,val;
		cin>>u>>v>>val;
		add(u,v,val);
	}
	auto ans=dijkstra();
	for(int i=1;i<=n;++i) cout<<ans[i]<<' ';
}


6 SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include "bits/stdc++.h"
using namespace std;
struct Edge{
	int to,next,w;
};
array<Edge,300000+10>edges;
array<int,200000+10> head,vis,dis;
int n,m,s,idx;
inline void add(int u,int v,int val){
	edges[++idx]={v,head[u],val};
	head[u]=idx;
}
void spfa(){
	queue<int>q;
	q.push(1);
	dis[1]=0;
	while(!q.empty()){
		int now=q.front();
		q.pop();
		++vis[now];
		if(vis[now]>n){
			cout<<"YES"<<endl;
			return;
		}
		for(int i=head[now];i;i=edges[i].next){
			if(dis[edges[i].to]>dis[now]+edges[i].w){
				q.push(edges[i].to);
				dis[edges[i].to]=dis[now]+edges[i].w;
			}
		}
	}
	cout<<"NO"<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--){
		head.fill(0);
		edges.fill({0,0,0});
		vis.fill(0);
		dis.fill(0x3f3f3f3f);
		cin>>n>>m;
		for(int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			add(u,v,w);
			if(w>=0) add(v,u,w);
		}
		spfa();
	}
}


7 kruscal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[20000+10],q,ans,cnt;
struct Edge{
	int from,to,val;
	friend bool operator < (const Edge &a,const Edge &b){
		return a.val<b.val;
	}
}edge[114514*2];
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;++i) cin>>edge[i].from>>edge[i].to>>edge[i].val;
	sort(&edge[1],&edge[m+1]);
	for(int i=1;i<=m;i++){
		int v1=edge[i].from,v2=edge[i].to;
		if(find(v1)==find(v2)) continue;
		ans+=edge[i].val,cnt++;
		fa[find(v1)]=fa[find(v2)];
		if(cnt==n-1) break;
	}
	if(cnt!=n-1) cout<<"orz"<<endl;
	else cout<<ans<<endl;
	return 0;
}


8 并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[20000+10],q;
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(x==y) continue;
		fa[find(x)]=find(y);
	}
	cin>>q;
	for(int i=1;i<=q;i++){
		int x,y;
		cin>>x>>y;
		if(find(x)==find(y)) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}


八 数学

1 线性筛素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int primes[N],cnt;
bool st[N];
void get_primes(int n)
{
    for(int i=2;i<=n;i++)//从2至n遍历 
    {
        if(!st[i])primes[cnt++]=i;//存储素数 
        for(int j=0;primes[j]<=n/i;i++)//primes[j]*i<=n
        {
            st[primes[j]*i]=true;//primes[j]是primes[j]*i的最小质因数 
            if(i%primes[j]==0)break;// prime[]数组中的素数是递增的,当i能整除prime[j]，那么i*prime[j+1]这个合数 肯定被prime[j]乘以某个数筛掉。
        }
    }
    return;
}

2 试除求约数

1
2
3
4
5
6
7
8
    
for (int i = 1; i <= x / i; i ++ )
   if (x % i == 0)
   {
       res.push_back(i);
       if (i != x / i) res.push_back(x / i);//x!=i*i
   }

3 快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
long long _pow_(long long a,long long x,long long p){ //a^b mod p
	if(x==0) return 1;
	long long t=_pow_(a,x/2,p)%p;
	t=(t*t)%p;
	if(x%2==1) t=(t*a)%p;
	return t;
}
int main(){
	long long a,b,p;
	scanf("%lld%lld%lld",&a,&b,&p);
	printf("%lld^%lld mod %lld=%lld",a,b,p,_pow_(a,b,p));
	return 0;
}


九 DP

1 序列DP——最长上升/下降子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int n,a[5000+10],f[5000+10];
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i];
	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);
	}
	int ans=0;
	for(int i=1;i<=n;++i) ans=max(ans,f[i]);
	cout<<ans<<endl;
	return 0;
}


2背包问题

01背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int n,vv;
int v[1000+10],w[1000+10],dp[1000+10];
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>vv;
	for(int i=1;i<=n;++i) cin>>v[i]>>w[i];
	for(int i=1;i<=n;++i){
		for(int j=vv;j>=v[i];--j){
			if(dp[j-v[i]]+w[i]>dp[j]) dp[j]=dp[j-v[i]]+w[i];
		}
	}
	cout<<dp[vv]<<endl;
	return 0;
}

完全背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int n,vv;
int v[1000+10],w[1000+10],dp[1000+10];
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>vv;
	for(int i=1;i<=n;++i) cin>>v[i]>>w[i];
	for(int i=1;i<=n;++i){
		for(int j=v[i];j<=vv;++j){
			if(dp[j-v[i]]+w[i]>dp[j]) dp[j]=dp[j-v[i]]+w[i];
		}
	}
	cout<<dp[vv]<<endl;
	return 0;
}

多重背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
int n,vv;
int v[100000+10],w[100000+10],dp[100000+10];
int n1,v1,w1,s1;
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n1>>vv;
	while(n1--){
		cin>>v1>>w1>>s1;
		int t1=1;
		while(s1>t1){
			v[++n]=v1*t1;
			w[n]=w1*t1;
			s1-=t1;
			t1<<=1;
		}
		v[++n]=v1*s1;
		w[n]=w1*s1;
	}
	for(int i=1;i<=n;++i){
		for(int j=vv;j>=v[i];--j){
			if(dp[j-v[i]]+w[i]>dp[j]) dp[j]=dp[j-v[i]]+w[i];
		}
	}
//	for(int i=1;i<=n;++i) cout<<v[i]<<' '<<w[i]<<' '<<dp[i]<<endl;
	cout<<dp[vv]<<endl;
	return 0;
}

混合背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
int n,vv;
int v[1000+10],w[1000+10],s[1000+10];
int dp[1000+10];
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>vv;
	for(int i=1;i<=n;++i) cin>>v[i]>>w[i]>>s[i];
	for(int i=1;i<=n;++i){
		if(s[i]==0){
			for(int j=v[i];j<=vv;++j){
				dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
			}
		}
		else{
			s[i]=abs(s[i]);
			for(int k=1;k<=s[i];++k)
			for(int j=vv;j>=v[i];--j){
				dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
			}
		}
	}
//	for(int i=1;i<=vv;++i) cout<<dp[i]<<endl;
	cout<<dp[vv]<<endl;
	return 0;
}

分组背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
int v,n,t=0,vv[1000+10],w[1000+10],a[100+10][100000+10],dp[1000000];
int main(){
    cin>>v>>n;
    for(int i=1;i<=n;i++){
        int tmp;
        cin>>vv[i]>>w[i]>>tmp;
        a[tmp][++a[tmp][0]]=i;
        t=max(tmp,t);
    }
    for(int tmp=1;tmp<=t;tmp++){
        for(int j=v;j>=0;j--){
            for(int i=1;i<=a[tmp][0];i++){
                if(j>=vv[a[tmp][i]]){
                    int tmp=a[tmp][i];
                    if(dp[j]<dp[j-vv[tmp]]+w[tmp]){
                        dp[j]=dp[j-vv[tmp]]+w[tmp];
                    }
                }
            }
        }
    }
    cout<<dp[v]<<endl;
    return 0;
}

二维费用背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int N, V, M;
    cin>>N>>V>>M;
    vector<vector<int>> dp(V+1,vector<int>(M+1, 0));
    vector<int> v(N+1), m(N+1),w(N+1);
    for (int i=1;i<=N;i++){
        cin>>v[i]>>m[i]>>w[i];
    }
    for(int i=1;i<=N;i++){
        for(int j=V;j>=v[i];j--){
            for(int k=M;k>=m[i];k--){
                dp[j][k]=max(dp[j][k],dp[j-v[i]][k-m[i]]+w[i]);
            }
        }
    }
    cout<<dp[V][M]<<endl;
    return 0;
}

3 区间DP

1
2
3
4
5
6
7
8
9
//合并问题
for(int len=2;len<=n;len++)
    for(int i=1;i<=n-len+1;i++)
    {
        int j=i+len-1;
    for(int k=i;k<j;k++)
    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]- s[i-1]);
    }

十 STL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
vector, 变长数组，倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序

pair<int, int>
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string，字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址

queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque, 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)

    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反
#总结
模板总结
https://lzj-blog.top/2023/10/13/模板总结/
作者
lzj
发布于
October 13, 2023
许可协议