压缩

题目

时间限制：1000 ms
空间限制：64 MB

题目描述

令

n = 2^{63}

。

如题，已知一个长度为

n

的数列

\{a_i\}

（

0 \leq i < n

），初始时

a

序列满足

a_i = 0

。你需要进行下面两种操作：

将某一个数改为 $k$ 。
求出某区间每一个数的异或和，并将结果写入 $L$ 。

L

初始为

0

。本题强制在线，具体看输入格式。

输入格式

第一行包含一个整数

m

，表示操作的总个数。

接下来

m

行每行包含

3

个整数，表示一个操作。将每个数异或

L

后，内容具体如下：

1 i k：将 $a_i$ 改为 $k$ 。
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};
  }
}

动态开点线段树优化

文章操作

压缩