Codeforces Round 240 (Div. 1) C. Mashmokh and Reverse Operation（分治+逆序对）

原题链接：C. Mashmokh and Reverse Operation

---

题目大意：

---

给出一个长度为 $2^n$ 的正整数数组 $a$ ，再给出 $m$ 次操作。

每次操作给出一个数字 $q$ ，把数组分为 $2^{n-q}$ 个长度为 $2^q$ 的段，然后每段执行一次翻转操作，操作完后输出当前数组的逆序对数量。

分段操作：$[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}]$

翻转操作：$[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}]$

每次操作会改变原数组，并且都要输出操作完后逆序对的数量。

解题思路：

---

很有意思的分治归并排序题。

首先发现我们数组长度是 $2$ 的次幂，且每次分段长度也都是 $2$ 的次幂，暗示我们可以向着分治的方向去思考。

我们知道：逆序对 $+$ 顺序对 $=\frac{n\cdot (n-1)}{2}$ 其中 $n$ 为区间长度。

我们将一个区间翻转时，本质上就是将逆序对的值和顺序对的值交换了一下，因为本来逆序的翻转之后就变成顺序的了。

这样类似将数组分成一段段的 $2$ 次幂长度，我们考虑可以考虑类似归并排序的分治方法。

归并排序是在排序的过程中同时算出每一层的逆序对，然后相加每层得到的逆序对，从而得到整个原数组的逆序对的。

假设原数组 $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]$

（右上角角标为将该层排好序时得到的逆序对数量，叶子层（第 $0$ 层）均为 $0$ 就不做标记了）

那么总的逆序对数就是所有层角标相加之和： $7+2+2+0+1+0+1=13$ 对。

我们考虑将区间长度为 $2^1$ 的段全翻转，看看会造成什么影响。

$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]$

那么总的逆序对数就是 $7+2+2+1+0+1+0=13$ 对。

可以发现，我们只有在第 $1\to 0$ 层往下的所有层逆序对被改变了，即顺序对和逆序对交换了，而其他层 $n\to 2$ 层则无变化。

因为归并到第 $0\to i$ 层前，其下的所有层是在做 边排序边计算 的过程，因此无论其下层的顺序是怎么样的，最终数组 排序 到到第 $i$ 层时的状态都是唯一确定的，不会影响到上一层。

比如我们修改前的第 $1$ 层，和我们原数组的第 $1$ 层状态是相同的，只有逆序对和顺序对的角标被改变了。

同理，无论按何种顺序如何翻转第 $2^q$ 层，其只会影响第 $0\to q$ 的逆序对状态，而不会影响第 $q+1\to n$ 层逆序对的状态。

因此，我们先对原数组做一次归并排序，同时记录每一层的逆序对状态，和顺序对状态。

对每次的修改，对 $1\to q$ 层直接交换顺序对和逆序对的值（第 $0$ 层全是 $0$ ，可以不管），其余不变（或者用 $2^{n-q}\cdot \frac{2^q\cdot (2^q-1)}{2}-$当前层逆序对之和，不过有个 $2$ 的次幂，比较麻烦）。

交换完后，统计所有层的逆序对之和就是我们的答案了。

时间复杂度：$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);//求顺序对while (i <= mid && j <= r) {if (a[i] < a[j]) {cnt[dep][1] += r - j + 1;++i;} else {++j;}}//求逆序对并同时将数组排序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;
}