Description
给一个长度为 $2^n$ 的数组 $a$，现在需要处理 $q$ 个询问，每个询问是以下 4 种类型之一：
- $Replace(x, k)$ 把 $a_x$ 修改为 $k$；
- $Reverse(k)$ 对于每一个 $i(ige 1)$，把区间 $[(i-1)cdot 2^k+1, icdot 2^k]$ 的元素翻转；
- $Swap(k)$ 对于每一个 $i(ige 1)$，交换区间 $[(2i-2)cdot2^k+1,(2i-1)cdot2^k]$ 和 $[(2i-1)cdot2^k+1,2icdot2^k]$ 的所有元素；
- $Sum(l,r)$ 输出区间 $[l,r]$ 中所有元素的和。
$n le 18$，$q le 10^5$
Background
个人认为挺巧妙的一道题，结果在神仙眼里就是：
（语言经过删节）
Solution
操作写的不是人话，翻译一下四个操作：
1. $operatorname{large{R}small{PLACE}}
ormalsize{(x, k)}$，单点修改 $a_x gets k$；
2. $operatorname{large{R}small{EVERSE}}
ormalsize{(k)}$，从左到右划分为若干个长度为 $2^k$ 的区间，将每个区间翻转；
3. $operatorname{large{S}small{WAP}}
ormalsize{(k)}$，从左到右划分为若干个长度为 $2^k$ 的区间，相邻两个区间交换位置；
4. $operatorname{large{S}small{UM}}
ormalsize{(l, r)}$，求 $sumlimits_{i=l}^r a_i$。
我会做 1 和 4 ！
考虑巧妙利用线段树，因为保证序列的长度为 $2^n$，所以，线段树的形状为：共 $n+1$ 层，令叶子结点为第 $0$ 层，根节点为第 $n$ 层，则第 $k$ 层的每个结点，维护的都是长度为 $2^k$ 的区间。
观察操作 2 和 3，我们发现，线段树第 $k$ 层的所有结点，恰好就是我们所想要修改的区间！
定义一个标记 $ ext{rev}_{dep}$，如果为 $1$ 表示第 $dep$ 层的左右结点的左右儿子分别互换，为 $0$ 则不变。
先来看操作 3，如果我们将 $ ext{rev}_{k+1}$ 改变，是不是，恰好相邻两个长度为 $2^k$ 的区间都互换了呢？
下图展示 $n = 3$，$operatorname{large{S}small{WAP}} ormalsize{(1)}$：
再看操作 4，不难发现，它等价于改变所有的 $ ext{rev}_0 sim ext{rev}_k$。这很好理解，$ ext{rev}_{k}$ 改变后，相当于是每个长度为 $2^k$ 的区间内部，前 $2^{k-1}$ 和后 $2^{k-1}$ 个调换了位置，但这两部分内部分别有序，所以要继续调换下去。
在加入了 $ ext{rev}$ 数组后，线段树也不难实现，如果当前处在 $ ext{rev}_{dep}=1$ 的一层，就把右儿子当作左儿子，左儿子当作右儿子好了。
时间复杂度 $mathcal O(qn)$。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 20, S = 1 << N;
int n, q;
bool rev[N];
struct segment_tree
{
int o[S << 2];
void build(int l, int r, int rt)
{
if(l == r) { scanf("%lld", &o[rt]); return; }
int mid = l + r >> 1;
build(l, mid, rt << 1); build(mid + 1, r, rt << 1 | 1);
o[rt] = o[rt << 1] + o[rt << 1 | 1];
}
void modify(int l, int r, int rt, int dep, int p, int v)
{
if(l == r) { o[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);
o[rt] = o[rt << 1] + o[rt << 1 | 1];
}
int query(int l, int r, int rt, int dep, int ql, int qr)
{
if(ql <= l && r <= qr) return o[rt];
int mid = l + r >> 1, 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;
}
} sgt;
#define Replace(x, k) sgt.modify(1, 1 << n, 1, n, x, k)
#define Sum(l, r) sgt.query(1, 1 << n, 1, n, l, r)
#define Swap(k) rev[k + 1] ^= 1
inline void Reverse(int k) { for(int i = 0; i <= k; i++) rev[i] ^= 1; }
signed main()
{
scanf("%lld %lld", &n, &q);
sgt.build(1, 1 << n, 1);
while(q--)
{
int opt, x, y;
scanf("%lld", &opt);
switch(opt)
{
case 1:
scanf("%lld %lld", &x, &y); Replace(x, y); break;
case 2:
scanf("%lld", &x); Reverse(x); break;
case 3:
scanf("%lld", &x); Swap(x); break;
case 4:
scanf("%lld %lld", &x, &y); printf("%lld
", Sum(x, y)); break;
}
}
return 0;
}