学习视频笔记-Toy模板网

这篇具有很好参考价值的文章主要介绍了学习视频笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

基础算法

排序

快速排序

思想

1.确定分界点

2.调整区间

3.递归处理左右两段

最左为基准数

注意：&& i < j老是忘记，会死循环

while (a[j] >= temp && i < j) j--;

#include <stdio.h>
int a[101];

void quicksort( int left, int right) {
    int i, j, temp, t;
    if (left > right) return;

    temp = a[left];
    i = left;
    j = right;
    while (i != j) {
        while (a[j] >= temp && i < j) j--;
        while (a[i] <= temp && i < j) i++;

        if (i < j) {
            t = a[j];
            a[j] = a[i];
            a[i] = t;
        }
    }
    a[left] = a[i];
    a[i] = temp;

    quicksort(left, i - 1);
    quicksort(i + 1, right);
}

int main() {
    int N,i;
    scanf("%d", &N);
    
    for ( i = 1; i<=N;i++) {
        scanf("%d", &a[i]);
    }

    quicksort(1, N);

    for ( i = 1; i<= N; i++) {
        printf("%d ", a[i]);
    }

    return 0;
}

中间为基准数

[P1005 NOIP2007 提高组] 矩阵取数游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <stdio.h>
int a[100005];
void quicksort(int a[], int left, int right) {
    int i, j, temp, t;
    if (left >= right) return;// 递归跳出条件
    

    temp = a[(left+right)/2];// 采用中间位置的数作为支点
    i = left;
    j = right;
    while (i <= j) {
        while (a[j] > temp ) j--;// 从右往左，大于支点的数跳过
        while (a[i] < temp ) i++;// 从左往右，小于支点的数跳过

        if (i <= j) {
            t = a[j];
            a[j] = a[i];
            a[i] = t;
            i++;
			j--; 
        }
	}
// 注意：此时 j 一定小于 i
    quicksort(a, left, j);// 递归处理左边的数
    quicksort(a, i, right);// 递归处理右边的数
}

int main() {
    int N,i;
    scanf("%d", &N);
    for (i = 0; i < N; i++)
        scanf("%d", &a[i]);
        
    quicksort(a, 0, N - 1);

    for ( i = 0; i < N; i++) 
        printf("%d ", a[i]);

    return 0;
}

归并排序

思想

1.确定分界点

mid = (l+r)/2;

2.先递归，排序left，right

3.归并——合二为一

递归在归并排序中的运用是为了将原问题分解成更小的、容易解决的子问题，并通过逐步解决这些子问题，最终得到整体的解。

代码

#include <stdio.h>
#define N 1000010
int n;
int q[N], tmp[N];

void merge_sort(int q[], int l, int r) {
    if (l >= r)
        return;

    int mid = (l + r) / 2;

    //注意先递归
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r); 

    int k = 0, i = l, j = mid + 1;

    // 合并两个已排序的子数组
    while (i <= mid && j <= r) {
        if (q[i] <= q[j])
            tmp[k++] = q[i++];
        else
            tmp[k++] = q[j++];
    }

    // 将剩余的元素复制到临时数组
    while (i <= mid)
        tmp[k++] = q[i++];
    while (j <= r)
        tmp[k++] = q[j++];

    // 将有序的临时数组复制回原数组
    for (i = l, j = 0; i <= r; i++, j++)
        q[i] = tmp[j];
}

int main() {
    scanf("%d", &n);
    int i, j;

    // 读取输入数组
    for (i = 0; i < n; i++) {
        scanf("%d", &q[i]);
    }

    // 调用归并排序
    merge_sort(q, 0, n - 1);

    // 输出排序后的数组
    for (i = 0; i < n; i++) {
        printf("%d ", q[i]);
    }

    return 0;
}

二分

题目无解，但二分法一定有解

整数二分

视频基础算法1

模版：

重点在于判断check不满足时r和l哪一个移动为mid+1或mid-1

//区间[l,r]被划分为[l,mid]和[mid+1,r]时使用
int research_1(int l,int r)
{
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid)) r=mid; //check()判断mid是否满足性质 
		else l=mid+1;
	}
	return l; 
}

//区间[l,r]被划分为[l,mid-1]和[mid,r]时使用
int research_2(int l,int r)
{
	while(l<r)
	{
		int mid=(l+r+1)/2;
		if(check(mid)) l=mid; //check()判断mid是否满足性质 
		else r=mid-1;
	}
	return l; 
}

例题：数的范围

题目：
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。

第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。

接下来 q 行，每行包含一个整数 k，表示一个询问元素。

输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围
1≤n≤100000

1≤q≤10000

1≤k≤10000

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

代码：

#include <stdio.h>
#define N 100010
int n,m;
int q[N];

int main()
{
	scanf("%d%d",&n,&m);
	int i;
	for(i=0;i<n;i++) scanf("%d",&q[i]); //读取有序数组
	
	while(m--)
	{
		int x;
		scanf("%d",&x);  //要找的值
		
        //找第一个x的位置
		int l=0,r=n-1;
		while(l<r)
		{
			int mid=(l+r)/2;
			if(q[mid]>=x) r=mid;
			else l=mid+1;		
		}
		
        //先从二分左边找，找不到l移为mid+1,一直找不到一直移
        //移到最后l<r的条件不满足了，即已经是有序数组最后一位数
        //要是此时q[l]还是！=x则说明这数组里没这个数
		if(q[l]!=x)  printf("-1 -1\n"); //有序数组中不存在
        
		else //找到了
		{
			printf("%d ",l); //第一个x位置
			
            //找第二个x的位置
			int l=0,r=n-1;
            
			while(l<r)
			{
				int mid=(l+r+1)/2;
				if(q[mid]<=x) l=mid;
				else r=mid-1;
			}
			
			printf("%d",l);
		}		
	}	
	
	return 0;
}

浮点数二分

模板：

double bsearch_3(double l,double r)
{
	while(r-l>1e-8) //r和l之间的差值足够小，可以认定即为这个数
        //看之后输出保留几位小数，保留z位小数，则r-l>1e-(z+2)（至少加2）
	{
		double mid=(l+r)/2;
		if(check(mid)) r=mid; //check()判断mid是否满足性质 
		else l=mid;
	}
	return l; 
}

例题：开平方

题目描述

给定一个数，写出算法，将其开方，结果保留6位小数。

输入一个数(可以是小数)，输出结果为其平方根，结果保留6位小数

#include <stdio.h>

int main()
{
	double x;
	scanf("%lf", &x);
	double l=0,r=x;
	while(r-l>1e-8)
	{
		double mid=(l+r)/2;
		if(mid*mid>=x) r=mid;
		else l=mid;
	}
	printf("%.6f\n",l);  //保留z位小数，则r-l>1e-(z+2)
	
	return 0;
}

高精度

高精度 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

各数据类型取值范围

数据类型	数值范围
int	10⁹
long	10⁹
long long	10¹⁸

加法（逆序）

P1601 A+B Problem（高精） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思想

1.先用字符数组读取，把大整数的每一位存入数组,注意存入数组先存低位，即第0位存放个位

_{两个数相加可能会进位，这样子方便计算}

2.对应位相加，新数组对应位为和的取余，t/=10（大于10则t自动留了个1）

代码：

#include <stdio.h>
#include <string.h>
#define N 100010 //预处理只能用整数不能用1e6+10

int i,j;

void add(int A[], int B[], int C[]) {
    int t = 0;
    for ( i = 0; i < N; i++) { //注意这里新数组正序存放
        t += A[i]+B[i];
        C[i] = t % 10;
        t /= 10;
    }
}

int main() {
    char a[N], b[N];
    int A[N] = {0}, B[N] = {0}, C[N] = {0};

    scanf("%s",a);
    getchar();
    scanf("%s", b);

    int lenA = strlen(a);
    int lenB = strlen(b);

    for (i = lenA - 1, j = 0; i >= 0; i--, j++) A[j] = a[i] - '0';
    for (i = lenB - 1, j = 0; i >= 0; i--, j++) B[j] = b[i] - '0';

    add(A, B, C);

    int flag = 0;
    for (i = N - 1; i >= 0; i--) {
        if (C[i]) flag = 1;
        if (flag) printf("%d", C[i]);
    }

    if (!flag) printf("0");//确保输入为0 0时有输出为0
    

    return 0;
}

减法（逆序）

P2142 高精度减法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思想：

1.字符串读数据

2.逆序存放

3.比较两个数组大小，分情况结果是负数还是正数

4.用一个函数拿较大的数组减小数组

5.逆序输出

学习视频笔记,学习,音视频,笔记,c语言,算法

代码：

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define N 100010 //预处理只能定义为整数，1e6+10不可以

int i,j;

bool cmp(int A[],int B[],int len1,int len2){
	if(len1!=len2) return len1>len2; //如果数组A比B长，返回1，说明差值为正数，进入主函数if，反之差值会为负值进入else
	for(i=N-1;i>=0;i--){
		if(A[i]!=B[i]) return A[i]>B[i];
	}
	return true; //A和B完全相同的情况，用true也可以
}


void sub(int A[],int B[],int C[],int len1,int len2){
	int t=0;
	for(i=0;i<len1;i++){
		t=A[i]-t;
		if(i<len2) t-=B[i];	
		C[i]=(t+10)%10;
		if(t<0) t=1;
		else t=0;
	}
}

int main(){
	int A[N]={0},B[N]={0},C[N]={0};
	char a[N],b[N];
	scanf("%s",a);
	getchar();
	scanf("%s",b);
	
	int len1=strlen(a);
	int len2=strlen(b);
	
	for(i=len1-1,j=0;i>=0;i--,j++) A[j]=a[i]-'0'; 
	for(i=len2-1,j=0;i>=0;i--,j++) B[j]=b[i]-'0'; 
	
	int flag;
	if(cmp(A,B,len1,len2)){
		sub(A,B,C,len1,len2);
		flag=0; //flag不需要放在循环里面，最主要作用就是找到第一个不为0的数，之前的一串数据统一输出就是所得值
                //如果放在里面那么差值里可能会包含0就不会输出了
		for(i=N-1;i>=0;i--){
			if(C[i]) flag=1;
			if(flag) printf("%d",C[i]);	
		}	
	}else{
		sub(B,A,C,len2,len1); //注意数组长度也要跟着交换
		printf("-");
		flag=0;
		for(i=N-1;i>=0;i--){
			if(C[i]) flag=1;
			if(flag) printf("%d",C[i]);	
		}	
	}
	
	if(!flag) printf("0");
	
	return 0;
}

注意len1和len2不要定义为全局变量

~~虽然很方便写函数~~

但是在被减数位数小于减数时会出错

最好还是作为参数传递

乘法（逆序）

P1303 A*B Problem - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思想：

1.存储和之前加减法一样

2.按照正常乘法的顺序，将每一次乘积按位置写下来

3.位置完全对齐的数相加赋值给C[i](如图中的20和15)

4.从C[0]起若数值大于9往前进位

学习视频笔记,学习,音视频,笔记,c语言,算法

代码：

#include <stdio.h>
#include <string.h>

#define N 100010
int i,j;

void mul(int A[],int B[],int C[],int len1,int len2){
	for(i=0;i<len2;i++){
		for(j=0;j<len1;j++){
			C[i+j]+=A[j]*B[i];
		} 
	}
	for(i=0;i<len1+len2;i++){
		if(C[i]>9){
			C[i+1]+=C[i]/10;
			C[i]%=10;
		}
	}
}

int main(){
	int A[N]={0},B[N]={0},C[N]={0};
	char a[N],b[N];
	scanf("%s",a);
	getchar();
	scanf("%s",b);
	
	int len1=strlen(a);
	int len2=strlen(b);
	
	for(i=len1-1,j=0;i>=0;i--,j++) A[j]=a[i]-'0';
	for(i=len2-1,j=0;i>=0;i--,j++) B[j]=b[i]-'0';
	
	mul(A,B,C,len1,len2);
	
	int flag=0;
	for(i=N-1;i>=0;i--){
		if(C[i]) flag=1;
		if(flag) printf("%d",C[i]);
	}
	
	if(!flag) printf("0");
	return 0;
}

除法（正序）

按照除法运算法则从最高位开始除

因此正序存放就行

除数较小（<=10⁸）

代码：

#include <stdio.h>
#include <string.h>
#define N 100010
int i,j;

int devide(int A[],int b,int C[],int len){
	int t=0;
	for(i=0;i<len;i++){
		C[i]=(t*10+A[i])/b;  //商
		t=(t*10+A[i])%b;
    }
	return t;//余数
}

int main(){
	int A[N]={0},C[N]={0},b,r;
	char a[N];
	scanf("%s",a);
	getchar();
	scanf("%d",&b);
	
	int len=strlen(a);
	for(i=0;i<len;i++) A[i]=a[i]-'0';
	
	r=devide(A,b,C,len);
    
	int lenc=0;
	while(C[lenc]==0&&lenc<len) lenc++; //去除前导零
    
	if(lenc==len) printf("0 0");
	else{
		for(i=lenc;i<len;i++) printf("%d",C[i]);
		printf("  %d",r);
	}
	return 0;
}

除数>=10⁸&&<=10¹⁸

把int类型全部改为long long

P1480 A/B Problem - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

前缀和

一维

注意是从 a[1] 开始

s[0]和a[0]都==0

就是计算 [ l , r ] 这个区间数组的总和

s[l-1]=a[1]+a[2]+...+a[l] s[r]=a[1]+a[2]+...+a[l]+...+a[r] s[l,r]=s[r]-s[l-1]=a[l]+...+a[r]

#include <stdio.h>
#define N 100010
int i,j;
int a[N],s[N];
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	for(i=1;i<=n;i++) s[i]=s[i-1]+a[i];
	
	while(m--){
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",s[r]-s[l-1]);
	}
	return 0;
}

二维

求二维数组 [x1 , y1] 到 [x2 , y2] 构成矩形包含元素的和

测试用例：

输出：

17
27
21

代码：

#include <stdio.h>
#define N 1010
int n,m,q;
int a[N][N],s[N][N];

int main(){
	scanf("%d %d %d",&n,&m,&q);
	int i,j;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
		}
	}
	while(q--){
		int x1,y1,x2,y2;
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
	}
	
	return 0;
}

差分

一维：

时间复杂度：O(n) 优化为 O(1)

例题：

输入一个长度为n的整数序列
m个操作，将序列中 [ l , r ] 的每个数加上 c
输出完成操作后的序列

输入样例：

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例：

3 4 5 3 4 2

思想：

假定数组A全为0，之后将输入值按照公式插入，得到差分数组B
b[l] + c,因为前缀和，相当于A的[l,n]都加c
所以b[r+1]-c,则A的[r+1 ,n] 保持原样，A的[l,n]都加c

学习视频笔记,学习,音视频,笔记,c语言,算法

代码：

#include <stdio.h>
#define N 100010
int n,m;
int a[N],b[N];

void insert(int l,int r,int c){
	b[l]+=c;
	b[r+1]-=c;
}

int main(){
	int i;
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	for(i=1;i<=n;i++) insert(i,i,a[i]);
    //如果按照例题，此时b[n]={1,1,0,-1,1,-1}
	while(m--){
		int l,r,c;
		scanf("%d %d %d",&l,&r,&c);
		insert(l,r,c);
	}
	for(i=1;i<=n;i++) b[i]+=b[i-1]; //改变为前缀和后的数组输出
	for(i=1;i<=n;i++) printf("%d ",b[i]);
	return 0;
}

二维：

代码：

#include <stdio.h>
#define N 1010

int n,m,q;
int a[N][N],b[N][N];

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

int main(){
	scanf("%d %d %d",&n,&m,&q);
	int i,j;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
		} 
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			insert(i,j,i,j,a[i][j]); //得到差分数组b
		}
	}
	while(q--){
		int x1,y1,x2,y2,c;
		scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&c);
		insert(x1,y1,x2,y2,c); 
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]; //求前缀和
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++) printf("%d ",b[i][j]);
		printf("\n");
	}
    return 0;
}

测试用例：

输出：

2 3 4 1
4 3 4 1
2 2 2 2

双指针算法

朴素做法：

for(i=0;i<n;i++){
    for(j=0;j<m;j++){
        ...
    }
} //O(n^2)

优化：

for(i=0,j=0;i<n;i++){
    while(j<r&&check(i,j)) j++;
    //每道题目的具体逻辑
} //O(n)

常见问题分类：

（1）对于一个序列，用两个指针维护一段区间。

（2）对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作。

先写出朴素做法，再想双指针算法怎么写

例题：最长连续不重复子序列

给定一个长度为n的整数序列，请找出最长不包含重复数字的连续子序列并输出它的长度

输入格式：

第一行整数n。

第二行包含n个整数（0~100000）

输入样例：

5
1 2 2 3 4

输出样例：

思路：

//朴素做法：
for(i=0;i<n;i++){
	for(j=0;j<=i;j++){
		if(check(i,j)){
			res=max(res,i-j+1);
		}
	}
} 
//双指针算法：
for(i=0;i<n;i++){
	while(j<=i&&check(i,j)) j++;
	res=max(res,i-j+1);
	}
}

代码：

#include <stdio.h>

#define N 100010

int main() {
    int n;
    int a[N], s[N];

    scanf("%d", &n);
    int i,j;
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);

    int res = 0;
    for ( i = 0, j = 0; i < n; i++) {
        s[a[i]]++;     //存放每个数出现次数 
        while (s[a[i]] > 1) {
            s[a[j]]--;  //重复则j指针向后移直至不重复 
            j++;        //找符合条件新子串的开头数 
        }
        res = (res > (i - j + 1)) ? res : (i - j + 1); //最长不重复子串长度 
    }

    printf("%d\n", res);
    return 0;
}

位运算

位运算_判断某位是否为0-CSDN博客

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

n的二进制表示中第k位数（之后）是几

先把第k位移到最后一位
看各位是几 x%1
合起来 (n>>k)%1

n=15=(1111)₂
从最右边起第0位，3 2 1 0 , 总共4位

代码：

#include <stdio.h>

int main() {
    int n = 10;
	int k;
    for (k = 3; k >= 0; k--) { //k随机改变
        printf("%d", (n >> k) & 1);
    }
    return 0;
}

lowbit(x)

返回x的最后一位1

int lowbit(int x) {
    return x & -x;
}

x & ( -x )= x & ( ~x + 1)

二进制表示中-x是x的补码(取反加一)

学习视频笔记,学习,音视频,笔记,c语言,算法

例题：二进制中1的个数

给定一个长度为n的数列，求出数列中每个数的二进制表示中1的个数

输入样例：

5
1 2 3 4 5

输出样例：

1 1 2 1 2

#include <stdio.h>

int lowbit(int x) {
    return x & -x;
}

int main() {
    int n;
    scanf("%d", &n);

    while (n--) {
        int x;
        scanf("%d", &x);
        int res = 0;

        while (x) {
            x -= lowbit(x); //在二进制表达中每次减去x的最后一位1 
            res++; //统计1出现次数 
        }
        printf("%d ", res);
    }
    return 0;
}

离散化

离散化的目的可能是为了将插入的值映射到一个有限的范围，
以便更方便地进行处理和查询。
这可以通过排序和去重数组，
并使用插入的值在这个数组中的位置进行索引实现。

模板：

vector <int> alls; //存储所有待离散化的值
sort(alls.begin(),alls.end()); //所有值升序排序
alls,erase(unique(alls.begin(),alls.end()),alls.end()); //去掉重复元素

//二分求出x对应的离散化的值
int find(int x)
{
    int l=0,r=all.size()-1;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(all[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r+1; //映射到1,2...n
    //return r； 映射到0,1,...n-1
}

例题：区间和

假设有一个无限长的数轴，数轴上每个坐标上的数都是0.

现在我们首先进行n次操作，每次操作将某一位置x上的数加c。

接下来，进行m次询问，每个询问包含两个整数l和r，你需要求出区间[ l , r ]之间所有数的和

输入格式：

第一行包含两个整数n和m

接下来n行，每行包含两个整数x和c

再接下m行，每行包含两个整数 l 和 r

输出格式：

共m行，每行输出一个询问中所求区间和内数字和

数据范围：

-10⁹<=x<=10⁹
1<=n,m<=10⁵
-10⁹<=l<=r<=10⁹
-10000<=c<=10000

输入：

输出：

8
0
5

代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
 
const int N = 300010; //本来题目规定100000 但是a一个，PII两个，加起来3*100000

int i,j;
int n, m;
int a[N], s[N];

vector<int> alls;
vector<PII> add, query;

int find(int x) //二分
{
	int l = 0, r = alls.size() - 1;
	while (l < r)
	{
		int mid = l + r >> 1;
		if (alls[mid] >= x) r = mid;
		else l = mid + 1;
	}
	return r + 1;
}

int main() {
	cin >> n >> m;
    //插入
	for (i = 0; i < n; i++)
	{
		int x, c;
		cin >> x >> c;
		add.push_back({ x,c });

		alls.push_back(x);
	}
    
	for ( i = 0; i < m; i++)
	{
		int l, r;
		cin >> l >> r;
		query.push_back({ l,r });

		alls.push_back(l);
		alls.push_back(r);
	}
	
    //排序
	sort(alls.begin(), alls.end());
    
    //排序之后的去重
	alls.erase(unique(alls.begin(), alls.end()), alls.end());

	//处理插入
	for (auto item : add)
	{
		int x = find(item.first);
		a[x] += item.second;
	}

	//预处理前缀和
	for ( i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];

	//处理询问
	for (auto item : query)
	{
		int l = find(item.first), r = find(item.second);
		cout << s[r] - s[l - 1] << endl;
    }
	return 0;
}

解释：

unique函数：
- 作用：函数用于在已排序的范围内去除相邻的重复元素，并返回指向新的逻辑尾部的迭代器。unique
- 用法：unique(start, end)
在这里，alls.begin()表示范围的起始迭代器，alls.end()表示范围的结束迭代器。unique函数会去除相邻的重复元素，并将这些重复元素移到容器的末尾。它返回指向新的逻辑尾部的迭代器。
erase函数：
- 作用：函数用于移除指定范围内的元素。erase
- 用法：erase(start, end)
其中：
- start是指定范围的起始位置的迭代器。
- end是指定范围的结束位置的迭代器。
erase函数会删除从 end 到（不包括) end的所有元素。删除后，容器的大小会相应地减小，并且后续元素会向前移动填补删除的位置。

例如：

在这个示例中，erase 函数删除了 numbers 向量中索引为1到3的元素，即2、3、4。输出结果将是1 5 。
```
#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // 删除索引为1到3的元素
    numbers.erase(numbers.begin() + 1, numbers.begin() + 4);

    // 输出结果
    for (auto num : numbers) {
        std::cout << num << " ";
    }

    return 0;
}
```

区间合并

步骤：

按区间左端点排序
比较st , ed

(1) 包含（2）有交集（3）无交集

学习视频笔记,学习,音视频,笔记,c语言,算法

例题：

给定n个区间 [ l ,r ] ，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数

数据范围：

1<=n<=100000

-10⁹<=l<=r<=10⁹

输入样例：

输出样例：

代码：文章来源地址https://www.toymoban.com/news/detail-831947.html

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;

const int N = 100010;

int i;
int n;
vector<PII> segs; //存放区间

void merge(vector<PII> &segs)
{
	vector<PII> res;
	sort(segs.begin(), segs.end()); //左端点排序
	int st = -2e9, ed = -2e9; //假设是无穷
	for (auto seg : segs)
		if (ed < seg.first)  //若无交集
		{
			if (ed != -2e9) res.push_back({ st,ed }); //原先的一段区间res里
			st = seg.first, ed = seg.second; //更新新区间
		} 
		else ed = max(ed, seg.second); //有交集，找最大值更新ed
	if (st != -2e9) res.push_back({ st,ed }); //没输入区间确保放进去一个
	segs = res;  
}

int main()
{
	cin >> n;
	for (i = 0; i < n; i++)
	{
		int l, r;
		cin >> l >> r;
		segs.push_back({ l,r }); 
	}
	merge(segs);
	cout << segs.size() << endl;
	return 0;
}