poj2299UltraQuickSort

求逆序数

第一种做法利用归并排序在进行两个升序数组归并时如果右边指针指向的那个数比左边小那从左边那个位置到mid的数都比右边那个数大所以比它大的数的个数就是左边那个数到mid之间的数依次类推

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 long long a[500001],num,x[500001],y[500001];
 4 long long  msort(long long low,long long mid,long long high)
 5  {
 6      long long  i,j,n1 = mid-low+1,n2 = high-mid;
 7      for(i = 1 ; i <= n1 ; i++)
 8          x[i] = a[low+i-1];
 9      for(i = 1 ; i <= n2 ; i++)
10          y[i] = a[mid+i];
11      long long k = low;
12      i = 1;
13      j = 1;
14      while(i<=n1&&j<=n2)
15      {
16          if(x[i]<=y[j])
17              a[k] = x[i++];
18          else
19          {
20              num+=mid-(low+i)+2;//加上i到mid之间的数
21              a[k] = y[j++];
22          }
23          k++;
24      }
25      while(i<=n1)
26          a[k++] = x[i++];
27      while(j<=n2)
28          a[k++] = y[j++];
29  }
30  void merge(long long low,long long high)
31  {
32      long long  mid;
33      if(low<high)
34      {
35          mid = (low+high)/2;
36          merge(low,mid);
37          merge(mid+1,high);
38          msort(low,mid ,high);
39      }
40  }
41 int main()
42 {
43     int i,j,k,n,m;
44     while(scanf("%d",&n)&&n)
45     {
46         num = 0;
47         for(i = 1; i <= n ; i++)
48         scanf("%d",&a[i]);
49         merge(1,n);
50         printf("%lld\n",num) ;
51     }
52     return 0;
53 }

第二种树状数组

树状数组时用来求和的从小到大排好序之后用一个数组记录原来位置的数现在在什么位置然后调用更新函数让原来那个位置标记为1 这样再调用getsum函数就可以得到原来这个位置前面有多少比它小的数依次加起来

View Code

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include<string.h>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef struct node
 7 {
 8     int a,p;
 9 }st;
10 st q[500001];
11 int re[500001],n,po[500001];
12 bool cmpp(st x, st y)
13 {
14     return x.a<y.a;
15 }
16 void add(int i,int da)
17 {
18     while(i<=n)
19     {
20        re[i]+=da;
21        i += i&(-i);
22     }
23 }
24 int getsum(int i)
25 {
26     long long s = 0;
27     while(i)
28     {
29         s+=re[i];
30         i-=i&(-i);
31     }
32     return s;
33 }
34 int main()
35 {
36     int i,j,m;
37     long long s1;
38     while(scanf("%d",&n)&&n)
39     {
40         s1 = 0;
41         memset(re,0,sizeof(re));
42         for(i = 1 ; i <= n ; i++)
43         {
44             scanf("%d",&q[i].a);
45             q[i].p = i;
46         }
47         sort(q+1,q+n+1,cmpp);
48         for(i = 1 ; i <= n ; i++)
49             po[q[i].p] = i;
50         for(i = 1 ; i <= n ; i++)
51         {
52             add(po[i],1);
53             s1+=(i-getsum(po[i]));
54         }
55         printf("%lld\n",s1);
56     }
57     return 0;
58 }