1401F - Reverse and Swap（线段树之左右儿子交换）

看题面很显然的一道数据结构题，但是对于2和3操作我想了一会没有啥思路，网上看了大佬的博客，发现只需要维护线段树上的每个结点的左右儿子是否交换就行了，在纸上模拟了几遍就想通了。唉，这就是思维的差距吧...

AC代码

// Author: Feng
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pii pair<int,int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pb push_back
#define X first
#define Y second
inline ll gcd(ll a, ll b) { while (b != 0) { ll c = a % b; a = b; b = c; }return a < 0 ? -a : a; }
inline ll lowbit(ll x) { return x & (-x); }
int head[1000010], Edge_Num;
struct Edge { int to, next; ll w; }e[2000010];
inline void ade(int x, int y, ll w) { e[++Edge_Num] = { y,head[x],w }; head[x] = Edge_Num; }
inline void G_init(int n) { memset(head, 0, sizeof(int) * (n + 100)); Edge_Num = 0; }
int dir[8][2] = { {-1,0},{0,-1},{1,0},{0,1},{-1,-1},{-1,1},{1,-1},{1,1} };
const long double PI = 3.14159265358979323846;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
inline ll rd() {
    ll x = 0; bool f = 1; char ch = getchar();
    while (ch<'0' || ch>'9') { if (ch == '-')f = 0; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    return f ? x : -x;
}
const double eps = 1e-8;
const ll mod = 1e9 + 7;
const int M = 5e6 + 10;
const int N = (1 << 18) + 10;
struct Segment_Tree {
    int l, r;
    ll sum;
}t[N << 2];
ll a[N];
void pushup(int p) {
    t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
}
void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) {
        t[p].sum = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushup(p);
}
int flip[20];
void update(int p, int x, ll v, int d) {
    if (t[p].l == x && x == t[p].r) {
        t[p].sum = v;
        return;
    }
    int mid = (t[p].l + t[p].r) >> 1;
    int det = (t[p].r - t[p].l + 1) >> 1;
    if (flip[d])x += (x > mid ? -det : det);
    if (x <= mid)update(p << 1, x, v, d + 1);
    else update(p << 1 | 1, x, v, d + 1);
    pushup(p);
}
ll query(int p, int l, int r, int d) {
    if (t[p].l == l && t[p].r == r)return t[p].sum;
    int mid = (t[p].l + t[p].r) >> 1;
    int det = (t[p].r - t[p].l + 1) >> 1;
    if (r <= mid) {
        if (flip[d])return query(p << 1 | 1, l + det, r + det, d + 1);
        return query(p << 1, l, r, d + 1);
    }
    else if (l > mid) {
        if (flip[d])return query(p << 1, l - det, r - det, d + 1);
        return query(p << 1 | 1, l, r, d + 1);
    }
    else {
        if (flip[d])return query(p << 1 | 1, l + det, mid + det, d + 1) + query(p << 1, mid + 1 - det, r - det, d + 1);
        else return query(p << 1, l, mid, d + 1) + query(p << 1 | 1, mid + 1, r, d + 1);
    }
}
void solve() {
    int n = rd(), q = rd();
    for (int i = 1; i <= 1 << n; i++)a[i] = rd();
    build(1, 1, 1 << n);
    while (q--) {
        int op = rd();
        if (op == 1) {
            int x = rd();
            ll k = rd();
            update(1, x, k, 0);
        }
        else if (op == 2) {
            int k = rd();
            for (int i = n - k; i <= n; i++)flip[i] ^= 1;
        }
        else if (op == 3) {
            int k = rd();
            flip[n - k - 1] ^= 1;
        }
        else {
            int l = rd(), r = rd();
            printf("%lld\n", query(1, l, r, 0));
        }
    }
}
int main() {
    int _T = 1;
    while (_T--)solve();
}