动态开点线段树优化
__cplusplus
·
·
个人记录
压缩
:::info[题目]
时间限制：1000 ms
空间限制：64 MB
题目描述
令 n = 2^{63}。
如题，已知一个长度为 n 的数列 \{a_i\}（0 \leq i < n），初始时 a 序列满足 a_i = 0。你需要进行下面两种操作：
- 将某一个数改为 k。
- 求出某区间每一个数的异或和，并将结果写入 L。
## 输入格式
第一行包含一个整数 $m$，表示操作的总个数。
接下来 $m$ 行每行包含 $3$ 个整数，表示一个操作。将每个数异或 $L$ 后，内容具体如下：
1. `1 i k`：将 $a_i$ 改为 $k$。
2. `2 l r`：输出 $a_l \sim a_r$ 内每个数的异或和，并将结果写入 $L$。
比如，输入了 $a,b,c$，则其实际值为$a\oplus L,b\oplus L,c\oplus L$。
## 输出格式
输出包含若干行整数，即为所有操作 2 的结果。
## 说明/提示
保证 $1 \le m\le {10}^6$，$0 \le l \le r <n$，$0 \le k < n$。]
:::
定义高度为与叶子的距离，叶子的高度为 0.
对于每个节点，维护其左子节点（含）下最高的节点；右同理.
```cpp
typedef std::size_t S;
struct No {
S L, R, x;
No *c[2];
};
#define lc (p->c[0])
#define rc (p->c[1])
```
宏定义一会有用。
### 修改
递归修改 $a_i \leftarrow k$。当递归到一个节点 $p$ 时：
- 判断是否可以直接修改；
- 判断在哪侧 $j$；
- 如果 $j$ 不存在，创建；
- 否则如果 $i$ 在 $j$ 内，递归；
- 否则创建其 LCA 并将两点放在其两侧（一定在两侧）。
```cpp
void pushup(No* p) {
p->x = lc->x + rc->x;
}
void update(No* p, S i, S k) {
if (p->L == p->R - 1) {
p->x = k;
return;
}
S L = p->L, r = p->R;
S mid = L + ((R - L) >> 1);
No*& s = p->c[i >= mid];
if (s) {
if (s->L <= i && i < s->R)
update(s, i, k);
else {
S t = SIZE_MAX >> __builtin_clzll(s->L ^ i), u = ~t & i;
No* v = s;
if (i >= v->R)
s = new No {u, u + t + 1, 0, {v, new No{i, i, k}}};
else
s = new No {u, u + t + 1, 0, {new No{i, i, k}, v}};
pushup(s);
}
} else {
s = new No {i, i, k};
}
}
```