Xor-Forces

简称释义：MX - 梦熊信息学联盟，Cfz - Coffee_zzz。

场上算错了复杂度，自己把自己的可持久化线段树的正解给叉掉了。

对于复杂度不是很好算的题目，要认真算。像这样也就一百来行的代码，思路又已经证明是正确的，可以把它实现出来，再拿极限数据去测。

问题重述

原题面已足够清晰，抄录如下：

给定一个长度为 $n=2^k$ 的数组 $a$，下标从 $0$ 开始，维护 $m$ 次操作：

1. 操作一：给定 $x$，设数列 $a^{\prime }$ 满足 $a_i^{\prime }=a_{i\oplus x}$，将 $a$ 修改为 $a^{\prime }$。其中 $\oplus$ 表示按位异或运算。
2. 操作二：给定 $l,r$，查询 $a$ 的下标在 $l,r$ 之间的子数组有多少颜色段。不保证 $\mathbf{l}\le \mathbf{r}$，若 $\mathbf{l}>\mathbf{r}$，请自行交换 $\mathbf{l},\mathbf{r}$。

其中，一个极长的所有数都相等的子数组称为一个颜色段。

对于 $T=1$ 的测试点，要求强制在线。

---

对于所有测试数据，T∈{0,1}T \in \{ 0, 1 \}T∈{0,1}，$0\le k\le 18$，$n=2^k$，$1\le m\le 2\times 10^5$，$1\le a_i\le n$，op∈{1,2}\mathit{op} \in \{ 1, 2 \}op∈{1,2}，$0\le x,l,r<n$。

• Subtask 1（15 pts）：$T=1$，$k\le 10$，$m\le 10^3$。
• Subtask 2（15 pts）：$T=1$，不存在操作一。
• Subtask 3（20 pts）：$T=1$，对于所有操作二，要么 $l=0,r=n-1$，要么 $l=n-1,r=0$。
• Subtask 4（20 pts）：$T=0$。
• Subtask 5（30 pts）：$T=1$。

部分分

Subtask 1，暴力计算即可。
Subtask 2，可以使用线段树进行维护。

当然其实显然也可以 $O(n)$，不过 $O(n)$ 做法对正解的启发性似乎不大。

线段树节点需要维护的信息以及合并方式如下：

struct Data {
    int l, r, val; // 最左端的值，最右端的值，不同颜色段的数目
    Data(int a=0, int b=0, int c=0): l(a), r(b), val(c) {}
    Data operator+(const Data &x) { // 合并两个线段的值
        return {l, x.r, val + x.val - (r==x.l)};
    }
};

Subtask 3 & 4 可以参考官方题解。

正解：可持久化线段树

考虑可持久化，对每一个 $x$（$0\le x<2^k$）建立一个主席树的根节点，分别初始下标 xor $x$ 得到的新数组的信息。

尝试：对所有的初始下标 xor 同一个数 $x$。当 $k=4$，$x=10=(1010{)}_2$ 时：

原下标：	0		1		2		3		4		5		6		7
二进制：	0000	0001	0010	0011	0100	0101	0110	0111
新下标：	10		11		8		9		14		15		12		13
二进制：	1010	1011	1000	1001	1110	1111	1100	1101

原下标：	8		9		10		11		12		13		14		15
二进制：	1000	1001	1010	1011	1100	1101	1110	1111
新下标：	2		3		0		1		6		7		4		5
二进制：	0010	0011	0000	0001	0110	0111	0100	0101

如果当前线段左端点为$l$，右端点为 $r$，$mid=(l+r)/2$，$len=r-l+1$（显然这是一棵满二叉树，$len$ 为 $2$ 的自然数次幂），观察发现：

• 若 $x\mathrm{and}(len/2)=0$，则左子树对应原来下标的 $[l,mid]$，右子树对应原来下标的 $[mid+1,r]$。
• 若 $x\mathrm{and}(len/2)=1$，则左子树对应原来下标的 $[mid+1,r]$，右子树对应原来下标的 $[l,mid]$，恰好与前一种情况相反。

因为位运算中，每一位之间独立，所以如果二进制下 $x_1$ 和 $x_2$ 的后 $k$ 位相同，那么相应会有 $k$ 层 非叶子节点的子树形态相同。那么形态相同的这些部分就可以发挥可持久化的作用。

先建立 $x=0$，即原始数组的线段树。

$\forall x>0$，找到 $x$ 二进制下非 $0$ 的最高位，将这一位设为 $0$ 之后，就能得到我们需要从这里转移的蓝本。

例如 $x=(01011{)}_2$，它应从 $x^{\prime }=(00011{)}_2$ 转移，因为两者的后 $3$ 位都是 $011$，对应的子树形态相同，应当被重复利用。只有在从后往前第 $4$ 位开始，才需要发生改变。

转移的时候从原来的根节点向下递归，第一次 $x\mathrm{and}(len/2)=1$ 时（此时就是 $x$ 的最高位），在此建立新节点，其左子树是原节点的右子树，右子树时原节点的左子树，然后合并左右子信息，返回当前的新节点。

建立可持久化线段树之后，查询就变得十分简单了。

复杂度分析

查询 $O(m\log n)$ 显然。

建立可持久化线段树的时候，如果线段长度为 $2^x$，那么有 $2^k/2^x=2^{k-x}$ 个这么长的线段。同时经过 xor 操作，区间 $[l,l+2^x-1]$ 会有 $2^x$ 种不同可能的情况，那么当前层一共有 $2^{k-x}\times 2^x=2^k$ 个维护不同信息的线段。包括叶子节点，一共有 $(k+1)$ 层，所以建立主席树的过程，时间和空间复杂度均为 $O(n\log n)$，总复杂度 $O((n+m)\log n)$，可以通过此题。

代码

// persistent segment tree
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
const int MAXN = (1<<18)+5; // 一定要加括号

int n, m, k, a[MAXN];

namespace SGT { // 数据结构封装
	struct Data {
	    int l, r, val;
	    Data(int a=0, int b=0, int c=0): l(a), r(b), val(c) {}
	    Data operator+(const Data &x) {
	        return {l, x.r, val + x.val - (r==x.l)};
	    }
	} s[MAXN<<5];
    int lc[MAXN<<5], rc[MAXN<<5], tot;
    int root[MAXN];

    int newNode(Data x) {
        s[++tot] = x;
        lc[tot] = rc[tot] = 0;
        return tot;
    }

    int build(int a[], int l, int r) {
        if (l == r) {
            int cur = newNode({a[l], a[r], 1});
            return cur;
        }
        int mid = (l + r) >> 1;
        int cur = newNode(Data());
        lc[cur] = build(a, l, mid);
        rc[cur] = build(a, mid+1, r);
        s[cur] = s[lc[cur]] + s[rc[cur]]; // 不要丢 pushup!
        return cur;
    }

    int update(int last, int l, int r, int x) {
        int mid = (l + r) >> 1, len = r - l + 1;
        int cur = newNode(Data());
        if (x & (len >> 1)) { // 最高位的 1，在这里可持久化，利用算好了的，同时递归结束。
            lc[cur] = rc[last], rc[cur] = lc[last];
        } else {
            lc[cur] = update(lc[last], l, mid, x);
            rc[cur] = update(rc[last], mid+1, r, x);
        }
        s[cur] = s[lc[cur]] + s[rc[cur]]; // 不要丢 pushup!
        return cur;
    }

    Data query(int cur, int l, int r, int L, int R) {
        if (L <= l && R >= r) return s[cur];
        int mid = (l + r) >> 1;
        if (R <= mid) {
            return query(lc[cur], l, mid, L, R);
        } else if (L > mid) {
            return query(rc[cur], mid+1, r, L, R);
        } else {
            return query(lc[cur], l, mid, L, R) + query(rc[cur], mid+1, r, L, R);
        }
    }

    void init(int a[]) {
        tot = 0;
        root[0] = build(a, 0, n-1);
        for (int i = 1; i < n; ++i) {
            int k = log(i) / log(2); // 强制转换的时候向下取整，刚好符合要求
            root[i] = update(root[i^(1<<k)], 0, n-1, i);
        }
    }

    Data query(int L, int R, int x) { return query(root[x], 0, n-1, L, R); }
}

int main() {
    int T;
    scanf("%d%d%d", &T, &k, &m);
    n = 1<<k;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    SGT::init(a);
    int v = 0, lst = 0;
    while (m--) {
        int op;
        scanf("%d", &op);
        if (op == 1) {
            int x;
            scanf("%d", &x);
            x ^= T * lst;
            v ^= x; // 利用了 xor 的结合律
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            l ^= T * lst, r ^= T * lst;
            if (l > r) swap(l, r);
            lst = SGT::query(l, r, v).val;
            printf("%d\n", lst);
        }
    }
    return 0;
}

问： 为什么 x&(len>>1)=1 就要互换线段树左右节点？
回答：
$x\mathrm{and}(len/2)=1$ 意思是 $x$ 的二进制表示下当前位是 $1$，那么原序列这一位是 $1$ 的，它的下标在新序列里面这一位就会变成 $0$；而原序列这一位是 $0$ 的就会变到 $1$ 去，那么这就是一个交换。

补充：2024.9.29 更新了代码，远古码风的 class 已经不知道死了多少回了，建议后人不要用 class 封装，防止 MLE/TLE/RE，我们机房不止一个人因为不合适的封装爆过零。