排序
快速排序
快排属于分治算法，分治算法都有三步：
- 分成子问题
- 递归处理子问题
- 子问题合并
```cpp
include
include
using namespace std; void quickSort(vector& q,int l,int r){ if(l>=r) return; int i=l-1,j=r+1,x=q[(l+r)>>1]; while(i<j){
} quickSort(q,l,j);//quick(q,l,i-1); quickSort(q,j+1,r);//quick(q,i,r); } int main(){ int n; cin>>n; vectordo i++;while(q[i]<x);do j--;while(q[j]>x);if(i<j) swap(q[i],q[j]);
q(n,0); for(int i=0;i<n;i++){
} quickSort(q,0,n-1); for(auto num:q){cin>>q[i];
} return 0; }cout<<num<<" ";
`while`循环结束后，`q[l..j] <= x`,`q[j+1..r] >= x`<br />注:`q[l..j] <= x`意为`q[l],q[l+1]...q[j-1],q[j]`的所有元素都`<= x`<a name="GRcht"></a>### 第k个数快排序实际上分了三段：<br />一次迭代输出的是：- 左边：小于等于x- 右边：大于等于x，分界点在i/j因此若是`i-l+1>需要的长度`，在前半段查<br />否则再后半段查，**因为后半段中，前面j前面部分确定已经小于此结果**，因此需要找<br />`j+1，r`中的第`k-(j-l+1)`个，即前面`j-l+1`个已经是小数了```cpp//这里填你的代码^^//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~#include<iostream>using namespace std;const int N=1000010;int q[N];int quickSort(int q[], int l, int r, int k){if(l>=r) return q[l];int i=l-1;int j=r+1;int 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]);}int left=j-l+1;if(left>=k){return quickSort(q,l,j,k);}else{return quickSort(q,j+1,r,k-(j-l+1));}}int main(){int n,k;cin>>n>>k;for(int i=0;i<n;i++) cin>>q[i];cout<<quickSort(q,0,n-1,k);return 0;}
归并排序
- 选取中点
- 排序
- 合并
```cpp
include
using namespace std; const int N=100010; int q[N]; int temp[N]; void mergeSort(int q[],int l,int r){ if(l>=r) return; int mid=(l+r)>>1; mergeSort(q,l,mid); mergeSort(q,mid+1,r); int k=0,i=l,j=mid+1; while(i<=mid && j<=r){
} while(i<=mid) temp[k++] = q[i++]; while(j<=r) temp[k++] = q[j++]; for(int i=l,k=0;i<=r;i++,k++){if(q[i]<=q[j]) temp[k++]=q[i++];else temp[k++]=q[j++];
} } int main(){ int n; cin>>n; for(int i=0;iq[i]=temp[k];
<a name="Sn5Tl"></a>### 逆序对的数量当前逆序对数量=前半边逆序对数量+后半边逆序对数量+合并过程中产生的逆序对<br />计算合并过程中的逆序对：- `if q[i]<=q[j]` , `(q[i], q[j]) `则不是逆序对。- `else if(q[i]>q[j])` `(q[i], q[j])`是逆序对，并且`q[i]....q[mid]`与`q[j]` 形成 `mid-i+1`个逆序对。```cpp#include<iostream>using namespace std;const int N=100010;int q[N];int temp[N];long long mergeSort(int q[],int l,int r){if(l>=r) return 0;int mid=(l+r)>>1;long long cnt=0;cnt+=mergeSort(q,l,mid);cnt+=mergeSort(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++];cnt+=mid-i+1;}}while(i<=mid) temp[k++]=q[i++];while(j<=r) temp[k++]=q[j++];for(int i=l,k=0;i<=r;i++,k++){q[i]=temp[k];}return cnt;}int main(){int n;cin>>n;for(int i=0;i<n;i++) cin>>q[i];cout<<mergeSort(q,0,n-1);return 0;}
二分查找
二分查找的核心不是有序性，而是边界，即存在边界能将数组分成两个区间，每段分别满足一个条件。
对于整数二分而言，可以对左边界和右边界进行》
两个二分查找的板子：
void binarySearch1(int l,int r){while(l<r){int mid=(l+r)>>1;if(check(mid)) r=mid;else l=mid+1;}}//求右边界的时候void binarySerch2(int l,int r){while(l<r){int mid=(l+r+1)>>1;if(check(mid)) l=mid;else r=mid-1;}}
:::info 注意的点是当l=mid时需要向上取整，因为C++默认是向下取整的。 :::
数的范围
#include<iostream>using namespace std;const int N=100010;int vec[N];int main(){int n;cin>>n;int q;cin>>q;for(int i=0;i<n;i++){cin>>vec[i];}while(q--){int k;cin>>k;int l=0,r=n-1;while(l<r){int mid=(l+r)>>1;if(vec[mid]>=k) r=mid;else l=mid+1;}if(vec[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(vec[mid]<=k) l=mid;else r=mid-1;}cout<<l<<endl;}}return 0;}
数的三次方跟
#include<iostream>#include<cstdio>using namespace std;int main(){double l=-10000;double x;cin>>x;double r=10000;while(r-l>1e-9){double mid=(l+r)/2;if(mid*mid*mid<x) l=mid;else r=mid;}printf("%.6f", l);return 0;}
前缀和与差分
前缀和
数列：
前缀和：
- 如何求
递推：
for(i=1;i<=n;i++){S(i)=S(i-1)+a(i);}
- 作用：快速求一段数组区间的和
二维前缀和
如何求红色部分面积？
差分
差分实际上相当于前缀和的逆运算
数列：
构造：
使得
，b即称为a的差分，a即使b的前缀和
作用：
在[l,r]区间内，所有元素+c
用差分来做可以做到
;
只要用
，
即可。
:::info
关于构造问题：
一开始可以认为a数组全是0，但是进行了n次插入，即第一次在[1,1]区间插入了a_1，对应操作是b1+a_1,b_2-a；以此类推。 :::
双指针算法
:::info
双指针算法的核心思想是运用某些性质降低复杂度：
:::
基本的板子
for(int i=0,j=0;i<n;i++){j=i;while(j<n&&check(j))...}
位运算
查看n的二进制表示中第k位是几;
:::warning
- 先把第k位移动到最右边:
n>>k - 看个位是几:
x&1:::
lowbit
:::info
返回x的最后一位1x=1010 lobit(x)=10x=101000 lobit(x)=1000
:::
lobit(x)=x&-x
C++中负数是通过取反原数+1来实现的(补码)
:::warning
x=0010 -x=1110x&-x=0010
:::
离散化
:::warning
Definition:
例如有一系列数，值域在
，但是个数比较少，有时候可能需要用这些值作为下标来做，不能直接开辟一个如此巨大的数组，因此需要将这些数字映射到一个更小的值域区间。
:::
:::info
e.g.
a[]: 1,3,100,2000,50000
b[]: 0,1,2,3,4 映射后的数组
:::
可能的问题：
- a中可能有重复元素—需要去重
- 希望快速映射：如何算出x在a中的映射值？：因为a是有序的，可以用二分法
去重的操作：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}
区间和
例子是求区间和
using namespace std;
using PII=pair
vector
int find(int x){
//查找alls中小于或等于x的最大值的坐标
int l=0,r=alls.size()-1;
while(l
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(int i=1;i<=alls.size()+1;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;
}
<a name="TWB2K"></a>## 区间合并<br />区间合并：快速地将有交集的区间进行合并:::info边界情况：只有端点相交也算是相交:::1. 按照区间左端点排序1. 扫描整个区间，将可能有交集的区间合并1. 扫描过程中维护一个当前的区间1. 三种情况考虑1. 在当前区间内，不变1. 末尾超出了，更新区间范围1. 无交集，此区间更换为当前的区间，原来区间存入```cpp#include<iostream>#include<vector>#include<algorithm>using namespace std;using PII=pair<int,int>;vector<PII> seg;void merge(vector<PII>& segs){vector<PII> res;/*auto cmp=[](const PII a, const PII b){return a.first>b.first;//pair排序默认先拍左端点};*/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});//防止只有一个区间的情况，and将最后一个区间更新进去segs=res;}int main(){int n;cin>>n;for(int i=0;i<n;i++){int l,r;cin>>l>>r;seg.push_back(make_pair(l,r));}merge(seg);cout<<seg.size()<<endl;return 0;}
若有收获，就点个赞吧
0 人点赞
