题目描述

难度分:$2400$

输入$n(0 \leq n \leq 18)$，$q(1 \leq q \leq 10^5)$和长为$2^n$的数组$a(0 \leq a[i] \leq 10^9)$。数组下标从$1$开始。

然后输入$q$个询问：

• 1 i v：把$a[i]$改成$v(0 \leq v \leq 10^9)$。
• 2 k：把数组从左到右划分为若干长为$2^k$的区间，将每个区间$reverse$。$(0 \leq k \leq n)$
• 3 k：把数组从左到右划分为若干长为 $2^k$的区间，交换第一个和第二个区间，第三个和第四个区间，依此类推。$(0 \leq k \leq n-1)$
• 4 L R：输出$a[L] + a[L+1] + … + a[R]$。

输入样例$1$

2 3
7 4 9 9
1 2 8
3 1
4 2 4

输出样例$1$

24

输入样例$2$

3 8
7 0 8 8 7 1 5 2
4 3 7
2 1
3 2
4 1 6
2 3
1 5 16
4 8 8
3 0

输出样例$2$

29
22
1

算法

线段树

最近灵佬选了好几个题目都直击某算法的本质，完全不会做，学了之后对题目的考点算法又有了进一步的理解。

先考虑如何翻转一个数组？对于如下数组：
12345678

首先，交换相邻数字：
21436587

然后，两个数一组，交换：
43218765

最后，四个数一组，交换：
87654321

所以操作$2$可以用操作$3$表达：
调用2 k，相当于依次调用3 0，3 1，3 2，……，3 k-1。

对于每个k，用一个$O(n)$规模的数组$rev$记录3 k的调用次数。而偶数次相当于不变，因此只需要调用次数的奇偶性。

现在剩下操作$1$、$4$，单点修改+区间查询，用线段树解决。注意操作$2$和操作$3$的$k$ 越大，每个区间越长，所以$k$越大越靠近线段树的根节点，可以对线段树节点的层编号为$0$~$n$，$0$是叶子节点，$n$是根节点。当执行3 k时，就相当于要把线段树第$k$层的所有节点代表的区间做翻转。

如果线段树第$k$层执行了奇数次操作$3$，那么原来要递归左子树的逻辑，就要变成递归右子树；原来要递归右子树的逻辑，就要变成递归左子树。

复杂度分析

时间复杂度

构建线段树的时间复杂度为$O(n2^n)$。而对于每个询问，除了操作$3$，其余操作都要进行线段树树高级别的操作，即单次操作的时间复杂度为$O(n)$，$q$个询问的整体时间复杂度为$O(qn)$。因此，整个算法的时间复杂度为$O(n2^n+qn)$。

空间复杂度

$rev$数组的空间复杂度为$O(n)$，相比线段树的消耗可以忽略不计。因此整个算法的额外空间复杂度就是线段树的空间消耗，为$O(2^n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int M = 20, N = (1<<18) + 1;
int n, q, a[N];
bool rev[M];

class SegmentTree {
public:
    LL seg[N<<2];

    explicit SegmentTree() {}

    void build(int u, int l, int r) {
        if(l == r) {
            seg[u] = a[r];
        }else {
            int mid = l + r >> 1;
            build(u<<1, l, mid);
            build(u<<1|1, mid + 1, r);
            seg[u] = seg[u<<1] + seg[u<<1|1];
        }
    }

    void modify(int pos, LL val) {
        modify(1, 1<<n, 1, n, pos, val);
    }

    LL query(int l, int r) {
        return query(1, 1<<n, 1, n, l, r);
    }

private:
    void modify(int l, int r, int rt, int dep, int p, int v) {
        if(l == r) {
            seg[rt] = v;
            return;
        }
        int mid = l + r >> 1;
        if(p <= mid) {
            modify(l, mid, rt<<1|rev[dep], dep - 1, p, v);
        }else {
            modify(mid + 1, r, rt<<1|rev[dep]^1, dep - 1, p, v);
        }
        seg[rt] = seg[rt<<1] + seg[rt<<1|1];
    }

    LL query(int l, int r, int rt, int dep, int ql, int qr) {
        if(ql <= l && r <= qr) return seg[rt];
        int mid = l + r >> 1;
        LL res = 0;
        if(ql <= mid) {
            res += query(l, mid, rt<<1|rev[dep], dep - 1, ql, qr);
        }
        if(qr > mid) {
            res += query(mid + 1, r, rt<<1|rev[dep]^1, dep - 1, ql, qr);
        }
        return res;
    }
};

int main() {
    scanf("%d %d", &n, &q);
    for(int i = 1; i <= (1<<n); i++) {
        scanf("%d", &a[i]);
    }
    SegmentTree seg;
    seg.build(1, 1, 1<<n);
    while(q--) {
        int opt;
        scanf("%d", &opt);
        if(opt == 1) {
            int i, v;
            scanf("%d%d", &i, &v);
            seg.modify(i, v);
        }else if(opt == 2) {
            int k;
            scanf("%d", &k);
            for(int i = 0; i <= k; i++) {
                rev[i] ^= 1;
            }
        }else if(opt == 3) {
            int k;
            scanf("%d", &k);
            rev[k + 1] ^= 1;
        }else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", seg.query(l, r));
        }
    }
    return 0;
}