正经题解|逆序对

当看到题解区全是某并排序身为线段树爱好者的我必须发一篇题解（
其实逆序对根本没必要用写也麻烦调也麻烦的归并排序，用简简单单的线段树不就好了
放代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N=5e5+5,N4=2e6+5;
struct Node{
	int l,r,val,tag;
}a[N4];
struct node{
	int x,id;
}A[N];
int num[N];
int cmp(node x,node y) {
	return x.x<y.x;
}
void pushup(int u) {
	a[u].val=a[u<<1].val+a[u<<1|1].val;
}
void pushdown(int u) {
	Node &root=a[u];
	if (root.tag) {
		Node &l=a[u<<1],&r=a[u<<1|1];
		l.val+=root.tag*(l.r-l.l+1);
		r.val+=root.tag*(r.r-r.l+1);
		l.tag+=root.tag;
		r.tag+=root.tag;
		root.tag=0;
	}
}
void build(int u,int l,int r) {
	a[u].l=l,a[u].r=r;
	if (l==r) {
		return;
	}
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
}
int query(int u,int l,int r) {
	if (a[u].l>=l&&a[u].r<=r) {
		return a[u].val;
	}
	pushdown(u);
	int mid=(a[u].l+a[u].r)>>1,val=0;
	if (l<=mid) {
		val+=query(u<<1,l,r);
	}
	if (r>mid) {
		val+=query(u<<1|1,l,r);
	}
	return val;
}
void add(int u,int l,int r,int x) {
	if (a[u].l>=l&&a[u].r<=r) {
		a[u].val+=x*(a[u].r-a[u].l+1);
		a[u].tag+=x;
		return;
	}
	pushdown(u);
	int mid=(a[u].l+a[u].r)>>1;
	if (l<=mid) {
		add(u<<1,l,r,x);
	}
	if (r>mid) {
		add(u<<1|1,l,r,x);
	}
	pushup(u);
}
int main() {
	int n,m=0;
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		scanf("%d",&A[i].x);
		A[i].id=i;
	}
	sort(A+1,A+1+n,cmp);
	for (int i=1,last=-2e9;i<=n;i++) {
		if (A[i].x!=last) {
			last=A[i].x;
			m++;
		}
		num[A[i].id]=m;
	}
	build(1,1,m);
	long long sum=0;
	for (int i=n;i>=1;i--) {
		sum+=query(1,1,num[i]-1);
		add(1,num[i],num[i],1);
	}
	printf("%lld",sum);
	return 0;
}

就是用时有点抽象（）