逆序对

并归排序

#include<bits/stdc++.h>
const int N = 5e5+5;
int a[N],tmp[N];           //a[]是原数组，b[]用于合并两半部分
long long ans=0;           //记录逆序对数量
void Merge(int L, int mid, int R){    //合并
  int i=L,j=mid+1,t=L;
  while(i<=mid && j<=R) {
    if(a[i]>a[j]){
      ans += mid-i+1;      //记录逆序对数量。去掉这一行，就是纯的归并排序
      tmp[t++]=a[j++];
    }
    else tmp[t++]=a[i++];
  }
  //其中一半已经处理完。另一半还没有，它剩下的都是有序的，直接copy
  while(i<=mid) tmp[t++]=a[i++];
  while(j<=R) tmp[t++]=a[j++];
  for(i=L;i<=R;i++) a[i]=tmp[i];      //把排好序的b[]复制回去
}
void Mergesort(int L,int R) {         //分治
  if(L>=R) return;
  int mid= L + (R-L)/2;      //比这样写好：int mid=(L+R)/2; 因为L+R可能溢出
  Mergesort(L,mid);          //左半
  Mergesort(mid+1,R);        //右半
  Merge(L,mid,R);            //合并
}
int main() {
  int n; scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  Mergesort(1,n);            //归并排序，并统计逆序对
  printf("%lld\n",ans);
  return 0;
}

笔记：在对数组进行并归排序的过程中，记录调整排序过程的操作次数，就是逆序对的数量

偏序问题

#include <bits/stdc++.h>
#include<algorithm>
//using namespace std;
const int N = 500010;
#define lowbit(x) ((x) & - (x))
int tree[N],rank[N],n;              //注：rank是C++的保留字，如果加了using namespace std，编译通不过
void update(int x, int d) {         //单点修改：修改元素a[x], a[x] = a[x] + d
  while(x <= N) {
    tree[x] += d;
    x += lowbit(x);
  }
}
int sum(int x) {                   //查询前缀和：返回前缀和sum = a[1] + a[2] +... + a[x]
  int ans = 0;
  while(x > 0){
    ans += tree[x];
    x -= lowbit(x);
  }
  return ans;
}

struct point{ int num,val;}a[N];   //录入顺序、输入数字
bool cmp(point x,point y){         //排序规则：正序
  if(x.val == y.val) return x.num < y.num;       //如果相等，让先出现的更小
  return x.val < y.val;
}
int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++) {
    scanf("%d",&a[i].val);
    a[i].num = i;                  //记录顺序，用于离散化
  }
  std::sort(a+1,a+1+n,cmp);        //排序
  for(int i=1;i<=n;i++) rank[a[i].num]=i;        //离散化，得到新的数字序列rank[]
  long long ans=0;
  /*for(int i=1;i<=n;i++){         //正序处理
    update(rank[i],1);
    ans += i-sum(rank[i]); }*/
  for(int i=n;i>0;--i){            //倒序处理
    update(rank[i],1);
    ans += sum(rank[i]-1);
  }
  printf("%lld",ans);
  return 0;
}

笔记：逆序对不需要具体的数字，用离散化处理数字再放到树状数组避免超出题目限制空间，倒叙查找逆序，直接用sum返回的前缀和添加到ans中，正序：就要用 i 减去sum返回的前缀和才是逆序对。以下的表格是倒叙的运算过程

i	0 1 2 3 4 5 6 7 8	rank[i]	sum	ans
6	0 [1] 1 0 1 0 0 0 1	1	sum[1-1]	0
5	0 1 1 [1] 2 0 0 0 2	3	sum[3-1]	0+1
4	0 1 1 1 2 0 [1] 0 3	6	sum[6-1]	0+1+2
3	0 1 [2] 1 3 0 1 0 4	2	sum[2-1]	0+1+2+1
2	0 1 2 1 [4] 0 1 0 5	4	sum[4-1]	0+1+2+1+3
1	0 1 2 1 4 [1] 2 0 6	5	sum[5-1]	0+1+2+1+3+4