poj 2299 Ultra-QuickSort 树状数组求逆序数离散化

题目链接:

题意:

求逆序数

题解:

树状数组可以求逆序数
但是数据50w，所以要离散化。
归并也可做：http://blog.csdn.net/zxy_snow/article/details/6257561
这位大牛不知道什么叫离散化写出了离散化 Orz “就排下序，重新编数，这个据说叫离散化 = =”

另外一种离散化方式吧 ( 其实就是排序，去重，找到原来的数应该放在什么位置，这样就产生了每个数对应一个位置[映射]，中间的间隙没有用。—》代码2

代码:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 typedef long long ll;
 7 #define MS(a) memset(a,0,sizeof(a))
 8 #define MP make_pair
 9 #define PB push_back
10 const int INF = 0x3f3f3f3f;
11 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
12 inline ll read(){
13     ll x=0,f=1;char ch=getchar();
14     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
15     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
16     return x*f;
17 }
18 //////////////////////////////////////////////////////////////////////////
19 const int maxn = 5e5+10;
20 
21 struct node{
22     int x,id;
23 }a[maxn];
24 int aa[maxn],bit[maxn];
25 
26 bool cmp(node k,node kk){
27     return k.x < kk.x;
28 }
29 
30 void add(int x,int v){
31     while(x<maxn){
32         bit[x] += v;
33         x += x&-x;
34     }
35 }
36 
37 ll sum(int x){
38     ll res = 0;
39     while(x > 0){
40         res += bit[x];
41         x -= x&-x;
42     }
43     return res;
44 }
45 
46 int main(){
47     int n;
48     while(cin>>n && n){
49         MS(bit);
50         for(int i=0; i<n; i++){
51             a[i].x = read();
52             a[i].id = i;
53         }
54         sort(a,a+n,cmp);
55         int p = 1;
56         aa[a[0].id] = p;
57         for(int i=1; i<n; i++){
58             if(a[i].x == a[i-1].x) aa[a[i].id] = p;
59             else aa[a[i].id] = ++p;
60         }
61 
62         // for(int i=0; i<n; i++){
63         //  cout << aa[i] << " ";
64         // }puts("");
65 
66         ll ans = 0;
67         for(int i=0; i<n; i++){
68             // cout << sum(aa[i]) << endl;
69             // cout << i << " " << i-sum(aa[i]) << endl;
70             ans += i-sum(aa[i]);
71             add(aa[i],1);
72             cout << aa[i] << endl;
73         }
74 
75         cout << ans << endl;
76 
77     }
78 
79     return 0;
80 }

离散2：

 1   for(int i=0; i<n; i++){
 2             a[i] = read();
 3             tmp[i] = a[i];
 4         }
 5         sort(tmp,tmp+n);
 6         int cnt = unique(tmp,tmp+n)-tmp;
 7 
 8         // for(int i=0; i<cnt; i++){
 9         //  cout << tmp[i] << " ";
10         // }puts("");
11 
12         ll ans = 0;
13         for(int i=0; i<n; i++){
14             int pos = lower_bound(tmp,tmp+cnt,a[i])-tmp;
15             pos++;
16             ans += i-sum(pos);
17             add(pos,1);
18         }

poj 2299 Ultra-QuickSort 树状数组求逆序数 离散化

题目链接:

题意:

题解:

代码:

poj 2299 Ultra-QuickSort 树状数组求逆序数离散化