位变换线段树

· · 算法·理论

QOJ12325 Data Structure Problem

给定长为 2^n 的序列 a_0 \sim a_{2^n-1}。维护 q 次操作

  • 给定 x,\delta,令 a_x \gets a_x+\delta。
  • 给定 l,r,求 \sum \limits_{i=l}^r a_i。
  • 给定 k,设 b_j=\sum \limits_{i \text{ and } k=j} a_i,令 a \gets b。
  • 给定 k,设 b_j=\sum \limits_{i \text{ or } k=j} a_i,令 a \gets b。
  • 给定 k,设 b_j=\sum \limits_{i \text{ xor } k=j} a_i,令 a \gets b。

:::::success[题解]

我们建立 a_i 的线段树。注意到此时的线段树等价于高位向低位的 01-Trie。

考虑在线段树节点上打两个标记 a_0,a_1,表示下标二进制位 0,1 变换后的去向为 a_0,a_1,标记复合是容易的。每个二进制位独立,故可以压位记录标记值。

分析三种位运算对 01-Trie 的影响:

考虑 u 的子节点 v,设 v 代表第 d 位。在做 u \to v 的 pushdown 时,我们在 u 处考察 f 对 d 的变换,进行讨论:

变换完成后,将残余标记下传到子树中,并清空 u 的 tag。

单点修改和区间求和是平凡的。这样问题在 O(2^n+qn) 内解决。

:::::

:::::info[代码]

const int N = 5e5 + 5;
int n, m, q, tot, lc[40*N], rc[40*N], t0[40*N], t1[40*N];
i64 sum[40*N];
#define ls lc[rt]
#define rs rc[rt]
void pushup(int rt) {sum[rt] = sum[ls] + sum[rs];}
void apply(int rt, int a0, int a1) {
    if (!rt) return;
    int n0 = (~t0[rt] & a0) | (t0[rt] & a1);
    int n1 = (~t1[rt] & a0) | (t1[rt] & a1);
    t0[rt] = n0 & m, t1[rt] = n1 & m;
} 
void pushdown(int rt, int d);
int merge(int u, int v, int d) {
    if (!u || !v) return u ? u : v;
    if (d < 0) return sum[u] += sum[v], u;
    pushdown(u, d), pushdown(v, d);
    lc[u] = merge(lc[u], lc[v], d - 1);
    rc[u] = merge(rc[u], rc[v], d - 1);
    return pushup(u), u;
}
void pushdown(int rt, int d) {
    if (t0[rt] == 0 && t1[rt] == m) return;
    int d0 = t0[rt] >> d & 1, d1 = t1[rt] >> d & 1;
    if (d0 == 0 && d1 == 0) ls = merge(ls, rs, d - 1), rs = 0;
    if (d0 == 1 && d1 == 1) rs = merge(rs, ls, d - 1), ls = 0;
    if (d0 == 1 && d1 == 0) swap(ls, rs);
    apply(ls, t0[rt], t1[rt]), apply(rs, t0[rt], t1[rt]);
    t0[rt] = 0, t1[rt] = m;
} 
int create() {
    int u = ++tot;
    return t0[u] = 0, t1[u] = m, u;
}
void build(int l, int r, int& rt, int d) {
    rt = create();
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(l, mid, ls, d - 1), build(mid + 1, r, rs, d - 1);
    pushup(rt);
}
void update(int x, i64 c, int l, int r, int& rt, int d) {
    if (!rt) rt = create();
    if (l == r) return sum[rt] += c, void();
    int mid = (l + r) >> 1; pushdown(rt, d);
    if (x <= mid) update(x, c, l, mid, ls, d - 1);
    else update(x, c, mid + 1, r, rs, d - 1);
    pushup(rt);
}
i64 ask(int tl, int tr, int l, int r, int rt, int d) {
    if (!rt) return 0;
    if (tl <= l && r <= tr) return sum[rt];
    i64 mid = (l + r) >> 1, res = 0; pushdown(rt, d);
    if (tl <= mid) res += ask(tl, tr, l, mid, ls, d - 1);
    if (tr > mid) res += ask(tl, tr, mid + 1, r, rs, d - 1);
    return res;
}

void _main() {
    cin >> n >> q; m = (1 << n) - 1;
    int rt = 0; build(0, m, rt, n-1);
    for (int i = 0, x; i <= m; i++) cin >> x, update(i, x, 0, m, rt, n-1);
    for (int i, x, l, r; q--; ) {
        string op; cin >> op;
        if (op == "add") cin >> i >> x, update(i, x, 0, m, rt, n-1);
        if (op == "sum") cin >> l >> r, cout << ask(l, r, 0, m, rt, n-1) << '\n';
        if (op == "and") cin >> x, apply(rt, 0, x);
        if (op == "or") cin >> x, apply(rt, x, m);
        if (op == "xor") cin >> x, apply(rt, x, x ^ m);
    }
}

:::::

P10856 【MX-X2-T5】「Cfz Round 4」Xor-Forces

给定长为 n=2^k 的数组 a_i,下标从 0 开始,支持 q 次操作:

  • 给定 x,令 a_i \gets a_{i \oplus x}。
  • 给定 l,r,查询区间 [l,r] 的颜色段数。

强制在线。

:::::success[题解]

将修改标记永久化,对全局打标记 x 表示下标偏移量,只要查询 a'_i=a_{i \oplus x} 的区间颜色段数。

区间颜色段是半群信息,记录端点处的颜色值可以 O(1) 合并,注意信息不具有交换律。

对原序列建线段树,预处理所有节点偏移 0 \sim \text{len}-1 的答案。将线段树视作 01-Trie 结构,合并时简单讨论即可。

断言 a_{l \oplus x}, a_{(l+1) \oplus x},\cdots a_{r \oplus x} 可以分解为静态线段树上 O(\log n) 个带偏移区间。

具体地,我们对 [l,r] 进行递归分解,若 x 高位为 0 则直接递归,若 x 高位为 1 则需要交换左右子树。可以算出对应区间后递归,注意半群复合顺序是反过来的。静态线段树可以视作高位向低位的 01-Trie 结构。

复杂度 O(n \log n+q \log n)。代码。

:::::