POJ-2299 Ultra-QuickSort (树状数组)

题意：

　　给出了一个序列，序列中有n个数，现在每次操作能交换相邻的两个数，要求操作几次可以将这个序列转换为一个从小到大排序的序列。

题解：

　　我的解法是先把所有的数和位置存下来，pair排序一下，然后从最小的数开始遍历。因为最小的数的位置我们已经知道了，那么这个数左边的数都要和这个数交换，一共要进行pos-1次交换。这里我们用树状数组来实现求某个位置前面仍然在序列中的数的个数(经典操作,先给每个位置都add(1),然后每处理一个位置在这个位置上add(-1)。可以实现logn求前缀。)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAX_N = 5e5+9;
 7 typedef pair<long long,int> P;
 8 P vec[MAX_N];
 9 int res[MAX_N];
10 void add(int x,int num)
11 {
12     for(;x<MAX_N;x+=(x&-x))
13         res[x] += num;
14 }
15 long long sum(int x)
16 {
17     long long ans = 0;
18     for(;x>0;x-=(x&-x))
19         ans += res[x];
20     return ans;
21 }
22 int main()
23 {
24     int N,M,T;
25     while(cin>>N)
26     {
27         memset(res,0,sizeof(res));
28         if(N==0) break;
29         for(int i=1;i<=N;i++)
30         {
31             scanf("%lld",&vec[i].first);
32             vec[i].second = i;
33             add(i,1);
34         }
35         sort(vec+1,vec+N+1);
36         long long ans =0 ;
37         for(int i=1;i<=N;i++)
38         {
39             int pos = vec[i].second;
40             ans += sum(pos)-1;
41             add(pos,-1);
42         }
43         cout<<ans<<endl;
44     }
45     return 0;
46 }