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; }