位变换线段树
stripe_python · · 算法·理论
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[题解]
我们建立
考虑在线段树节点上打两个标记
分析三种位运算对 01-Trie 的影响:
- XOR:交换左右子树。
- AND / OR:将某侧子树合并到另一侧。
由于左右子树合并会使得总节点数减少,且单点修改只会新增O(n) 个节点,故暴力进行线段树合并可以均摊为O(2^n+qn) ,复杂度正确。
考虑
- 若
0 \to 0 且1 \to 0 ,将右子树合并到左子树,断开右子树。 - 若
0 \to 1 且1 \to 1 ,将左子树合并到右子树,断开左子树。 - 若
0 \to 1 且1 \to 0 ,交换左右儿子即可。
变换完成后,将残余标记下传到子树中,并清空
单点修改和区间求和是平凡的。这样问题在
:::::
:::::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[题解]
将修改标记永久化,对全局打标记
区间颜色段是半群信息,记录端点处的颜色值可以
对原序列建线段树,预处理所有节点偏移
断言
具体地,我们对
复杂度
:::::