位运算
<<
这个符号相当于将一个数二进制往左移动几位，如(100110)2<<1=(001100)2。相当于乘以2的k次方
>>
这个符号相当于将一个数二进制往右移动几位，如(100110)2<<1=(0100110)2。相当于除以2的k次方
归并排序
先看一个视频一分钟了解"归并排序"_哔哩哔哩_bilibili
main函数
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>x[i];
msort(0,n-1);
for(int i=0;i<n;i++) cout<<x[i];
return 0;
}这个我相信大家不看就知道怎么写吧
msort函数
msort函数的意义是“对数组l号到r号排序”
思考五分钟：代码该如何填呢
void msort(int l,int r){
if(l==r) return ;
int mid=(l+r)>>1;
msort(l,mid);
msort(mid+1,r);
*************************************************
* *
* 将左右已经排序的两个部分合并 *
* *
*************************************************
}我们可以使用双游标，给出代码和注释
void msort(int l,int r){
if(l==r) return ;
int mid=(l+r)>>1;
msort(l,mid);
msort(mid+1,r);
int i=l,j=mid+1;//双游标
for(int k=l;k<=r;k++){
if(i>mid) y[k]=x[j++];//如果左部分用完，填上右部分当前数
else if(j>r) y[k]=x[i++];//如果右部分用完，填上左部分当前数
else if(x[i]<=x[j]) y[k]=x[i++];//如果左部分当前数小于右部分当前数，填上左部分当前数
else y[k]=x[j++];//否则填上右部分当前数
}
}分析一下时间复杂度
但是，我们发现这个算法空间复杂度不行啊，但是我们不用管他，因为这个算法是稳定排序
逆序对问题
树状数组
#include <bits/stdc++.h>
using namespace std;
int tree[500010],ranks[500010],n;
long long ans;
struct point
{
int num,val;
}a[500010];
inline bool cmp(point q,point w)
{
if(q.val==w.val)
return q.num<w.num;
return q.val<w.val;
}
inline void insert(int p,int d)
{
for(;p<=n;p+=p&-p)
tree[p]+=d;
}
inline int query(int p)
{
int sum=0;
for(;p;p-=p&-p)
sum+=tree[p];
return sum;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i].val),a[i].num=i;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
ranks[a[i].num]=i;
for(int i=1;i<=n;i++)
{
insert(ranks[i],1);
ans+=i-query(ranks[i]);
}
printf("%lld",ans);
return 0;
} 此处不细讲
归并排序
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=10000009;
int n,x[N],y[N];
ll solve(ll l,ll r){
if(l==r)return 0;
ll mid=(l+r)>>1;
ll ret=0;
ret+=solve(l,mid);
ret+=solve(mid+1,r);
ll i=l,j=mid+1;
for(ll k=l;k<=r;k++){
if(i>mid)y[k]=x[j++];
else if(j>r)y[k]=x[i++];
else if(x[i]<=x[j])y[k]=x[i++];
else {ret+=mid-i+1;y[k]=x[j++];}
}
for(ll k=l;k<=r;k++)x[k]=y[k];
return ret;
}
int main(){
int cnt=0;
cin>>n;
for(ll i=0;i<n;i++)cin>>x[i];
cout<<solve(0,n-1)<<endl;
return 0;
}希望这些对大家有用，三联必回
