在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
现在，给你一个N个元素的序列，请你判断出它的逆序数是多少。
比如 1 3 2 的逆序数就是1。
输入 第一行输入一个整数T表示测试数据的组数（1<=T<=5) 每组测试数据的每一行是一个整数N表示数列中共有N个元素（2〈=N〈=1000000） 随后的一行共有N个整数Ai(0<=Ai<1000000000)，表示数列中的所有元素。 数据保证在多组测试数据中，多于10万个数的测试数据最多只有一组。 输出 输出该数列的逆序数 样例输入 2 2 1 1 3 1 3 2 样例输出 0 1 tips：最大数值达到了1e9的级别，线段树是无法开到那么大的数组的，因此需要离散化+线段树。 #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; const int maxn=1001000; int sum[maxn<<2]; int n; struct node{ int v,i; friend bool operator <(node n1,node n2) { if(n1.v==n2.v){ return n1.i<n2.i; } else return n1.v<n2.v; } }num[maxn<<2]; #define ll long long ll ans; void pushup(int rt) { sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void update(int x,int rt,int l,int r) { if(l==r) { sum[rt]++; return; } int m=(l+r)>>1; if(x<=m)update(x,rt<<1,l,m); else update(x,rt<<1|1,m+1,r); pushup(rt); } int query(int x,int y,int rt,int l,int r) { if(x<=l&&y>=r) { return sum[rt]; } int ret=0; int m=(l+r)>>1; if(x<=m)ret+=query(x,y,rt<<1,l,m); if(y>m)ret+=query(x,y,rt<<1|1,m+1,r); return ret; } int main() { int t;scanf("%d",&t); while(t--) { memset(sum,0,sizeof(sum)); ans=0; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&num[i].v); num[i].i=i+1; } sort(num,num+n); for(int i=0;i<n;i++) { update(num[i].i,1,1,n); ans+=query(num[i].i+1,n,1,1,n); } cout<<ans<<endl; } return 0; }