nyoj117求逆序数(离散化+树状数组/归并排序)

题目链接：nyoj117

树状数组思路：

首先将输入的数组离散化，使各个元素比较接近，而不是离散的。

离散时用一个结构体，val表示原来输入的数，pos表示下标；接着对结构体按val的大小排序，此时，val和结构体的下标就是一个一一对应的关系，而且满足原来的大小关系。然后用数组reflect存储原来所有的大小信息。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const int N = 1000005; int reflect[N],c[N],n; struct node { int val; int pos; }s[N]; bool cmp(node x,node y) { if(x.val == y.val) return x.pos < y.pos; return x.val < y.val; } int lowbit(int x) { return x&(-x); } void update(int x) { while(x <= n) { c[x] += 1; x += lowbit(x); } } long long getsum(int x)//统计比x小的数 { long long sum = 0; while(x > 0) { sum += c[x]; x -= lowbit(x); } return sum; } int main() { int T,i; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i = 1; i <= n; i ++) scanf("%d",&s[i].val), s[i].pos = i; sort(s+1,s+n+1,cmp); for(i = 1; i <= n; i ++) reflect[s[i].pos] = i; memset(c,0,sizeof(c)); long long ans = 0; for(i = 1; i <= n; i ++) { update(reflect[i]); ans += i - getsum(reflect[i]);//i表示已经插入的数的个数 } printf("%lld\n",ans); } return 0; } 
     
    
   
  

#include
  
   
int a[1000005],temp[1000005];
long long sum;
void merge(int left,int mid,int right)
{
	int i = left,j = mid + 1;
	int k = left;
	while(i <=mid && j <= right)
	{
		if(a[i] <= a[j])
			temp[k ++] = a[i ++];
		else
		{
			temp[k ++] = a[j ++];
			sum += mid - i + 1;//关键
		}
	}
	while(i <= mid)
        temp[k ++] = a[i ++];

	while(j <= right)
        temp[k ++] = a[j ++];

	for(i = left ; i <= right; i ++)
		a[i] = temp[i];
}
void msort(int left,int right)
{
	if(left < right)
	{
		int mid = (left + right) >> 1;
		msort(left,mid);
		msort(mid + 1,right);
		merge(left,mid,right);
	}
}
int main()
{
	int i,n,T;
	scanf("%d",&T);
	while(T--)
	{
	    scanf("%d",&n);
		for(i = 0;i < n; i ++)
			scanf("%d",&a[i]);
        sum = 0;
		msort(0,n - 1);
		printf("%lld\n",sum);
	}
	return 0;
}