原題鏈接：C. Mashmokh and Reverse Operation

---

題目大意：

---

給出一個(gè)長(zhǎng)度為 $2^n$ 的正整數(shù)數(shù)組 $a$ ，再給出 $m$ 次操作。

每次操作給出一個(gè)數(shù)字 $q$ ，把數(shù)組分為 $2^{n?q}$ 個(gè)長(zhǎng)度為 $2^q$ 的段，然后每段執(zhí)行一次翻轉(zhuǎn)操作，操作完后輸出當(dāng)前數(shù)組的逆序?qū)?shù)量。

分段操作：$[a_1,a_2,...,a_{2^q}],[a_{2^q+1},a_{2^q+2},...,a_{2^{q+1}}],...,[a_{2^{n?1}+1},a_{2^{n?1}+2},...,a_{2^n}]$

翻轉(zhuǎn)操作：$[a_{2^q},a_{2^q?1},...,a_1],[a_{2^{q+1}},a_{2^q?1},...,a_{2^q+1}],...,[a_{2^n},a_{2^n?1},...,a_{2^{n?1}+1}]$

每次操作會(huì)改變?cè)瓟?shù)組，并且都要輸出操作完后逆序?qū)Φ臄?shù)量。

解題思路：

---

很有意思的分治歸并排序題。

首先發(fā)現(xiàn)我們數(shù)組長(zhǎng)度是 $2$ 的次冪，且每次分段長(zhǎng)度也都是 $2$ 的次冪，暗示我們可以向著分治的方向去思考。

我們知道：逆序?qū)?$+$ 順序?qū)?$=\frac{n?(n?1)}{2}$ 其中 $n$ 為區(qū)間長(zhǎng)度。

我們將一個(gè)區(qū)間翻轉(zhuǎn)時(shí)，本質(zhì)上就是將逆序?qū)Φ闹岛晚樞驅(qū)Φ闹到粨Q了一下，因?yàn)楸緛砟嫘虻姆D(zhuǎn)之后就變成順序的了。

這樣類似將數(shù)組分成一段段的 $2$ 次冪長(zhǎng)度，我們考慮可以考慮類似歸并排序的分治方法。

歸并排序是在排序的過程中同時(shí)算出每一層的逆序?qū)?#xff0c;然后相加每層得到的逆序?qū)?#xff0c;從而得到整個(gè)原數(shù)組的逆序?qū)Φ摹?/p>

假設(shè)原數(shù)組 $a$ 為 $[4,5,7,1,3,6,8,2]$ ，我們畫出歸并排序樹看看：

$3:[1,2,3,4,5,6,7,8{]}^7$
$2:[1,4,5,7{]}^2,[2,3,6,8{]}^2$
$1:[4,5{]}^0,[1,7{]}^1,[3,6{]}^0,[2,8{]}^1$
$0:[4],[5],[7],[1],[3],[6],[8],[2]$

（右上角角標(biāo)為將該層排好序時(shí)得到的逆序?qū)?shù)量，葉子層（第 $0$ 層）均為 $0$ 就不做標(biāo)記了）

那么總的逆序?qū)?shù)就是所有層角標(biāo)相加之和： $7+2+2+0+1+0+1=13$ 對(duì)。

我們考慮將區(qū)間長(zhǎng)度為 $2^1$ 的段全翻轉(zhuǎn)，看看會(huì)造成什么影響。

$3:[1,2,3,4,5,6,7,8{]}^7$
$2:[1,4,5,7{]}^2,[2,3,6,8{]}^2$

$1^{\prime }:[4,5{]}^1,[1,7{]}^0,[3,6{]}^1,[2,8{]}^0$
$0^{\prime }:[5],[4],[1],[7],[6],[3],[2],[8]$

那么總的逆序?qū)?shù)就是 $7+2+2+1+0+1+0=13$ 對(duì)。

可以發(fā)現(xiàn)，我們只有在第 $1\to 0$ 層往下的所有層逆序?qū)Ρ桓淖兞?#xff0c;即順序?qū)湍嫘驅(qū)粨Q了，而其他層 $n\to 2$ 層則無變化。

因?yàn)闅w并到第 $0\to i$ 層前，其下的所有層是在做 邊排序邊計(jì)算 的過程，因此無論其下層的順序是怎么樣的，最終數(shù)組 排序 到到第 $i$ 層時(shí)的狀態(tài)都是唯一確定的，不會(huì)影響到上一層。

比如我們修改前的第 $1$ 層，和我們?cè)瓟?shù)組的第 $1$ 層狀態(tài)是相同的，只有逆序?qū)晚樞驅(qū)Φ慕菢?biāo)被改變了。

同理，無論按何種順序如何翻轉(zhuǎn)第 $2^q$ 層，其只會(huì)影響第 $0\to q$ 的逆序?qū)顟B(tài)，而不會(huì)影響第 $q+1\to n$ 層逆序?qū)Φ臓顟B(tài)。

因此，我們先對(duì)原數(shù)組做一次歸并排序，同時(shí)記錄每一層的逆序?qū)顟B(tài)，和順序?qū)顟B(tài)。

對(duì)每次的修改，對(duì) $1\to q$ 層直接交換順序?qū)湍嫘驅(qū)Φ闹?#xff08;第 $0$ 層全是 $0$ ，可以不管），其余不變（或者用 $2^{n?q}?\frac{2^q?(2^q?1)}{2}?$當(dāng)前層逆序?qū)χ?#xff0c;不過有個(gè) $2$ 的次冪，比較麻煩）。

交換完后，統(tǒng)計(jì)所有層的逆序?qū)χ途褪俏覀兊拇鸢噶恕?/p>

時(shí)間復(fù)雜度：$O(n\log n+q\log n)$

AC代碼：

#include <bits/stdc++.h>
using namespace std;using PII = pair<int, int>;
using i64 = long long;void solve() {int n;cin >> n;vector<int> a((1 << n) + 1);for (int i = 1; i <= (1 << n); ++i) {cin >> a[i];}vector cnt(n + 1, vector<i64>(2));vector<int> b(1 << n);auto Msort = [&](auto self, int l, int r, int dep) -> void {if (l >= r) return;int mid = l + r >> 1, i = l, j = mid + 1, k = 0;self(self, l, mid, dep - 1), self(self, mid + 1, r, dep - 1);//求順序?qū)?/span>while (i <= mid && j <= r) {if (a[i] < a[j]) {cnt[dep][1] += r - j + 1;++i;} else {++j;}}//求逆序?qū)Σ⑼瑫r(shí)將數(shù)組排序i = l, j = mid + 1;while (i <= mid && j <= r) {if (a[i] > a[j]) {cnt[dep][0] += mid - i + 1;b[k++] = a[j++];} else {b[k++] = a[i++];}}while (i <= mid) {b[k++] = a[i++];}while (j <= r) {b[k++] = a[j++];}for (i = l, j = 0; i <= r; ++i, ++j) {a[i] = b[j];}};Msort(Msort, 1, 1 << n, n);int q;cin >> q;for (int i = 1; i <= q; ++i) {int d;cin >> d;i64 ans = 0;//修改d層 則將 [1, d] 層的值全部交換一下for (int j = 1; j <= n; ++j) {if (j <= d) {swap(cnt[j][0], cnt[j][1]);}ans += cnt[j][0];}cout << ans << '\n';}
}signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1; //cin >> t;while (t--) solve();return 0;
}