17年的时候在HDU新生赛的时候遇到这样一道题目， 当时对于这种题目， 只会n^2去数左边比他大的个数 再相加一下 就是答案了。
无奈n是1e5 毫无疑问的T了。 后来学长说这个不就是归并排序吗， 你去学一下归并就可以做了， 然后我去学了归并， 又交了一发，
结果竟然还是T(这Y的不是耍我玩吗）。 然后从另一位学长哪里听说了用线段树去求逆序对， 把n^2变成nlogn就不会T了，最后，
我又学了线段树，终于这回AC了。写这个帖子的时候，我顺便去HDU找了找这道题目，结果找不到这道题目，竟然没挂出来。。。。
庆幸的是当时比较勤奋，打完新生赛没几天就补上了，不然就没机会做这道题目了。
好了 废话不多说 我们先上一个n^2的数数算法。
1 int main() 2 { 3 int n; 4 while(cin >> n) 5 { 6 ans = 0; 7 for(int i = 1; i <= n; i++) 8 { 9 cin >> a[i]; 10 if(i%2==0 && a[i-1]>a[i]) 11 { 12 swap(a[i-1],a[i]); 13 ans++; 14 } 15 } 16 for(int i = 1; i <= n; i+=2) 17 { 18 for(int j = 1; j < i; j+=2) 19 { 20 if(a[j] > a[i]) ans++; 21 } 22 } 23 cout << ans << endl; 24 } 25 return 0; 26 }
n^2算法就是数一下前面有多少个数比现在这个数大 这样全部跑完只后就是逆序数了。
其中重点是 前面有多少个数比现在这个数大
但是每次从1for一遍到i的位置太浪费时间了
所以我们用线段树来优化这个数数过程
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define lson l,m,rt<<1 4 #define rson m+1,r,rt<<1|1 5 #define ll long long 6 const int N=100005; 7 int sum[N<<2], a[N]; 8 ll ans; 9 void Update(int c, int l, int r,int rt) 10 { 11 if(l == r) 12 { 13 sum[rt]++; 14 return; 15 } 16 int m = l+r >> 1; 17 if(c <= m) Update(c,lson); 18 else Update(c,rson); 19 sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 20 } 21 ll Query(int L, int R, int l, int r, int rt) 22 { 23 if(L <= l && r <= R) 24 return sum[rt]; 25 int m = l+r >> 1; 26 ll cnt = 0; 27 if(L <= m) cnt+=Query(L,R,lson); 28 if(m < R) cnt += Query(L,R,rson); 29 return cnt; 30 } 31 int main() 32 { 33 ios::sync_with_stdio(false); 34 cin.tie(0); 35 int n; 36 while(cin >> n) 37 { 38 ans = 0; 39 memset(sum, 0, sizeof(sum)); 40 for(int i = 1; i <= n; i++) 41 { 42 cin >> a[i]; 43 if(i%2==0 && a[i-1]>a[i]) 44 { 45 swap(a[i-1],a[i]); 46 ans++; 47 } 48 } 49 for(int i = 1; i <= n; i+=2) 50 { 51 ans+=Query(a[i],n,1,n,1); 52 Update(a[i],1,n,1); 53 } 54 cout <<ans << endl; 55 } 56 return 0; 57 }
线段树算法的精髓就是将出现过的数对应的位置标记一下（+1）
假设 i=k时， 查询一下区间 [a[k], n] 的区间和， 这个和就是（j < k && a[j] > a[k]) 的数目
然后在a[k] 的位置 +1
重复这个过程就能求出解了
是不是很疑惑为什么？
当查询区间的时候， 如果在后面的区间内查询到次数不为0时， 说明有几个比他大数在他前面出现过，
线段树写法的精髓就是标记位置 进行查询， 这就是线段树的写法。
当然还有树状数组的写法
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=100005; 4 int sum[N], a[N]; 5 int n; 6 int lowbit(int x) 7 { 8 return x&(-x); 9 } 10 void Update(int x) 11 { 12 while(x <= n) 13 { 14 sum[x]++; 15 x += lowbit(x); 16 } 17 } 18 int Query(int x) 19 { 20 int ans = 0; 21 while(x > 0) 22 { 23 ans += sum[x]; 24 x -= lowbit(x); 25 } 26 return ans; 27 } 28 int main() 29 { 30 ios::sync_with_stdio(false); 31 cin.tie(0); 32 while(cin >> n) 33 { 34 long long ans = 0; 35 memset(sum, 0, sizeof(sum)); 36 for(int i = 1; i <= n; i++) 37 { 38 cin >> a[i]; 39 if(i%2==0 && a[i-1]>a[i]) 40 { 41 swap(a[i-1],a[i]); 42 ans++; 43 } 44 } 45 for(int i = 1; i <= n; i+=2) 46 { 47 ans += Query(n) - Query(a[i]); 48 Update(a[i]); 49 } 50 cout << ans << endl; 51 } 52 return 0; 53 }
注意的是 线段树与树状数组求逆序对的时候 数值不能太大 比如a[i] <= 1e9的时候 就不能直接用树状数组和逆序数去求了，因为开不了那么大的空间。
但在这个时候 如果n不是很大 可以先对数据进行离散化 进行树状数组或者线段树处理数据。
PS: 本篇博客到这里就结束了，谢谢你的观看， 如果有疑惑可以在下方留言或者加我QQ：1073223357进行询问。
同时欢迎各路大牛对我代码中的漏洞进行指正。