本文主要是介绍Codeforces Round #240 (Div. 2) E分治算法探究1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Codeforces Round #240 (Div. 2) E
http://codeforces.com/contest/415/problem/E
2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。
图一： 划分子问题。
图二： 分而治之，=> 合并 。
图三： 回溯：计算第3层，逆序对 1 ， 正序对3
图四： 回溯：计算第2层，逆序对 3 ， 正序对5
图五： 回溯：计算第1层，逆序对 8 ， 正序对8 。
1 、每次翻转操作时， 逆序对变为顺序对， 顺序对变为逆序。
2 、翻转x层。 1至x-1层的值不会变化， 变化的是x-最底层。
3、题目是分成2^q份 <=> 翻转n - q + 1 层
const int Max_N = 1<<21 ;
int x[Max_N] ;
LL bigger[32] , smaller[32];void Divide(int L , int R , int dep){if(L == R) return ;int M = (L + R) >> 1 ;Divide(L , M , dep+1) ;Divide(M+1 , R , dep+1) ;for(int i = M+1 ; i <= R ; i++){bigger[dep] += (LL)((x + M + 1) - upper_bound(x+L , x+M+1 , x[i]));smaller[dep] += (LL)(lower_bound(x+L , x+M+1 , x[i]) - (x+L)) ;}sort(x+L , x+R+1) ;
}int main(){int n , i , m , q ;LL ans ;while(cin>>n){for(i = 1 ; i <= (1<<n) ; i++)scanf("%d" ,&x[i]) ;memset(bigger , 0 , sizeof(bigger)) ;memset(smaller , 0 , sizeof(smaller)) ;Divide(1 , 1<<n , 1) ;ans = 0 ;for(i = 1 ; i <= n ; i++)ans += bigger[i] ;cin>>m ;while(m--){scanf("%d" ,&q) ;for(i = n - q + 1 ; i <= n ; i++){ans -= bigger[i] ;ans += smaller[i] ;swap(bigger[i] , smaller[i]) ;}printf("%I64d\n" ,ans) ;}}return 0;
}这篇关于Codeforces Round #240 (Div. 2) E分治算法探究1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
