位运算
<<
这个符号相当于将一个数二进制往左移动几位，如(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;
}希望这些对大家有用，三联必回
