首页 > 代码库 > 逆序对 【线段树解法】
逆序对 【线段树解法】
逆序对 【线段树解法】
求逆序对问题是一个十分经典的算法问题，通常使用归并排序解决，经gster大神指点，写出了逆序对线段树写法，顺便练了练线段树。
题目传送门：http://noi.openjudge.cn/ch0204/7622/
代码：
1 /* 2 Segment_Tree 3 author: SHHHS 4 2016-09-28 12:35:17 5 */ 6 #include "bits/stdc++.h" 7 8 using namespace std ; 9 typedef long long QAQ ;10 const int maxN = 100100 ;11 struct SegTree { int l , r , sum ;};12 13 SegTree tr[ maxN<<2 ] ;14 int arr[ maxN ] ;15 void Build_Tree ( int x , int y , int i ) {16 tr[ i ].l = x ; tr[ i ].r = y ;17 if ( x==y ) return ;18 else {19 QAQ mid = ( tr[ i ].l + tr[ i ].r ) >> 1 ;20 Build_Tree ( x , mid , i<<1 ) ;21 Build_Tree ( mid +1 , y , i<<1|1 ) ;22 }23 }24 25 void Insert_Tree ( int q , int i ) {26 if ( q==tr[ i ].l && q==tr[ i ].r ) {27 tr[ i ].sum ++ ;28 return ;29 }30 else {31 QAQ mid = ( tr[ i ].l + tr[ i ].r ) >> 1 ;32 if ( q>mid ) Insert_Tree ( q , i<<1|1 ) ;33 else if ( q<=mid ) Insert_Tree ( q , i<<1 ) ;34 }35 tr[ i ].sum = tr[ i<<1 ].sum + tr[ i<<1|1 ].sum ;36 }37 38 QAQ Query_Tree ( int q , int w , int i ){39 if ( q<=tr[i].l && w>=tr[i].r ) {40 return tr[i].sum ;41 }42 else {43 QAQ mid=(tr[i].l+tr[i].r)>>1;44 if ( q>mid )return Query_Tree(q,w,i<<1|1);45 else if ( w<=mid )return Query_Tree(q,w,i<<1);46 else return Query_Tree(q,mid,i<<1) + Query_Tree(mid+1,w,i<<1|1);47 48 }49 }50 51 int main ( ) {52 int N ; 53 QAQ ans = 0;54 scanf ("%d",&N);55 for ( int i=1 ; i<=N ; ++i ) scanf ( "%d" , arr + i ) ;56 Build_Tree ( 1 , N , 1 ) ;57 for ( int i=1 ; i<=N ; ++i ) {58 int temp = arr [ i ] ;59 Insert_Tree ( temp , 1 ) ;60 ans += i - Query_Tree ( 1 , temp , 1 ) ;61 }62 printf ( "%lld" , ans ) ;63 return 0 ;64 }
逆序对 【线段树解法】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。