快速排序
快速排序
题目：
给定你一个长度为n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在1~109109范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤1000001≤n≤100000
输入样例：53 1 2 4 5输出样例：1 2 3 4 5
程序
using namespace std;
const int N=100000;
int p[N];
void quick_sort(int p[],int l,int r){
if(l>=r) return ;
int i = l-1,j=r+1,x=p[l+r>>1];
while(i<j){
do i++;while(p[i]<x);
do j--;while(p[j]>x);
if(i<j) swap(p[i],p[j]);
}
quick_sort(p,l,j);
quick_sort(p,j+1,r);
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&p[i]);
quick_sort(p,0,n-1);
for(int i=0;i<n;i++)printf("%d ",p[i]);
return 0;
}
题目2
题目2
给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列的第k小的数是多少。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数（所有整数均在$1-~10^9$范围内），表示整数数列。
输出格式
输出一个整数，表示数列的第k小数。
数据范围
$1≤n≤1000000,
1≤k≤n$
样例
输入样例：
5 3
2 4 1 5 3
输出样例：
3
程序
#include <iostream>
using namespace std;
const int N=100000;
int a[N];
int quick_sort_k(int a[],int l,int r,int k){
if(l>=r) return q[l] ;
int i=l-1;j=r+1,x=q[l+r>>1];
while(i<j){
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if(i<j) swap(q[i],q[j]);
}
sl=j-l+1;
if(k<=sl) return quick_sort_k(q,l,j,k);
else return quick_sort_k(q,j+1,r,k-sl);//k-sl 因为整个区间第K小的数是右半边区间的k-sl小的数
}
int main(){
int n,k;
cin >> n >> k ;
for(int i=0;i<n;i++)sccanf("%d",a[i]);
cout << quick_sort_k(q,0,n-1,k)<< endl;;
return 0;
}
时间复杂度
n *(1+1/2+1/4 +.....) < 2n O(n)
归并排序
模板
题目
题目：给定你一个长度为n的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在1~109109范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
$1≤n≤1000001≤n≤100000$
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
程序
#include<iostream>
using namespace std;
const int N =100000;
int q[N],temp[N];
long long res=0;
void merge_sort(int q[],int l,int r){
if(l>=r) return;
int mid = l+r>>1;
merge_sort(q,l,mid);
merge_sort(q,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r){
if(q[i]<=q[j]) temp[k++]=q[i++];
else {
temp[k++]=q[j++];
}
}
while(i<=mid)temp[k++]=q[i++];
while(j<=r) temp[k++]=q[j++];
for(i=l,j=0;i<=r;i++,j++) q[i]=temp[j];
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&q[i]);
}
merge_sort(q,0,n-1);
for(int i=0;i<n;i++)printf("%d ",q[i]);
}
题目2
逆序对的数量
题目描述
给定一个长度为$n$的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 $i $个和第$ j $个元素，如果满足$ i < j 且 a[i] > a[j]$，则其为一个逆序对；否则不是。
输入格式
第一行包含整数$n$，表示数列的长度。
第二行包含 $n $个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
$1≤n≤100000$
输入样例：
6
2 3 4 5 6 1
输出样例：
5
程序
#include<iostream>
using namespace std;
const int N =100010;
int q[N],temp[N];
long long res=0;
void merge_sort(int q[],int l,int r){
if(l>=r) return;
int mid = l+r>>1;
merge_sort(q,l,mid);
merge_sort(q,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r){
if(q[i]<=q[j]) temp[k++]=q[i++];
else {
res += mid-i+1;
temp[k++]=q[j++];
}
}
while(i<=mid)temp[k++]=q[i++];
while(j<=r) temp[k++]=q[j++];
for(i=l,j=0;i<=r;i++,j++) q[i]=temp[j];
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&q[i]);
}
merge_sort(q,0,n-1);
cout << res<<endl;
for(int i=0;i<n;i++)printf("%d ",q[i]);
}
二分查找
整数的二分
数的范围
给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。
对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。
如果数组中不存在该元素，则返回“-1 -1”。
输入格式
第一行包含整数n和q，表示数组长度和询问个数。
第二行包含$n$个整数（均在1~10000范围内），表示完整数组。
接下来$q$行，每行包含一个整数k，表示一个询问元素。
输出格式
共$q$行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回“-1 -1”。
数据范围
$1≤n≤1000001≤n≤100000
1≤q≤100001≤q≤10000
1≤k≤100001≤k≤10000$
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1
程序
using namespace std;
const int N=100000;
int a[N];
int q,k,n;
int main(){
cin >> n >> q;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
while(q--){
scanf("%d",&k);
//二分查找
int l=0,r=n-1;
while(l<r){
int mid =l+r>>1;
if(a[mid]>=k) r= mid;
else l=mid+1;
}//eof l=r
if(a[l]!=k) cout << "-1 -1"<<endl;
else{
cout << l << " ";
int l=0,r=n-1;
while(l<r){
int mid = l+r+1 >> 1;
if(a[mid]<=k) l=mid;
else r=mid-1;
}
cout << l << endl;
}
}
return 0;
}
实数的二分
数的三次立方根
给定一个浮点数n，求它的三次方根。
输入格式
共一行，包含一个浮点数n。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留6位小数。
数据范围
$−10000≤n≤10000−10000≤n≤10000$
输入样例：
1000.00
输出样例：
10.000000
程序
#include<math.h>
using namespace std;
int main(){
double n=0;
cin >> n;
double l=-10000,r=10000;
while(r-l>1e-8){
double mid =(l+r)/2;
if(pow(mid,3)<=n) l=mid;
else r=mid;
}
printf("%.6f",l);
}
高精度加法
A+B A的长度可能为 10^6
模板
题目
题目描述
定两个正整数，计算它们的和。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的和。
数据范围
$1≤整数长度≤100000$
样例
输入样例：
12
23
输出样例：
35
程序
#include <iostream>
#include <vector>
using namespace std;
vector<int> A,B;
string 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 代表 A[i]+B[i]+t C[i] = (A[i]+B[i]+t)%10
t/=10; //判断是否有进位
}
if(t) C.push_back(t);
return C;
}
int main() {
cin >> a >> b;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0'); // A = [1,2,3,4,5]
for(int i = b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
vector<int> C = add(A,B);
for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]);
return 0;
}
高精度减法
题目描述
给定两个正整数，计算它们的差。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的差。
数据范围
1≤整数长度≤105
样例
输入样例：
32
11
输出样例：
21
//A>=B return ture
bool cmp(vector<int> &A,vector<int> &B){
if(A.size()!=B.size()) return A.size()>B.size(); //如果位数不等，长度长的大
else{
for(int i=0;i<A.size();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();
return C;
}
int main() {
cin >> a >> b;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0'); // A = [1,2,3,4,5]
for(int i = b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
if(cmp(A,B)){
vector<int> C = sub(A,B);
for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]);
}
else{
vector<int> C = sub(B,A);
cout << '-';
for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]);
}
return 0;
}
高精度乘法
题目描述
给定两个正整数A和B，请你计算A * B的值。
输入格式
共两行，第一行包含整数A，第二行包含整数B。
输出格式
共一行，包含A * B的值。
数据范围
1≤A的长度≤100000,
1≤B≤10000
样例
输入样例：
2
3
输出样例：
6
vector<int> mul(vector<int> &A,int b){
vector<int> C;
int t=0;
for(int i=0;i<A.size();i++){
t+=A[i]*b;
C.push_back(t%10);
t/=10;
}
if(t) C.push_back(t);
while(C.size()>1&&C.back()==0) C.pop_back();
return C;
}
//乘法
int main(){
string a;
int b;
vector<int> A;
cin >> a >> b;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0'); // A
auto C = mul(A,b);
for(int i =C.size()-1;i>=0;i--)printf("%d",C[i]);
return 0;
}
高精度除法
题目描述
给定两个正整数A，B，请你计算 A / B的商和余数。
输入格式
共两行，第一行包含整数A，第二行包含整数B。
输出格式
共两行，第一行输出所求的商，第二行输出所求余数。
数据范围
1≤A的长度≤100000,
1≤B≤10000
样例
输入样例：
7
2
输出样例：
3
1
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 = r%b;
}
reverse(C.begin(),C.end());
while(C.size()>1&&C.back()==0) C.pop_back();
return C;
}
//除法
int main(){
string a;
int b,r=0; //r 余数
vector<int> A;
cin >> a >> b;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0'); // A
auto C = div(A,b,r);
for(int i =C.size()-1;i>=0;i--)printf("%d",C[i]);
cout << endl << r << endl;
return 0;
}
前缀和
一维数组的前缀和
题目描述
输入一个长度为n的整数序列。
接下来再输入m个询问，每个询问输入一对l, r。
对于每个询问，输出原序列中从第l个数到第r个数的和。
输入格式
第一行包含两个整数n和m。
第二行包含n个整数，表示整数数列。
接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。
输出格式
共m行，每行输出一个询问的结果
#include <iostream>
using namespace std;
const int N=100010;
int a[N],S[N];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i =1;i<=n;i++)scanf("%d",&a[i]); //i要从1开始！！！
for(int 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]); // i 从1 开始的原因
}
return 0;
}
二维数组的前缀和
题目描述
输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数n，m，q。
接下来n行，每行包含m个整数，表示整数矩阵。
接下来q行，每行包含四个整数x1, y1, x2, y2，表示一组询问。
输出格式
共q行，每行输出一个询问的结果。
数据范围
1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000
输入样例
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出
17
27
21
#include <iostream >
using namespace std;
const int N=10000;
int a[N][N],s[N][N];
int main(){
int n,m,q;
cin >> n >> m >> q;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
}
}
//构造s
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,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
}
return 0;
}
差分
一维差分
说明
模板
给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c
题目
题目描述
输入一个长度为n的整数序列。
接下来输入$m$个操作，每个操作包含三个整数$l, r, c，$表示将序列中$[l, r]$之间的每个数加上$c$。
请你输出进行完所有操作后的序列。
输入格式
$第一行包含两个整数n和m。$
$第二行包含n个整数，表示整数序列。$
$接下来m行，每行包含三个整数l，r，c，表示一个操作。$
输出格式
$共一行，包含n个整数，表示最终序列。$
数据范围
$1≤n,m≤100000,
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000$
样例
输入样例：
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例：
3 4 5 3 4 2
程序
#include <iostream>
const int N=100000+10;
int a[N],b[N];//a 原数组 b 差分数组
using namespace std;
void insert(int l,int r,int x){
b[l]+=x;
b[r+1]-=x;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) insert(i,i,a[i]);//相当于在[i,i]插入 a[i]
while(m--){
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
insert(l,r,c);
}
// 由b生成a b的前缀和
for(int i=1;i<=n;i++) b[i]+=b[i-1];
for(int i=1;i<=n;i++) printf("%d ",b[i]);
return 0;
}
二维差分
说明
模板
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
题目
题目描述
输入一个n行m列的整数矩阵，再输入q个操作，每个操作包含五个整数$x1, y1, x2, y2, c，其中(x1, y1)和(x2, y2)$表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上$c$。
请你将进行完所有操作后的矩阵输出。
输入格式
第一行包含整数$n,m,q$。
接下来$n$行，每行包含m个整数，表示整数矩阵。
接下来$q$行，每行包含5个整数$x1, y1, x2, y2, c$，表示一个操作。
输出格式
共 $n$ 行，每行$ m$ 个整数，表示所有操作进行完毕后的最终矩阵。
数据范围
$1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤矩阵内元素的值≤1000$
样例
输入样例：
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1
输出样例：
2 3 4 1
4 3 4 1
2 2 2 2
程序
#include <iostream>
using namespace std;
const int N = 1002;
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++){
scanf("%d",&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,y1,x2,y2,c;
cin >> x1 >>y1 >> x2 >> y2 >> c;
insert(x1,y1,x2 ,y2,c);
}
//b的前缀和
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++){
printf("%d ",b[i][j]);
}
puts("");
}
}
位运算
说明
模板
求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n //作用： 10100 --> 100 1010110 --> 10
题目
二进制中1的个数
程序
//x 二进制中1的个数
#include <bitset>
#include <iostream>
using namespace std;
//返回x的最后一位1 例如 10100 --> 100 1010110 --> 10
int lowbit(const int x){
return x&(-x);
}
int main(){
int x,i=0;
cin >> x;
cout << bitset<sizeof(int)*8>(x) <<endl; // 调用库函数打印二进制数
for(int k=31;k>=0;k--) cout << (x>>k&1); // 利用位运算-x的二进制表中第k位是几？ x>>k &1 的方法打印二进制
cout << endl;
while(x){
x-=lowbit(x); // 10100 - 100 --> 10000 -10000 --> 00000 不断减去为1 的后几位
i++;
}
cout << "number of bit 1 : " << i << endl;
return 0;
}
双指针算法
说明
模板
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
// 具体问题的逻辑
}
常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
题目
1、最长序列
题目描述
给定一个长度为$n$的整数序列，请找出最长的不包含重复数字的连续子序列，输出它的长度。
输入格式
第一行包含整数$n$。
第二行包含$n$个整数（均在0~100000范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复数字的连续子序列的长度。
数据范围
$1≤n≤100000$
样例
输入样例：
5
1 2 2 3 5
输出样例：
3
程序
using namespace std;
const int N =100010;
int a[N],s[N];
int main(){
int n;
int res=0;
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 <<endl;
return 0;
}
2、数组元素的目标和
题目描述
$给定两个升序排序的有序数组$A$和$B$，以及一个目标值$x$，请你求出满足$A[i] + B[j] = x$的数对$(i, j)。
$数据保证有唯一解。$
输入格式
$第一行包含三个整数n，m，x，分别表示A的长度，B的长度以及目标值x。$
$第二行包含n个整数，表示数组A。$
$第三行包含m个整数，表示数组B.$
输出格式
$共一行，包含两个整数 i 和 j。$
数据范围
$数组长度不超过1000000。$
$同一数组内元素各不相同。$
$1≤数组元素≤10^9$
样例
输入样例：
4 5 6
1 2 4 7
3 4 6 8 9
输出样例：
1 1
程序
#include <iostream>
using namespace std;
const int N=1000010;
int A[N];
int B[N];
int main(){
int n,m,x;
cin>> n>>m >> x;
for(int i=0;i<n;i++){
scanf("%d",&A[i]);
}
for(int i=0;i<m;i++) scanf("%d",&B[i]);
for(int i=0,j=m-1;i<n;i++){
while(j>0&&A[i]+B[j]>x) j--;
if(A[i]+B[j]==x) printf("%d %d",i,j);
}
return 0;
}
离散化
说明
实际上其主要思想是用一个数组来(这里记为all)存储大小两个数组之间的映射关系:
小的数组的下标和all的下标是一一对应的;
大的数组的下标是all存的值。
但是只有all数组还是不够的，all只是把大小数组的映射关系保存下来了，我们还需要一个find()函数，这样每次我们给它喂一个大数组的下标，它就会吐出来一个小数组的下标，这样就可以通过大数组的下标来访问小数组了。
步骤分为两步 去重 、二分
模板
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于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; // 映射到1, 2, ...n
}
题目描述
$假定有一个无限长的数轴，数轴上每个坐标上的数都是$0$，现在，我们首先进行 $n$ 次操作，每次操作将某一位置$x$上的数加$c$。近下来，进行 $m$ 次询问，每个询问包含两个整数$l$和$r$，你需要求出在区间$[l, r]$之间的所有数的和。$
输入格式
$第一行包含两个整数$n$和$m。
$接下来$ n$ 行，每行包含两个整数$x$和$c。
$再接下里 $m$ 行，每行包含两个整数$l$和$r。
输出格式
$共$m$行，每行输出一个询问中所求的区间内数字和。$
数据范围
$−109,
1≤n,m≤10^5,
−109,
−10000≤c≤10000$
样例
输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：
8
0
5
程序
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 300100;// l r x
vector<int> alls;
vector<pair<int,int>> add, query;
int a[N];
int s[N];
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; //找第一个大于x的数
else l =mid +1;
}
return r+1; // 因为要用前缀和，所以从1开始
}
int main(){
int n,m;
cin >> n>> m;
for(int i=0;i<n;i++){
int x,c;
cin >> x >> c;
add.push_back({x,c});
alls.push_back(x);
}
for(int 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){
a[find(item.first)]+= item.second;
}
//前缀和构建s[] s[x] = s[x-1]+a[x]
for(int i=1;i<= alls.size();i++) s[i] = s[i-1]+a[i];
//前缀和 计算[l,r]数
for(auto item : query){
int l=find(item.first),r=find(item.second);
cout << s[r] - s[l-1]<< endl;
}
return 0;
}
区间合并
说明
模板
// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
vector<pair<int,int>> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first){
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res;
}
题目描述
给定n个区间[l, r]，合并所有有交集的区间，输出合并完成后的区间个数。
例如：[1,3]和[2,6]可以合并为一个区间[1,6]。
输入格式
第一行包含整数$n$。
接下来$n$行，每行包含两个整数$ l$ 和 $r$。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
样例
输入样例：
5
1 2
2 4
5 6
7 8
7 9
输出样例：
3
程序
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int,int>> regs;
vector<pair<int,int>> merge(vector<pair<int ,int >> &segs){
vector<pair<int,int>> res;
sort(segs.begin(),segs.end());
int start = -2e9,end = -2e9; //无穷远
for(auto seg:segs){
if(end < seg.first){
if(start!=-2e9) res.push_back({start,end});
start = seg.first;end = seg.second;
} else{
end = max(end,seg.second);
}
}
if(start!=-2e9) res.push_back({start,end}); //记得加上最后一个，判断条件是为了避免空数组
return res;
}
int main(){
int n;
cin >> n;
for(int i=0;i<n;i++){
int l,r;
cin >> l>>r;
regs.push_back(pair<int,int>(l,r));
//regs.push_back({l,r}); // 另一种形式
}
vector<pair<int,int>> res = merge(regs);
cout << res.size() <<endl;
return 0;
}
若有收获，就点个赞吧
0 人点赞
