Codeforces 414(#240 Div1) C. Mashmokh and Reverse Operation

問題

長さ2^nの数列a[i]がある。
これに以下のクエリがm個来るので処理せよ。

i番目のクエリでは、0≦qi≦nなる整数qiが来る。
数列を2^qi個ずつに区切り、それぞれを反転させた後、同じ順に結合した数列を新しいa[i]とする。
クエリ毎に、操作後のa[i]における転置(i < jでa[i] > a[j]なる(i, j)の個数)を求めよ。

制約条件

n≦20

方針

マージソートの各段の途中で転置の個数を覚えておく。
a[i]を逆順にしておいた数列においても、マージソートの各段の途中で転置の個数を覚えておく。
整数qiの操作がきたら、qi段目以降の転置の個数は、逆順にしておいた数列のほうの転置になる。

ソースコード

const int MX = (1 << 20) + 5;
int N, n, a[1 << 20], b[1 << 20], c[1 << 20];
ll cnt[21][2];

ll merge(int *a, int w){
	int *b = a + w;
	vi v;
	ll res = 0;
	int cnt = 0;
	
	for(int i = w - 1, j = w - 1; i >= 0 || j >= 0;){
		
		if(j < 0 || i >= 0 && a[i] > b[j]){
			if(i < w - 1 && a[i] == a[i + 1]) cnt++;
			else cnt = 1;
			v.pb(a[i--]);
		}
		else{
			res += w - i - 1;
			if(i < w - 1 && a[i + 1] == b[j]) res -= cnt;
			else cnt = 0;
			
			v.pb(b[j--]);
		}
	}
	rep(i, 2 * w) a[i] = v[2 * w - i - 1];
	return res;
}

int main(){
	
	scanf("%d", &N);
	n = 1 << N;
	rep(i, n) scanf("%d", a + i);
	
	rep(i, n) b[i] = c[i] = a[i];
	reverse(c, c + n);
	
	
	for(int i = N - 1; i >= 0; i--){
		
		int w = 1 << (N - i);

		rep(j, n >> (N - i)){
			cnt[i][0] += merge(b + j * w, w / 2);
			cnt[i][1] += merge(c + j * w, w / 2);
		}
	}
	int m;
	
	scanf("%d", &m);
	while(m--){
		int t;
		scanf("%d", &t);
		
		for(t = N - t; t < N; t++) swap(cnt[t][0], cnt[t][1]);
		
		ll ans = 0;
		rep(i, N) ans += cnt[i][0];
		printf("%I64d\n", ans);
	}
	
	return 0;
}