一、基础算法
(一).排序算法
1.快速排序(quick_sort) (AcWing 785.快速排序)
(1)算法思想(分治)：
先确认分界点：一般选为左端点l或者右端点r或者中间点(l+r)/2
调整区间：使分界点左侧的数都小于等于分界点，右侧的数都大于等于分界点
递归处理左右两侧
(2)代码实现思路：
循环实现分界点调整区间操作，设置两个指针i,j分别指向数组的首尾，将两个指针的内容的大小与分界点比较，当左指针内容小于分界点，左指针右移，当右指针内容大于分界点，右指针左移，否则先交换两个指针的内容，再向中间靠拢。如果两个指针相遇，则退出循环。通过递归将每一个分界点完成调整区间操作。
(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int n;
int a[N];
void quick_sort(int a[],int l,int r)
{
if(l>=r) return;
int x=a[l],i=l-1,j=r+1;
while(i<j)
{
do i++; while(a[i]<x);//当左指针内容小于分界点的值右移
do j--; while(a[j]>x);//当右指针内容小于分界点的值左移
if(i<j) swap(a[i],a[j]);//当左指针大于等于，右指针小于
//等于，交换两指针的内容，又因为
//do循环所以两指针同时向中间移动
}
quick_sort(a,l,j);
quick_sort(a,j+1,r);
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) cin>>a[i];
quick_sort(a,0,n-1);
for(int i=0;i<n;i++) cout<<a[i]<<" ";
return 0;
}2.归并排序(merge_sort)(AcWing 787.归并排序)
(1)算法思想：
先确认分界点：一般选中间点(l+r)/2
排序：递归排序分界点左侧和右侧
归并：将两侧已经排序完成的数组合并成一个数组
(2)代码实现思路：
先以中间点为分界点，将整个数组分为左右两侧，然后依次递归处理，设置左右指针分别指向左侧的第一个元素和右侧的第一个元素，直到左右指针相等时返回。对于每一次递归都要进行合并操作，即设置一个新的数组，循环依次比较左右指针，将较小的数放到新数组中，直到某个指针到达终点，再将未放置完的一侧数字依次放入新数组后面。最后将新数组依次复制到递归数组中。
(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
int n;
int a[N],tmp[N];
void merge_sort(int a[],int l,int r)
{
if(l>=r) return;
int mid=(l+r)/2;
merge_sort(a,l,mid),merge_sort(a,mid+1,r);//递归排序左侧和右侧
int k=0,i=l,j=mid+1;
while(i<=mid&&j<=r)
{
if(a[i]<=a[j]) tmp[k++]=a[i++];//如果左指针小，则放入新数组中
else tmp[k++]=a[j++];//否则右指针内容放入新数组中
}
while(i<=mid) tmp[k++]=a[i++];//如果左侧有剩余，则将剩余部分放入新数组中
while(j<=r) tmp[k++]=a[j++];//如果右侧有剩余，则将剩余部分放入新数组中
for(int i=l,j=0;i<=r;i++,j++) a[i]=tmp[j];//将新数组的内容复制到递归数组中
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
merge_sort(a,0,n-1);
for(int i=0;i<n;i++) cout<<a[i]<<" ";
}(二).二分查找
1.整数二分(AcWing 789.数的范围)
(1)算法思想：
结束条件并不是找到x,而是找到满足性质的最后一个数。
模板一
确认中间值：根据已排序完成的数组，选择中间点mid=(l+r+1)/2，假设小于待查找数x的范围为左区间，右侧为大于待查找数x的范围为右区间（这里与我之前学的思维有点差异：我之前学的是用x跟mid的内容比较，y总讲的是mid的内容和x比较，直接看代码可能更好理解一些~）
条件判断：判断mid是否满足左区间性质（即x>=a[mid]），如果满足则说明mid在左区间,即x在mid右侧（更新区间为[mid,r]，l=mid），否则x在mid左侧（更新区间为[l,mid-1],r=mid-1）
可以看出，当有多个x出现在数组中时，一定是l先锁定x的位置（因为相等时更新的是l），然后如果下次q[mid]（当l和r不重合时，mid一定在l右侧）再一次小于等于（重点是等于,即若l不等于r时，当再次找到x时，这时候的x一定在上一个x（位置为l）的右侧）依旧更新l，因此最终l是在x出现的最后一个位置。
因此该模版查找的是x出现的最后一个位置，因为相等时更新l，而l不断向右移动（mid向上取整,即mid=(l+r+1)/2）。
模板二
确认中间值：根据已排序完成的数组，选择中间点mid=(l+r)/2，假设小于待查找数x的范围为左区间，右侧为大于待查找数x的范围为右区间
条件判断：判断mid是否满足右区间性质（即x<=a[mid]），如果满足则说明mid在右区间,即x在mid左侧（更新区间为[l,mid]，r=mid），否则x在mid右侧（更新区间为[mid+1,r],l=mid+1）
可以看出，当有多个x出现在数组中时，一定是r先锁定x的位置（因为相等时更新的是r），然后如果下次q[mid]（当l和r不重合时，mid一定在r左侧）再一次大于等于（重点是等于,即若l不等于r时，当再次找到x时，这时候的x一定在上一个x（位置为r）的左侧）依旧更新r，因此最终r是在x出现的第一个位置。
因此该模版查找的是x出现的第一个位置，因为相等时更新r，而r不断向左移动（mid向下取整，即mid=(l+r)/2）。
(2)代码实现思路：
设置两个指针l,r分别指向区间两端，待查找的数为x。
模板一（寻找满足左区间条件的数）
设置mid为mid=(l+r+1)/2，如果满足a[mid]<=x，则令l=mid，否则令r=mid-1,循环结束时l=r。
模板二（寻找满足右区间条件的数）
设置mid为mid=(l+r)/2，如果满足a[mid]>=x，则令r=mid，否则令l=mid+1,循环结束时l=r。
(3)代码实现：
#include <iostream>
using namespace std;
const int N=1e6+10;
int n;
int a[N];
int m,x;
int main() {
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
while(m--)
{
cin>>x;
int l=0,r=n-1;
while(l<r)
{
int mid=(l+r)/2;
if(a[mid]>=x) r=mid;
else l=mid+1;
}
if(a[l]!=x) cout<<"-1 -1"<<endl;
else
{
cout<<l<<" ";
int l=0,r=n-1;
while(l<r)
{
int mid=(l+r+1)/2;
if(a[mid]<=x) l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
}
return 0;
}2.浮点数二分
(1)算法思想：（使用上面哪种模板都可以）
确认中间值：根据已排序完成的数组，选择中间点mid=(l+r)/2，假设小于待查找数x的范围为左区间，右侧为大于待查找数x的范围为右区间
条件判断：判断mid是否满足右区间性质（即x<=a[mid]），如果满足则说明mid在右区间,即x在mid左侧（更新区间为[l,mid]，r=mid），否则x在mid右侧（更新区间为[mid,r],l=mid）
(2)代码实现思路：
设置两个指针l,r分别指向区间两端，待查找的数为x。
设置mid为mid=(l+r)/2，如果满足a[mid]>=x，则令r=mid，否则令l=mid,循环结束时r-l<1e-6(或者更小的数)。
(3)代码实现：
#include <iostream>
using namespace std;
double x;
int main()
{
cin>>x;
double l=0,r=x;
while(r-l>1e-6)
{
double mid=(r+l)/2;
if(mid*mid>=x) r=mid;
else l=mid;
}
cout<<l;
return 0;
}
(三).高精度运算
简介：由于存在一些位数极多的数（如10^6个位数的大整数），它们在c++中无法用一个已知数据类型表示，所以需要运用新的表示方法，一般采用开辟一个存储各位数字的数组，倒序存入大整数每一位的数字（方便进位）。
1.大整数加大整数(AcWing 791.高精度加法)
(1)算法思想：
进位设置：设置进位Ti，T0=0
判断溢出：如果Ai+Bi+Ti-1大于10，则将本位的进位Ti设置为1
计算本位和:将本位与进位的和对10进行取余运算，即可计算出本位和
(2)代码实现思路：
首先输入两个字符串，将两个字符串倒序存入两个vector数组中。设置进位t并初始化为0，将其与每一位做加法，将此时的t对10取余，即为本位和，再对10做除法，即为本位产生的进位。当i大于每一个数组的位数时退出循环，最后判断最高位的进位是否存在，若不为0则在末尾添加1。
(3)代码实现：
#include <iostream>
#include <vector>
using namespace std;
string a,b;
vector<int> A,B;
vector<int> 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;
}
int main() {
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
auto C=add(A,B);
for(int i=C.size()-1;i>=0;i--) cout<<C[i];
return 0;
}
2.大整数减大整数(AcWing 792.高精度减法)
(1)算法思想：
判断被减数A和减数B关系：如果A<B，计算-（B-A）
借位设置:如果低位产生借位则，Ti为1，初始为0
判断每一位被减数Ai与减数Bi关系：如果Ai>Bi，直接减;如果Ai<=Bi, 减完加10。
计算本位和:将两数相减的结果再减去借位即为本位和
(2)代码实现思路：
首先比较被减数A和减数B的大小关系：设置布尔类型的函数，如果A的位数不等于B的位数，则返回位数做差后的结果；否则比较每一位，如果不相等，返回该位两数做差后的结果。若函数返回true，则不变，否则交换A,B顺序，并先输出“-”。
再创建减法运算的函数：设置借位t并初始化为0，让被减数Ai减去借位t，再与减数Bi相减，将此时的t加10后再对10取余即可实现对本位结果正负两种情况的处理。
最后，处理输出多余0的情况，如果输出的数组最后一位为0，则丢弃。
(3)代码实现：
#include <iostream>
#include <vector>
using namespace std;
string a,b;
vector<int> A,B;
bool cmp(vector<int> &A,vector<int> &B)
{
if(A.size()!=B.size()) return A.size()>B.size();
else{
for(int i=A.size()-1;i>=0;i++)
if(A[i]!=B[i]) return A[i]-B[i];
}
return true;//如果相等不输出-
}
vector<int> 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);
if(t>=0) t=0;
else t=1;
}
while(C.size()>1&&C.back()==0) C.pop_back();//C.size()>1保证如果结果就是0那么就不删除最后一位
return C;
}
int main() {
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
if(cmp(A,B)) {
auto C = sub(A, B);
for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
}else{
auto C = sub(B,A);
cout<<"-";
for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
}
return 0;
}
3.大整数乘正常数(AcWing 793.高精度乘法)
(1)算法思想：
与正常手算略有不同：把乘数当成一个整体看待。
进位:设置进位Ti，初始为0，本位向高位的进位等于本位乘积除10（注：这里的本位是指被乘数，因为将乘数看成一个整体）
计算本位和:将两数相乘的结果对10取余即为本位和（由于乘数是正常大小的数所以可以直接计算）
(2)代码实现思路：
将乘数其与被乘数每一位做乘法，结果记为t，将此时的t对10取余，即为本位和，再对10做除法，即为本位产生的进位。最后判断最高位的进位是否存在，若不为0则在末尾添加此时的进位（这里可以写进循环判断条件中，若t不为0，则加入最终数组中）。
(3)代码实现：
#include <iostream>
#include <vector>
using namespace std;
int b;
vector<int> A;
string a;
vector<int> 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;//因为循环条件加上了t所以这里要重新判断一下条件是否符合
C.push_back(t%10);
t/=10;
}
return C;
}
int main()
{
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
auto C=mul(A,b);
for(int i=C.size()-1;i>=0;i--) cout<<C[i];
return 0;
}4.大整数除正常数(AcWing 794.高精度除法)
(1)算法思想：
与之前的计算不同：除法是从高位开始做运算。
进位:设置余数r，初始为0，本位的余数是上一位的余数乘10加上本位的数字再对除数取余
计算本位商:本位的商是余数乘10加上本位的数字再除以除数
(2)代码实现思路：
循环从高位，即被除数数组的末尾开始。将每一位产生的余数除以除数即为本位的商，再将余数对除数取余即为本位产生的余数，每一位使用的余数是将上一位的余数乘10在加上本位的数。最终要考虑处理输出多余0的情况，如果输出的数组最后一位为0，则丢弃。
(3)代码实现：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N =1e6+10;
int n,b,r;
vector<int> A;
string a;
vector<int> 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;
}
int main()
{
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
auto C=div(A,b,r);
for(int i=C.size()-1;i>=0;i--) cout<<C[i]<<endl;
cout<<r;
return 0;
}(四).前缀和
1.一维前缀和(AcWing 795.前缀和)
(1)算法思想：
创建一个前缀和数组S，通过S[i]=S[i-1]+a[i]计算数组a中前i个数的和，注意i从1开始。通过前缀和数组可以很快计算出数组a中某一段区间的和，如求l,r之间的和，就可通过计算S[r]-S[l-1]得出。
(2)代码实现：
#include <iostream>
using namespace std;
const int N = 1e6+10;
int a[N],s[N];
int n,m;
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
while(m--)
{
int l,r;
cin>>l>>r;
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}2.二维前缀和(AcWing 796.子矩阵的和)
(1)算法思想：（观察左上部分）
将二维数组看成一个矩形，创建一个前缀和数组S，因此S[i][j]就是数组a在（i,j）左上部分所有元素之和，可以通过S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+a[i][j]计算每一个位置的左上部分和。通过该前缀和数组可以很快计算出数组a中某块矩形区域的元素和，如求(x1,y1)（小）和(x2,y2)（大）之间的和，就可通过计算S[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]得出。
(2)代码实现：
#include <iostream>
using namespace std;
const int N = 1e3+10;
int a[N][N],s[N][N];
int n,m,q;
int main() {
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int 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;
cin>>x1>>y1>>x2>>y2;
cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
}
return 0;
}(五).差分
1.一维差分(AcWing 797.差分)
(1)算法思想：
假设一个差分数组b,使得该数组满足b[i]=a[i]-a[i-1]（a[0]初始为0），因此a[i]等于差分数组前面i个元素的和。所以当对原数组a的[l,r]区间内的元素都加上c时，可以通过对b[l]加c，此时由于区间内a数组的所有元素都等于差分数组前面i项的和，因此在a[l]之后的所有元素都加上了c。此时要想达到目的，只需要在r项之后每一项都减去c即可，因此只需将b[r+1]减去c即可使得a[r]之后所有元素都减去了c.
创建差分数组也可以通过类似的方法建立，如在差分数组区间（1,1）插入a[1]即可实现在b[1]位置插入a[1],同时b[2]位置处为-a[1],依此类推，即可完成建立。
(2)代码实现：
#include <iostream>
using namespace std;
const int N=1e6+10;
int a[N],b[N];
int n,m;
void insert(int l,int r,int c)
{
b[l]+=c;
b[r+1]-=c;
}
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) insert(i,i,a[i]);
while(m--)
{
int l,r,c;
cin>>l>>r>>c;
insert(l,r,c);
}
for(int i=1;i<=n;i++) b[i]+=b[i-1];
for(int i=1;i<=n;i++) cout<<b[i]<<" ";
return 0;
}
2.二维差分(AcWing 798.差分矩阵)
(1)算法思想：(观察右下部分)
将二维数组看成一个矩形，对于a[i][j]而言，它就是左上部分所有差分矩阵元素的和。因此，对照一维差分可以知道，对差分矩阵b[i][j]做变化就是对数组a在（i，j）右下部分做变化，差分矩阵的创建也可以通过类似的操作得出。即，若想使得矩形内(x1,y1)（小）与(x2,y2)（大）间的矩形元素统一发生变化，则可通过b[x1][y1]+=c，b[x2+1][y1]-=c，b[x1][y2+1]-=c,b[x2+1][y2+1]+=c实现
(2)代码实现：
#include <iostream>
using namespace std;
const int N=1e3+10;
int a[N][N],b[N][N];
int n,m,q;
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() {
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
insert(i,j,i,j,a[i][j]);
while(q--)
{
int x1,x2,y1,y2,c;
cin>>x1>>y1>>x2>>y2>>c;
insert(x1,y1,x2,y2,c);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<b[i][j]<<" ";
cout<<endl;
}
return 0;
}
(六).位运算
简介：常用两种运算：1、求n的二进制表示的第K位数字 2、返回n的最后一位1
1.求n的二进制表示的第K位数字
(1)算法思想：
将二进制数n的第k位移动到最后一位（n>>k），检查最后一位数字（即与1做与运算）
(2)代码实现：
#include <iostream>
using namespace std;
int main() {
int n=10;
for(int k=3;k>=0;k--) cout<<(n>>k&1);
return 0;
}
2.返回n的最后一位1（Acwing 801.二进制中1的个数）
(1)算法思想：
通过lowbit函数实现返回n的最后一位1，即将n和-n相与，再将n减去结果，当n为0时退出循环，做了多少次这样的运算就有几个1。(n=10100,-n=01100)
二进制常用技巧:
n&(n-1)可以将二进制数的最右边的1变成0，如10100经过该运算后会变成10000。因此该公式同样可以统计二进制数中1的个数，即while(n&(n-1)) cnt++；同时该公式也可以判断一个数是否是2的幂，即若n&(n-1)==0，则是2的幂，若不为0，则不是（因为2的幂的二进制数中只会有一个1）。
n&(-n)表示将一个数只是保留二进制下最右边的1的位，而其他位变成0.比如1111变成0001.这个公式在判断数组中除了两个数出现一次，其余数字出现两次中，可以通过与或所有数据得到的结果后，以这个结果中最右边位为界限，将数组划分为两个数组。因为这个位置=1则说明两个不同的数据在这位的位一定是一个为0一个为1(因为0^1=1)，这样就可以把数组分成两个组了。
(2)代码实现：
#include <iostream>
using namespace std;
int lowbit(int x)
{
return x&-x;
}
int main()
{
// 5
// 1 2 3 4 5
int n;
cin>>n;
while(n--)
{
int x,res=0;
cin>>x;
while(x) x-= lowbit(x),res++;
cout<<res<<" ";
}
}(七).双指针算法
简介：双指针是一种常见的算法，可以针对单一序列使用（快速排序），以维持区间内某种规则；也可以针对2个序列使用，以保证某种次序（归并排序）。双指针算法可以从暴力算法(O(n^2))通过使用某种规则优化到O(n)复杂度。其大致模板为：
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
// 具体问题的逻辑
}1.输出单词（输入包含空格）
(1)算法思想：
设置指针i,j，i负责向后遍历，j负责寻找单词的末尾，因此一个单词就是i到j之间的部分，再令i移动到下一个单词的位置
(2)代码实现思路：
当j不为空格时，就让j向后移动，循环结束时j指向空格，此时输出（j,i）就是该单词，再令i等于j,就使得i移动到下一个单词的位置。
(3)代码实现：
#include <iostream>
#include <string>
using namespace std;
int main()
{
string str;
getline(cin,str);//读入空格
int n=str.length();
for(int i=0;i<n;i++)
{
int j=i;
while(j<n&&str[j]!=' ') j++;
for(int k=i;k<j;k++) cout<<str[k];
cout<<endl;
i=j;
}
return 0;
}2.AcWing 799.最长连续不重复子序列
(1)算法思想：
暴力算法：通过对所有元素都进行枚举，在检查满足条件，选取满足条件的最长i,j间的距离
双指针算法：由于j随着i的增大，只会向数组末端移动，因此可以进行优化（单调的性质），判断当前的j是否满足从j到i没有重复数字，不满足就向后移动，不再重新置0，最终对每一次i-j+1的结果取最大值即可。（i在区间终点,j在区间起点）
(2)代码实现思路：
首先创建一个计数的数组s，如果数组中出现一个数字a[i]，则s[a[i]]++，随着i的增加，当这个数字大于1时（即出现两次），就令j移动到这个数字只出现一次的位置，同时对数组s进行更新，因为相当于i位置之前的元素不在对本次计算的距离有作用，所以将j移动过的数字的个数都减1，即s[a[j]]--同时j++。最终得出距离的最大值。
(3)代码实现：
#include <iostream>
#include <algorithm>
const int N=1e6+10;
int n,res=0;
int a[N],s[N];
using namespace std;
int main() {
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0,j=0;i<n;i++)
{
s[a[i]]++;
while (s[a[i]]>1)
{
s[a[j]]--;
j++;
}
res=max(res,i-j+1);
}
cout<<res;
return 0;
}
(八).离散化
简介：若有一个数组范围很大，但元素很少，则可以将其映射到一个新数组中，减少空间的浪费
1.Acwing 802.区间和
(1)算法思想：
用一个数组alls来存储x,l,r的数值，对于插入操作用一个add双元数组来存储{x,c}，对于查询操作用query双元数组来存储{l,r}，将x,l,r压入alls数组中，对其进行递增，去重操作。对于插入操作，用二分查找来查找x在alls数组中的位置q，然后创建一个数组a[]，在该数组的q位置上加上c（实现了坐标轴与alls数组位置的映射），对于未加c的位置而言，说明该位置并未有插入操作，默认为0，然后计算a数组的前缀和（注意该前缀和数组的大小与alls数组大小一致，因为a数组与alls对应），以便求一段区间的和。对于查询操作，同样用二分查找来查找l,r在alls数组的位置ql,qr，该位置同样对应于a数组的位置，因此求l,r区间内的和，就相当于求数组a中(ql,qr)间的和，通过前缀和数组即可求出。
(2)代码实现思路：
先读入插入操作需要的数字（x,c）将其存储在add类型的数组当中，同时将x压入alls数组当中。再读入问询操作需要的数字（l,r）将其存储在query类型的数组当中，同时将l,r压入alls数组当中。
再进行排序，去重操作，运用c++自带的sort函数对alls数组进行排序，再使用erase函数和unit函数对其进行去重操作。
再处理插入操作，利用二分查找，得到x在alls数组的位置（注意加1，因为前缀和数组从1 开始），在创建一个数组a,使得每一个x查找的位置都加c。
再求a数组前缀和数组，即s[i]=s[i-1]+a[i]，循环终止条件为i=alls.size()(因为二分查找最后一个位置加1)。
再求区间和，类似于插入操作，利用二分查找，得到l,r在alls数组的位置，通过前缀和数组求出区间和（s[r]-s[l-1]）。
(3)代码实现：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
vector<int> alls;
const int N =3e6+10;
int a[N],s[N];
int n,m;
vector<PII> add,query;
int find(int x)
{
int l=0,r=alls.size()-1;
while(l<r)
{
int mid=(l+r)/2;
if(x<=alls[mid]) r=mid;
else l=mid+1;
}
return r+1;
}
int main() {
cin>>n>>m;
while(n--)
{
int x,c;
cin>>x>>c;
add.push_back({x,c});
alls.push_back(x);
}
while(m--)
{
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 q;
q=find(item.first);
a[q]+=item.second;
}
for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];
for(auto item:query)
{
int l,r;
l=find(item.first);
r=find(item.second);
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}
(九).区间合并
简介：将有交集的区间合并成一个。
1.Acwing 803.区间合并
(1)算法思想：
分两种情况讨论，若两个区间没有交集，则直接加入最终数组内，若有交集，将右端点更新为最大值。
(2)代码实现思路：
先读入区间端点(l,r)，将其存入segs数组内。再实现合并，设置一个目标数组res，先将segs数组排序好，设置左右端点（st,ed）为第一个维护的区间，初始都为负无穷大，取出segs数组中的元素seg，比较ed和seg的l关系，如果ed<l，叫说明两个区间没有交集，则直接将seg加入res中，并将待维护的区间变为seg。反之，更新ed为最大值（因为区间排好序，所以不用将st更新为最小）。最后先判断segs是否为空，若不为空，则将最后一个维护的区间加入res中。
(3)代码实现：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
vector<PII> segs;
int n;
const int INF=2e9;
void merge(vector<PII> &segs)
{
vector<PII> res;
int st=-INF,ed=-INF;
for(auto seg:segs)
{
if(ed<seg.first)
{
if(ed!=-INF) res.push_back(seg);//第一个维护的区间是seg的第一个元素，因此先不将其加入res。
st=seg.first,ed=seg.second;
}
else ed=max(ed,seg.second);
}
if(st!=-INF) res.push_back({st,ed});
segs = res;
}
int main() {
cin>>n;
while(n--)
{
int l,r;
cin>>l>>r;
segs.push_back({l,r});
}
sort(segs.begin(),segs.end());
merge(segs);
cout<<segs.size();
return 0;
}
