XDOJ 1024: 简单逆序对

题意：这题解法不唯一，我刚学线段树，就直接上线段树了，一般来说求逆序对，对序列离散化，然后对于原序列找出每个元素对应位置，然后依次放入线段树中，查找1-i-1区间，可以找出比a[i]小的数据数，然后用一共比它小的数减去这个数据，即为逆序对；

#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<cstring>
#include<cstdio>
#define N 1000005
#define p 1000000007
using namespace std;
typedef struct list {
	int x;
	int y;
	int date;
} list;
list b[4*N];
void built(int root,int first,int end) {
	if(first==end) {
		b[root].x=first;
		b[root].y=end;
		b[root].date=0;
		return ;
	}
	int mid=(first+end)/2;
	built(root*2,first,mid);
	built(root*2+1,mid+1,end);
	b[root].x=b[root*2].x;
	b[root].y=b[root*2+1].y;
	b[root].date=0;
}
void U(int root,int first,int end,int e) {
	if(first==end) {
		b[root].date++;
		return ;
	}
	int mid=(first+end)/2;
	if(e<=mid)  U(root*2,first,mid,e);
	else U(root*2+1,mid+1,end,e);
	b[root].date=b[root*2].date+b[root*2+1].date;
}
long long sum=0;
void Q(int root,int first,int end,int l,int r) {
	if(l<=first&&end<=r) {
		sum+=b[root].date;
		return ;
	}
	int mid=(first+end)/2;
	if(l<=mid)  Q(2*root,first,mid,l,r);
	if(r>mid)  Q(2*root+1,mid+1,end,l,r);
}
int a[N];
int d[20];
long long e[N];
int main() {
	int m;
	scanf("%d",&m);
	int n;
	for(int i=1; i<=m; i++) {
		scanf("%d",&n);
		memset(d,0,sizeof(d));
		for(int j=1; j<=n; j++) {
			scanf("%d",&a[j]);
			d[a[j]]++;
		}
		memset(e,0,sizeof(e));
		for(int j=0; j<=9; j++) {
			for(int k=j-1; k>=0; k--) {
				e[j]+=d[k];
			}
		}
		built(1,0,9);
		long long ans=0;
		for(int j=1; j<=n; j++) {
			sum=0;
			if(a[j]==0) {
				U(1,0,9,a[j]);
			} else {
				Q(1,0,9,0,a[j]-1);
				sum=sum%p;
				e[a[j]]=e[a[j]]%p;
				ans=ans%p;
				ans=(ans+e[a[j]]-sum)%p;
				U(1,0,9,a[j]);
			}
		}
		printf("%lld
",ans);
	}
	return 0;
}