#include <bits/stdc++.h>
using namespace std;
struct T{
    long long num;
    bool t;
}a[200005];
bool cmp(T a,T b){
    if(a.num==b.num)return a.t<b.t;
    return a.num<b.num;
}
int main(){
    int m,x;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%lld%lld",&a[i*2-1].num,&a[i*2].num);
        a[i*2-1].t=0;
        a[i*2].t=1;
    }
    sort(a+1,a+m*2+1,cmp);
    int cs=1;
    long long l=0;
    for(int i=2;i<=m*2;i++){
        if(a[i].t==0){
        	cs++;
		}else{
			cs--;
		}
        if(cs==0){
            l+=a[i].num-a[1].num+1;
            a[1].num=a[i+1].num;
        }
    }
    cout<<l;
    return 0;
}

并查集：

int p[N];
void init(int n){ // 初始化， p[i]=i 自己是自己的父亲
    for(int i=0; i<=n; i++) p[i]=i;
}
int find(int u){ // 查询 u 的父亲
    return u==p[u] ? u:p[u]=find(p[u]);
}
void merge(int u,int v){ // 合并 u，v，使得其为同一个家族
    int a=find(u), b=find(v);
    p[a] = b;
}

Copy

最小生成树：

• kruskal：每次选择权值最小的边，利用并查集进行合并。

int dp[N][M];
void solve1(){
	
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			dp[i][j]=dp[i-1][j];
			if(j>=v[i]){
				dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
			}			
		}
	}
	cout<<dp[n][m]<<endl;
}

void solve2(){//滚动数组 优化 
	int dp[2][M]={0};
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			dp[i&1][j]=dp[(i-1)&1][j];
			if(j>=v[i]){
				dp[i&1][j]=max(dp[i&1][j],dp[(i-1)&1][j-v[i]]+w[i]);
			}
		}
	}
	cout<<dp[n&1][m]<<endl;
}
void solve3(){//状态压缩 
	int dp[M]={0};
	for(int i=1;i<=n;i++){
		for(int j=m;j>=v[i];j--){
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	cout<<dp[m]<<endl;
}

小小地球，竟然有两百多个国家，这难道不是对嬴先生的背叛吗？？！！

冷知识：中国海警在世界海军中排第九

完全背包

#include<bits/stdc++.h>
using namespace std;
int w[210],c[210],s[210];
int n,m;
int dp[210];
int main(){
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&w[i],&c[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			
			if(j>=w[i]){
				dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
			}
			
			
		}
		
		
	}
	
	
	
	
	
	printf("max=%d",dp[m]);
	
	
	
	
	
	
	
	
	return 0;
}

01背包

#include<bits/stdc++.h>
using namespace std;
int w[210],c[210],s[210];
int n,m;
int dp[210];
int main(){
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&w[i],&c[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=1;j--){
			
			if(j>=w[i]){
				dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
			}
			
			
		}
		
		
	}
	
	
	
	
	
	printf("%d",dp[m]);
	
	
	
	
	
	
	
	
	return 0;
}

混合背包

#include<bits/stdc++.h>
using namespace std;
int w[1010],c[1010],s[1010];
int n,m;
int dp[1010];
int main(){
	scanf("%d%d",&n,&m);
	
		
	
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&w[i],&c[i],&s[i]);
		if(s[i]==-1){
			for(int j=m;j>=1;j--){
			
			if(j>=w[i]){
				dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
			}
			
			
		}
			
			
			
		}
		if(s[i]==0){
			
			for(int j=1;j<=m;j++){
			
			if(j>=w[i]){
				dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
			}
			
			
		}
		
		} 
		if(s[i]>0){
			for(int j=m;j>=1;j--){
			for(int k=1;k<=s[i]&&j>=k*w[i];k++){
				
				
				dp[j]=max(dp[j],dp[j-k*w[i]]+c[i]*k);
			
			}
			
				
			
			
		}
			
			
		}
		
		
		
		
	}
	
	
	
	
	
	printf("%d",dp[m]);
	
	
	
	
	
	
	
	
	return 0;
}

滑雪

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
struct deta{
	int x,y,a;
}t[N*N];
bool cmp(deta a,deta b){
	return a.a>b.a;
}
int n,m,cnt,ans,a[N][N],dp[N][N];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			cnt++;
			t[cnt].a=a[i][j];
			t[cnt].x=i;
			t[cnt].y=j;
		}
	}
	sort(t+1,t+1+cnt,cmp);
	for(int i=1;i<=cnt;i++){
		dp[t[i].x][t[i].y]=max(dp[t[i].x][t[i].y],1);
		for(int k=0;k<4;k++){
			int tx=t[i].x+dx[k];
			int ty=t[i].y+dy[k];
			if(tx<=n&&ty<=m&&tx>0&&ty>0){
				if(t[i].a>a[tx][ty]){
					dp[tx][ty]=max(dp[t[i].x][t[i].y]+1,dp[tx][ty]);
				}	
			}
			
		}
		ans=max(ans,dp[t[i].x][t[i].y]);
	}
	cout<<ans;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=2501,M=6201,INF=0x3f3f3f3f;

int n,m,s,t;
int G[N][N],w[N];
int sl,tl,wl;

void dijkstra(){
	vector<long long >dis(N,10e18);
	vector<bool >st(N,0);
	dis[s]=0;
	for(int i=1;i<=n;i++){
		int u=-1;
		for(int j=1;j<=n;j++){
			if(!st[j] && (u==-1 || dis[u] > dis[j])) u =j;
		}
		if(u==-1)break;
		st[u]=1;
		for(int j=1;j<=n;j++){
			int v=j,w=G[u][j];
			dis[v]=min(dis[v],dis[u]+w);
		}
	}
	printf("%lld",dis[t]);
}

int main(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	memset(G,0x3f,sizeof G);
	
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&sl,&tl,&wl);
		G[sl][tl] = G[tl][sl] = min(G[sl][tl],wl);
	}
	dijkstra();
	
	return 0;
}

push法

#include<bits/stdc++.h>
using namespace  std;
const int N=25100;
struct node{
	int v,nxt,w;
}e[62100];
int cnt,head[N];
void add(int a,int b,int c){
	cnt++;
	e[cnt].v=b;
	e[cnt].nxt=head[a];
	e[cnt].w=c;
	head[a]=cnt;
}
int n,m,s,t,a,b,c,dij[N],vis[N],fom[N];
int main(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);
	}
	queue<int>q;
	memset(dij,127,sizeof(dij));
	dij[s]=0;
	q.push(s);
	vis[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(dij[u]+e[i].w<dij[v]){
				dij[v]=dij[u]+e[i].w;
				if(!vis[v])q.push(v);
			}
		}
	}
	cout<<dij[t];
	return 0;
}


SPFA算法
void SPFA(){
	vector<long long>dis(N,1e18);
	vector<bool>st(N,0);
	queue<int>q;
	q.push(1),dis[1]=0,st[1]=1;
	while(q.size()){
		int u=q.front();q.pop(),st[u]=0;
		for(auto it:G[u]){
			int v=it.first,w=it.second;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(!st[v])q.push(v),st[v]=1;
			}
		}
	}
	for(int i=2;i<=n;i++)printf("%lld\n",dis[i]);
}

Floyd算法

void Floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(flo[i][j]>flo[i][k]+flo[k][j]){
					flo[i][j]=flo[i][k]+flo[k][j]
				}
			}
		}
	}
}

单链表模板
/head 存储链表头节点 e[] 存储节点的值 ne[] 存储节点的next指针
//index 记录当前已经用到了哪个节点，相当于地址，用于创建节点
const int N = 100010;//看情况给大小
int head, e[N], ne[N], index;
//初始化
void init()
{
head = -1;//表示空集
index = 0;
}
//在链表头插入一个数a--相当于创建一个数据为a的节点头插链表
void insert(int a)
{
e[index] = a;
ne[index] = head;
head = index++;//记得index要向后走
}
//头删
void remove()
{
//不存在节点
if (head == -1)
return;
head = ne[head];
}
//插到下标k后面//如果向插到下标k前面
void insert_k(int k, int a)
{
e[index] = a;
ne[index] = ne[k];
ne[k] = index++;
}
//将下标k后面的点删除
void remove_k(int k)
{
ne[k] = ne[ne[k]];
}
//遍历
void ergodic()
{
for (int i = head; i != -1; i = ne[i])
cout << e[i] << ' ';
}

双链表模板：
// e[] 存储节点的值 l[] 存储节点的pre指针 r[]存放节点的next指针
//index 记录当前已经用到了哪个节点，相当于地址，用于创建节点
const int N = 100010;//看情况给大小
int e[N], l[N], r[N], index;
//初始化
void init()
{
//0是head指针，1是tail指针, 0头节点右指针指向1尾节点，1尾节点的左指针指向0头节点，形成闭
环
r[0] = 1, l[1] = 0;
index = 2;//要从2开始了
}
//在节点k右边插入一个数a//在k左边插入一个数a 即为 insert(l[k], a);
void insert(int k, int a)
{
e[index] = a;
l[index] = k;
r[index] = r[k];
l[r[k]] = index;
r[k] = index++;
}
//删除节点k
void remove(int k)
{
l[r[k]] = l[k];
r[l[k]] = r[k];
}

栈模板
const int N = 100010;
//栈
int st[N];
//tt维护栈顶，tt == 0时是栈底，栈底不存数据
int tt = 0;
//插入
void insert(int a)
{
st[++tt] = a;
}
//删除
void remove()
{
tt--;
}
//栈顶数值
int top()
{
return st[tt];
}
//判空
bool empty()
{
if (tt == 0)
return true;//空
else
return false;//不为空
}

单调栈模板
int tt = 0;
//伪代码，具体看题目
for (int i = 1; i <= n; i++)
{
//check是处理逻辑，满足条件就出栈
while (tt && check(st[tt], i))
{
tt--;
}
st[++tt] = i;
}

五.队列
维护对头和队尾
const int N = 100010;
//队列
int q[N];
//对头，队尾
int hh = 0, tt = -1;
//向队尾插入一个数
void insert(int a)
{
q[++tt] = a;
}
//从队头弹出一个数
void pop()
{
hh++;
}
//返回队头的值
int front()
{
return q[hh];
}
//判空
bool empty()
{
if (hh <= tt)
return false;//不为空
else
return true;
}

六.循环队列
也就多了个循环，队列满时直接改个方向
//hh表示队头，tt表示队尾的后一个位置
const int N = 100010;
int q[N];
int hh = 0, tt = 0;
//向队尾插入一个元素
void insert(int a)
{
q[tt++] = a;
//队满，循环改向
if (tt == N)
tt = 0;
}
//从队头弹出一个元素
void pop()
{
hh++;
if (hh == N)
hh = 0;
}
//返回队头的值
int front()
{
return q[hh];
}
//判空
bool empty()
{
if (hh == tt)
return true;//空
else
return false;//不为空
}

七.单调队列
单调队列（Monotonic Queue）是一种数据结构，通常用于解决一些需要维护一组数据中的最大值或最
小值的问题（比如滑动窗口中的最大值和最小值）。单调队列可以支持在队列两端进行插入和删除操
作，并且保持队列中的元素是单调递增或单调递减的。
单调队列的主要特点是在插入元素时，会将比当前元素小的元素从队列尾部删除，以保持队列的单调性
质。这样可以确保队列头部始终是当前队列中的最大值或最小值。
在实际应用中，单调队列常用于求滑动窗口中的最大值或最小值等问题，可以在O(N)的时间复杂度内解
决这类问题。
单调队列的基本操作包括：
1. 在队尾插入元素，并保持队列的单调性；
2. 在队头删除元素；
3. 获取队列的头部元素（最大值或最小值）。
单调队列可以通过双端队列（Deque）来实现，具体实现方式可以根据具体问题的需求选择单调递增队
列或单调递减队列。
接下来用数组来模拟实现单调队列：
模板：
const int N = 100010;
//队列
int q[N];
//队头，队尾
int hh = 0, tt = -1;
//伪代码
for (int i = 0; i < n; i++)
{
//队头是否滑出窗口
while (hh <= tt && check_out(q[hh]))
hh++;
//入队列要保持单调
while (hh <= t && check(q[tt], i))
tt--;
q[++tt] = i;
}

二、环形队列四要素
队空条件：front = rear
队满条件：(rear+1)%MaxSize = front
进队e操作：rear = (rear+1)%MaxSize; 将e放在rear处
出队操作：front = (front+1)%MaxSize; 取出front处元素e

一、树状数组概括
树状数组是一个查询和修改复杂度都为log(n)的数据结构。主要用于数组的单点修改&&区间求和，另外
一个拥有类似功能的是线段树。
具体区别和联系如下：
1.两者在复杂度上同级, 但是树状数组的常数明显优于线段树, 其编程复杂度也远小于线段树.
2.树状数组的作用被线段树完全涵盖, 凡是可以使用树状数组解决的问题, 使用线段树一定可以解决, 但是
线段树能够解决的问题树状数组未必能够解决.
3.树状数组的突出特点是其编程的极端简洁性, 使用lowbit技术可以在很短的几步操作中完成树状数组的
核心操作，其代码效率远高于线段树。
二、树状数组的应用
1.单点修改+区间查询
代码示例
int lowbit(int i)
{
return i & -i;//或者是return i-(i&(i-1));表示求数组下标二进制的非0最低位所表示的值
}
void update(int i,int val)//单点更新
{
while(i<=n){
C[i]+=val;
i+=lowbit(i);//由叶子节点向上更新树状数组C，从左往右更新
}
}
int sum(int i)//求区间[1,i]内所有元素的和
{
int ret=0;
while(i>0){
ret+=C[i];//从右往左累加求和
i-=lowbit(i);
}
return ret;
}

理解树状数组的重点
C[i]代表子树的叶子节点的权值之和，如图可以知道：
C[1]=A[1];
C[2]=A[1]+A[2];
C[3]=A[3];
C[4]=A[1]+A[2]+A[3]+A[4];
C[5]=A[5];
C[6]=A[5]+A[6];
C[7]=A[7];
C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];
首先是区间查询（求和）：
利用C[i]数组，求A数组中前i项和，举两个栗子：
①i=7，前7项和：sum[7]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]；
而C[4]=A[1]+A[2]+A[3]+A[4]；C[6]=A[5]+A[6]；C[7]=A[7]；可以得到：sum[7]=C[4]+C[6]+C[7]。
数组下标写成二进制：sum[(111)]=C[(100)]+C[(110)]+C[(111)]；
②i=5，前5项和：sum[5]=A[1]+A[2]+A[3]+A[4]+A[5]；
而C[4]=A[1]+A[2]+A[3]+A[4]；C[5]=A[5]；可以得到：sum[5]=C[4]+C[5]；
数组下标写成二进制：sum[(101)]=C[(100)]+C[(101)]；
细细观察二进制，树状数组追其根本就是二进制的应用，结合代码演示一下代码过程：
int sum(int i)//求区间[1,i]所有元素的和
{
int ret=0;
while(i>0){
ret+=C[i];//从右往左区间求和
i-=lowbit(i);
}
return ret;
}

然后单点更新：
int sum(int i)//求区间[1,i]所有元素的和
{
int ret=0;
while(i>0){
ret+=C[i];//从右往左区间求和
i-=lowbit(i);
}
return ret;
}
7(111) ans+=C[7]
5(101) ans+=C[5]
当我们修改A数组中某个值时，应当如何更新C数组呢？回想一下，区间查询的过程，再看一下上文中列
出的过程。这里声明一下：单点更新实际上是不修改A数组的，而是修改树状数组C，向上更新区间长度
为lowbit(i)所代表的节点的值。
void update(int i,int val)//更新单节点的值
{
while(i<=n){
C[i]+=val;
i+=lowbit(i);//由叶子节点向上更新a数组
}
}
//可以发现 更新过程是查询过程的逆过程
//由叶子结点向上更新C[]数组

总结
树状数组的重点就是利用二进制的变化，动态地更新树状数组。
树状数组的每一个节点并不是代表原数组的值，而是包含了原数组多个节点的值。
所以在更新A[1]时需要将所有包含A[1]的C[i]都加上val这也就利用到了二进制的神奇之处。
如果是更新A[i]的值，则每一次对C[i] 中的 i 向上更新，即每次i+=lowbit(i),这样就能C[i] 以及C[i] 的所有
父节点都加上val。
反之求区间和也是和更新节点值差不多，只不过每次 i-=lowbit(i)

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

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

const int maxn=1000010;

int n,q;
long long sum[maxn<<2],add[maxn<<2];

void Pushup(int rt){
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt){
	//sum[rt]
	if(l==r){
		//¸³Öµ sum[rt]
//		sum[rt]=a[l];
		scanf("%lld",&sum[rt]);
		return;
	} 
	int m=(l+r)>>1;
	//l,m,rt<<1
	build(lson);
	build(rson);
	Pushup(rt); 
}
void Add(int l,int r,int rt,int v){
	add[rt]+=v;
	sum[rt]+=(long long)v*(r-l+1);
}
void Pushdown(int l,int r,int rt,int m){
	if(add[rt]==0) return;
	Add(lson,add[rt]);
	Add(rson,add[rt]);
	add[rt]=0;
}
void update(int L,int R,int v,int l,int r,int rt){
	if(L<=l&&r<=R){
		Add(l,r,rt,v);
		return;
	}
	int m=(l+r)>>1;
	Pushdown(l,r,rt,m);
	if(L<=m) update(L,R,v,lson);
	if(m<R) update(L,R,v,rson);
	Pushup(rt);
}

long long query(int L,int R,int l,int r,int rt){
//	cout<<"AA "<<l<<" "<<r<<" "<<rt<<" "<<sum[rt]<<endl;
	if(L<=l&&r<=R){
		return sum[rt];
	}
	int m=(l+r)>>1;
	long long res=0; 
	Pushdown(l,r,rt,m);
	if(L<=m) res+=query(L,R,lson);
	if(m<R) res+=query(L,R,rson);
	Pushup(rt);
	return res;
}

int main(){
	scanf("%d%d",&n,&q);
	build(1,n,1);
	int op,a,b;
	while(q--){
		scanf("%d%d%d",&op,&a,&b);
		if(op==1){
			update(a,a,b,1,n,1);
		}else{
			printf("%lld\n",query(a,b,1,n,1));
		}
	}
	return 0;
}