树状数组求逆序对与luogu1908 - 逆序对

 1 //由于我们可以把s[i]直接累加到ans中，故不需要开s数组
 2 //<&x>为跳转符
 3 //以下是未离散化代码
 4 //以下是C++代码
 5 
 6 #include<cstdio>
 7 
 8 int a[40006];
 9 //由于题目没有说明a[i]的最大值（只说是正整数），故将c数组范围往大的开
10 //max为a[i]最大值
11 int c[5000000] = {0}, n, ans(0), max(0);
12 
13 void add_c(int x);                           //更新c数组
14 int sum(int x);                              //求小于a[i]的数的个数
15 int lowbit(const int &x);
16 
17 int main() 
18 {
19     scanf("%d", &n);
20     for(int i = 1; i <= n; ++i)
21     {
22         scanf("%d", &a[i]); 
23                 max = max < a[i] ? a[i] : max;
24     }
25         //与以往代码不同，本次我将处理放在读入的循环之后
26         //这是因为a[i]的范围不确定，在<&x>处循环到5000000太耗时间
27     for(int i = 1; i <= n; ++i)
28     {
29         add_c(a[i]);
30         ans += i - sum(a[i]);
31     }
32     printf("%d\n", ans);
33 }
34 
35 void add_c(int x)
36 {
37     while (x <= max)                         //<&x>
38     {
39         ++c[x];
40         x += lowbit(x);
41     }
42 }
43 
44 int sum(int x)
45 {
46     int s(0);
47     while (x > 0)
48     {
49         s += c[x];
50         x -= lowbit(x);
51     }
52     return s;
53 }
54 
55 int lowbit(const int &x)
56 {
57     return x & (-x);
58 }

 1 //以下是加入离散化的代码，离散化部分从<&beg>到<&end>，其余部分有较小规模改动
 2 //以下是C++代码
 3 
 4 #include<cstdio>
 5 #include<algorithm>
 6 
 7 struct map__
 8 {
 9     int in, to, po;                   //in:a[i]值;to:离散化目标值;po:输入顺序
10 }a[40006];
11 int c[5000000] = {0}, n, ans(0), p(0);//p:离散化目标最大值(max(to))
12 
13 //cmp1与cmp2分别用于in与po的sort排序
14 inline bool cmp1(const map__ &a, const map__ &b);
15 inline bool cmp2(const map__ &a, const map__ &b);
16 void add_c(int x);
17 int sum(int x);
18 int lowbit(const int &x);
19 
20 int main() 
21 {
22     scanf("%d", &n);
23     for(int i = 1; i <= n; ++i)
24     {
25         scanf("%d", &a[i].in);
26         a[i].po = i;
27     }
28     //<&beg>
29     std::sort(a + 1, a + n + 1, cmp1);
30     for(int i = 1; i <= n; ++i)
31     {
32         if(a[i].in == a[i - 1].in) a[i].to = a[i - 1].to;
33         else a[i].to = ++p;
34     }
35     std::sort(a + 1, a + n + 1, cmp2);
36     //<&end>
37     for(int i = 1; i <= n; ++i)
38     {
39         add_c(a[i].to);
40         ans += i - sum(a[i].to);
41     }
42     printf("%d\n", ans);
43 }
44 
45 inline bool cmp1(const map__ &a, const map__ &b)
46 {
47     return a.in < b.in;
48 }
49 
50 inline bool cmp2(const map__ &a, const map__ &b)
51 {
52     return a.po < b.po;
53 }
54 
55 void add_c(int x)
56 {
57     while (x <= p)
58     {
59         ++c[x];
60         x += lowbit(x);
61     }
62 }
63 
64 int sum(int x)
65 {
66     int s(0);
67     while (x > 0)
68     {
69         s += c[x];
70         x -= lowbit(x);
71     }
72     return s;
73 }
74 
75 int lowbit(const int &x)
76 {
77     return x & (-x);
78 }