求职网站开发多少钱,qq企业邮箱格式,搭建网站的主要风险,做APP必须要有网站么原题链接#xff1a;C. Mashmokh and Reverse Operation 题目大意#xff1a; 给出一个长度为 2 n 2^{n} 2n 的正整数数组 a a a #xff0c;再给出 m m m 次操作。
每次操作给出一个数字 q q q #xff0c;把数组分为 2 n − q 2^{n-q} 2n−q 个长度为 2 q 2^{q} 2…原题链接C. Mashmokh and Reverse Operation 题目大意 给出一个长度为 2 n 2^{n} 2n 的正整数数组 a a a 再给出 m m m 次操作。
每次操作给出一个数字 q q q 把数组分为 2 n − q 2^{n-q} 2n−q 个长度为 2 q 2^{q} 2q 的段然后每段执行一次翻转操作操作完后输出当前数组的逆序对数量。
分段操作 [ 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_{1},a_{2},...,a_{2^q}],[a_{2^{q}1},a_{2^{q}2},...,a_{2^{q1}}],...,[a_{2^{n-1}1},a_{2^{n-1}2},...,a_{2^{n}}] [a1,a2,...,a2q],[a2q1,a2q2,...,a2q1],...,[a2n−11,a2n−12,...,a2n]
翻转操作 [ 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 ] [a_{2^{q}},a_{2^{q}-1},...,a_{1}],[a_{2^{q1}},a_{2^{q}-1},...,a_{2^{q}1}],...,[a_{2^{n}},a_{2^{n}-1},...,a_{2^{n-1}1}] [a2q,a2q−1,...,a1],[a2q1,a2q−1,...,a2q1],...,[a2n,a2n−1,...,a2n−11]
每次操作会改变原数组并且都要输出操作完后逆序对的数量。
解题思路 很有意思的分治归并排序题。
首先发现我们数组长度是 2 2 2 的次幂且每次分段长度也都是 2 2 2 的次幂暗示我们可以向着分治的方向去思考。
我们知道逆序对 顺序对 n ⋅ ( n − 1 ) 2 \frac{n \cdot(n-1)}{2} 2n⋅(n−1) 其中 n n n 为区间长度。
我们将一个区间翻转时本质上就是将逆序对的值和顺序对的值交换了一下因为本来逆序的翻转之后就变成顺序的了。
这样类似将数组分成一段段的 2 2 2 次幂长度我们考虑可以考虑类似归并排序的分治方法。
归并排序是在排序的过程中同时算出每一层的逆序对然后相加每层得到的逆序对从而得到整个原数组的逆序对的。
假设原数组 a a a 为 [ 4 , 5 , 7 , 1 , 3 , 6 , 8 , 2 ] [4,5,7,1,3,6,8,2] [4,5,7,1,3,6,8,2] 我们画出归并排序树看看 3 : [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ] 7 3:[1,2,3,4,5,6,7,8]^{7} 3:[1,2,3,4,5,6,7,8]7 2 : [ 1 , 4 , 5 , 7 ] 2 , [ 2 , 3 , 6 , 8 ] 2 2:[1,4,5,7]^{2},[2,3,6,8]^{2} 2:[1,4,5,7]2,[2,3,6,8]2 1 : [ 4 , 5 ] 0 , [ 1 , 7 ] 1 , [ 3 , 6 ] 0 , [ 2 , 8 ] 1 1:[4,5]^{0},[1,7]^{1},[3,6]^{0},[2,8]^{1} 1:[4,5]0,[1,7]1,[3,6]0,[2,8]1 0 : [ 4 ] , [ 5 ] , [ 7 ] , [ 1 ] , [ 3 ] , [ 6 ] , [ 8 ] , [ 2 ] 0:[4],[5],[7],[1],[3],[6],[8],[2] 0:[4],[5],[7],[1],[3],[6],[8],[2]
右上角角标为将该层排好序时得到的逆序对数量叶子层第 0 0 0 层均为 0 0 0 就不做标记了
那么总的逆序对数就是所有层角标相加之和 7 2 2 0 1 0 1 13 722010113 722010113 对。
我们考虑将区间长度为 2 1 2^{1} 21 的段全翻转看看会造成什么影响。 3 : [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ] 7 3:[1,2,3,4,5,6,7,8]^{7} 3:[1,2,3,4,5,6,7,8]7 2 : [ 1 , 4 , 5 , 7 ] 2 , [ 2 , 3 , 6 , 8 ] 2 2:[1,4,5,7]^{2},[2,3,6,8]^{2} 2:[1,4,5,7]2,[2,3,6,8]2 1 ′ : [ 4 , 5 ] 1 , [ 1 , 7 ] 0 , [ 3 , 6 ] 1 , [ 2 , 8 ] 0 1:[4,5]^{1},[1,7]^{0},[3,6]^{1},[2,8]^{0} 1′:[4,5]1,[1,7]0,[3,6]1,[2,8]0 0 ′ : [ 5 ] , [ 4 ] , [ 1 ] , [ 7 ] , [ 6 ] , [ 3 ] , [ 2 ] , [ 8 ] 0:[5],[4],[1],[7],[6],[3],[2],[8] 0′:[5],[4],[1],[7],[6],[3],[2],[8]
那么总的逆序对数就是 7 2 2 1 0 1 0 13 722101013 722101013 对。
可以发现我们只有在第 1 → 0 1 \rightarrow 0 1→0 层往下的所有层逆序对被改变了即顺序对和逆序对交换了而其他层 n → 2 n \rightarrow 2 n→2 层则无变化。
因为归并到第 0 → i 0 \rightarrow i 0→i 层前其下的所有层是在做 边排序边计算 的过程因此无论其下层的顺序是怎么样的最终数组 排序 到到第 i i i 层时的状态都是唯一确定的不会影响到上一层。
比如我们修改前的第 1 1 1 层和我们原数组的第 1 1 1 层状态是相同的只有逆序对和顺序对的角标被改变了。
同理无论按何种顺序如何翻转第 2 q 2^{q} 2q 层其只会影响第 0 → q 0 \rightarrow q 0→q 的逆序对状态而不会影响第 q 1 → n q1 \rightarrow n q1→n 层逆序对的状态。
因此我们先对原数组做一次归并排序同时记录每一层的逆序对状态和顺序对状态。
对每次的修改对 1 → q 1 \rightarrow q 1→q 层直接交换顺序对和逆序对的值第 0 0 0 层全是 0 0 0 可以不管其余不变或者用 2 n − q ⋅ 2 q ⋅ ( 2 q − 1 ) 2 − 2^{n-q} \cdot \frac{2^{q} \cdot (2^{q}-1)}{2}- 2n−q⋅22q⋅(2q−1)−当前层逆序对之和不过有个 2 2 2 的次幂比较麻烦。
交换完后统计所有层的逆序对之和就是我们的答案了。
时间复杂度 O ( n log n q log n ) O(n \log nq \log n) O(nlognqlogn)
AC代码
#include bits/stdc.h
using namespace std;using PII pairint, int;
using i64 long long;void solve() {int n;cin n;vectorint a((1 n) 1);for (int i 1; i (1 n); i) {cin a[i];}vector cnt(n 1, vectori64(2));vectorint 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;
}
