逆序数对的求法：

1. 冒泡排序法
2. 归并排序法（下面介绍的方法）

（一）逆序数

解题思路：

利用归并排序求逆序数对，每当右边的数大于左边的数时，左边剩余的数就是逆序对数

解题代码：

#include<bits/stdc++.h>
using namespace std;
int a[100010],b[100010];
long long int cnt=0;
void hebin(int l,int mid,int r){
	int p=l,q=mid+1;
	for(int i=l;i<=r;i++){
		if((a[p]<=a[q]&&p<=mid)||(q>r)){
			b[i]=a[p++];
		}
		else{
			b[i]=a[q++];
			cnt+=mid-p+1;
		}
	}
	for(int i=l;i<=r;i++) a[i]=b[i];
}
void gbsort(int l,int r){
	if(l==r) return ;
	int mid=(l+r)/2;
	gbsort(l,mid);
	gbsort(mid+1,r);
	hebin(l,mid,r);
}
int main(){
	int n,i;
	cin>>n;
	for(i=1;i<=n;i++){//最好使用1开头的，不用考虑边界
		scanf("%d",&a[i]);
	}
	gbsort(1,n);
	cout<<cnt<<endl;
	return 0;
} 

（二）兔子的逆序对

解题思路：

• 再按上题思路写会导致运行超时。
• 逆序对数=原总逆序对-[l,r]间逆序对+[l,r]间顺序对（原数列不需要反转）
• =原总逆序对-[l,r]间逆序对+（[l,r]间总对数-[l,r]间逆序对）
• =原总逆序对+[l,r]间总对数-2*[l,r]间逆序对
• 据题意只要判断逆序对数是否为偶数即可，所以后面2*[l,r]间逆序对可以忽略（最好忽略，因为这样就不用考虑每次反转都会让原数列变化的影响）
• 要更新总逆序对（算是考虑了原数列的变化）

解题代码：

#include<bits/stdc++.h>
using namespace std;
int a[100010],b[100010],i;
long long int k,ans,cnt1,cntn,cnts,zong,cnt=0;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
void hebin(int l,int mid,int r){
	int p=l,q=mid+1;
	for(i=l;i<=r;i++){
		if((a[p]<a[q]&&p<=mid)||q>r){
			b[i]=a[p++];
		}
		else{
			b[i]=a[q++];
			cnt+=mid-p+1;
		}
	}
	for(i=l;i<=r;i++){
		a[i]=b[i];
	}
}
void gbsort(int l,int r){
	if(l==r) return ;
	int mid=(l+r)/2;
	gbsort(l,mid);
	gbsort(mid+1,r);
	hebin(l,mid,r);
}
int main(){
	int n,m,l,r;
	n=read();
	for(i=1;i<=n;i++){
		a[i]=read();
	}
	gbsort(1,n);
	m=read();
	while(m--){	
		l=read();r=read();
		zong=(r-l+1)*(r-l)/2;
		ans=cnt-zong;//ans表示答案，cnt表示总逆序对，zong表示lr区间总对数
		if(ans&1) printf("dislike\n");
		else printf("like\n");
        cnt=ans;//记得更新总逆序数对
	}
	return 0;
}