题解 Xor-Forces

本题解为 Xor-Forces 的官方题解。

解法一：我会暴力（子任务一，期望得分 $15$ 分）

按题意模拟即可。

时间复杂度 $\mathcal O(nm)$，空间复杂度 $\mathcal O(n)$。

解法二：我会线段树（子任务二，期望得分 $15$ 分）

没有修改操作，就是查询区间颜色段数量，线段树每个节点维护左端点颜色、右端点颜色、颜色段数量即可。

时间复杂度 $\mathcal O(n+m\log n)$，空间复杂度 $\mathcal O(n)$。

解法三：我会预处理（子任务三，期望得分 $20$ 分）

我们发现不管如何进行操作，数列都只有 $n$ 种，分别是 $b_x:b_{x,i}=a_{i\oplus x}$（$0\le x < n$）。我们记 $b_x$ 的颜色段个数为 $ans_x$，问题转化为求出所有 $ans_x$。

直接做还是 $\mathcal O(n^2)$ 的，但是我们可以递推。我们可以暴力求出 $ans_0$，假设我们已经求出了 $ans_{0\cdots p-1}$，接下来我们要求 $ans_p$。

我们设 $t$ 为 $p$ 的二进制最高位，尝试由 $ans_{p\oplus t}$ 推出 $ans_p$。考虑 $b_{p\oplus t}\to b_p$ 的变化，其实就是按照下标比 $t$ 高的位的异同分为 $\frac{n}{2t}$ 组，则这次操作就是将每组内下标的 $t$ 的这一位为 $1$ 的元素放在为 $0$ 的元素前面，可能影响 $ans_p$ 的只有每组正中间的断点以及两组中间的连接处，共 $\frac{n}{t}$ 个。

我们令 $ans_p\gets ans_{p\oplus t}$，然后枚举这 $\frac{n}{t}$ 个可能影响答案的位置，计算答案的变化量即可。

其实是个类似于格雷码的 trick。

时间复杂度 $\mathcal O(n\log n+m)$，空间复杂度 $\mathcal O(n)$。

解法四：我会离线（子任务四，期望得分 $20$ 分）

这次是区间询问，无法像「子任务三」一样预处理，但是可以离线，因此考虑按照下标异或的 $x$ 将所有询问分类。

分类后，对于每一类询问，是不带修改的，这部分和「子任务二」是一样的，我们可以简单地线段树来做。问题转化成了如何快速地执行下标异或操作。

由于 $n=2^k$，线段树其实相当于一棵 01trie。「解法三」告诉我们：在下标 $\oplus$ 一个 $2$ 的幂时，数列的变化相当于是交换了一层线段树节点的左右子树，这个线段树是支持的。

可以继续使用类似于格雷码的维护技巧，使得相邻两个异或的 $x$ 只有一个二进制位不同，使用线段树维护求解即可。

时间复杂度 $\mathcal O(n\log n+m\log n)$，空间复杂度 $\mathcal O(n)$。

解法五：我依然会线段树（正解，期望得分 $100$ 分）

这个解法的难点可能在于发现暴力是正确的（？）。

转化一下操作，也就是：

给定 $l,r,x$，求 $a_{l\oplus x},a_{(l+1)\oplus x},\cdots,a_{r\oplus x}$ 的颜色段数量。

接着考虑如何使用线段树维护它。

在「解法四」中我们说过，这棵线段树相当于一棵 01trie，因此我们知道一个节点代表的下标区间，一定是二进制高位已经确定，低位随便取的状态。于是我们不妨对于每一种取值都维护一个答案。

考虑向上合并两个节点信息的过程，我们记 $\operatorname{lc}(u),\operatorname{rc}(u)$ 为节点 $u$ 的左右儿子。现在希望求节点 $u$ 在下标异或 $x$ 时的答案，怎么求？

• 记 $x$ 去掉最高位的结果为 $x'$。请注意这里是用的 01trie 的理解方式，因此 $x$ 是定长二进制串，包含前导零，与前文意义略有不同。
• 若 $x$ 的最高位为 $0$，则合并 $\operatorname{lc}(u)$ 在 $x'$ 处的答案和 $\operatorname{rc}(u)$ 在 $x'$ 处的答案即可。
• 若 $x$ 的最高位为 $1$，则合并 $\operatorname{rc}(u)$ 在 $x'$ 处的答案和 $\operatorname{lc}(u)$ 在 $x'$ 处的答案即可。

最后是区间查询操作：

• 若查询区间完全包含于节点代表的区间，返回对应 $x$ 的答案即可。
• 若 $x$ 的最高位为 $0$，则没啥特殊的，正常查询即可。
• 若 $x$ 的最高位为 $1$，则查询到这里后需要交换左右子树，我们算出在右子树和左子树对应的查询区间，继续查询即可。

时间复杂度 $\mathcal O(n\log n+m\log n)$，空间复杂度 $\mathcal O(n\log n)$。

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

template<int mod>
inline unsigned int down(unsigned int x) {
	return x >= mod ? x - mod : x;
}

template<int mod>
struct Modint {
	unsigned int x;
	Modint() = default;
	Modint(unsigned int x) : x(x) {}
	friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
	friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
	friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
	friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
	friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
	friend Modint operator/(Modint a, Modint b) {return a * ~b;}
	friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
	friend Modint operator~(Modint a) {return a ^ (mod - 2);}
	friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
	friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
	friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
	friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
	friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
	friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
	friend Modint& operator++(Modint& a) {return a += 1;}
	friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
	friend Modint& operator--(Modint& a) {return a -= 1;}
	friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
	friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
	friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};

const int N = 1 << 18 | 5;

int T, k, n, m, a[N], now, lst;

struct Node {
    int l, r, cnt;
    Node(int a = 0, int b = 0, int c = 0) : l(a), r(b), cnt(c) {}
    friend bool operator==(const Node& u, const Node& v) {
        return u.l == v.l && u.r == v.r && u.cnt == v.cnt;
    }
    friend Node operator+(const Node& u, const Node& v) {
        if(u == Node()) return v;
        if(v == Node()) return u;
        return Node(u.l, v.r, u.cnt + v.cnt - (u.r == v.l));
    }
};
struct SegTree {
    vector<Node> t[N << 2];
    #define lc(u) (u << 1)
    #define rc(u) (u << 1 | 1)
    void build(int* a, int u, int l, int r) {
        int len = r - l + 1;
        t[u].resize(len);
        if(l == r) {
            t[u][0] = Node(a[l], a[r], 1);
            return;
        }
        int mid = (l + r) >> 1;
        build(a, lc(u), l, mid);
        build(a, rc(u), mid + 1, r);
        rep(i, 0, len - 1) {
            if(i < (len >> 1)) t[u][i] = t[lc(u)][i] + t[rc(u)][i];
            else t[u][i] = t[rc(u)][i ^ (len >> 1)] + t[lc(u)][i ^ (len >> 1)];
        }
    }
    Node query(int u, int l, int r, int ql, int qr, int qx, int pos) {
        if(qr < l || r < ql || qr < ql) return Node();
        if(ql <= l && r <= qr) {
            if(l == r) return t[u][0];
            else return t[u][qx & ((1 << (pos + 1)) - 1)];
        }
        int mid = (l + r) >> 1;
        if(!((qx >> pos) & 1)) {
            return query(lc(u), l, mid, ql, qr, qx, pos - 1)
                 + query(rc(u), mid + 1, r, ql, qr, qx, pos - 1);
        }
        else {
            int ql1 = ql, qr1 = min(mid, qr), ql2 = max(mid + 1, ql), qr2 = qr;
            return query(rc(u), mid + 1, r, mid + 1 + ql1 - l, mid + 1 + qr1 - l, qx, pos - 1)
                 + query(lc(u), l, mid, l + ql2 - (mid + 1), l + qr2 - (mid + 1), qx, pos - 1);
        }
    }
}sgt;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> T >> k >> m;
    n = 1 << k;
    rep(i, 0, n - 1) cin >> a[i];
    sgt.build(a, 1, 0, n - 1);
    while(m--) {
        int op;
        cin >> op;
        if(op == 1) {
            int x;
            cin >> x;
            x ^= T * lst;
            now ^= x;
        }
        else {
            int x, y;
            cin >> x >> y;
            x ^= T * lst; y ^= T * lst;
            if(x > y) swap(x, y);
            cout << (lst = sgt.query(1, 0, n - 1, x, y, now, k - 1).cnt) << endl;
        }
    }
    return 0;
}

首先我们发现操作 $1$ 具有结合律，于是我们要解决的就是每次给定一个 $x$，令 $a'_i = a_{i\oplus x}$，查询 $a'$ 下标在 $[l, r]$ 内的子数组的颜色段个数。

有个显然的转化：区间颜色段个数等于区间长度减去相邻同色对数，只需考虑如何计算 $l\lt i\leq r, a_{i\oplus x} = a_{(i - 1)\oplus x}$ 的 $i$ 个数即可。

考虑线段树，当询问跨过区间中点 $m$ 时，可以直接判断 $a_{m \oplus x}$ 和 $a_{(m - 1)\oplus x}$ 这一对是否相等，并递归到两个儿子去计算。

现在我们要解决的就是线段树上某个节点对应的答案，因为每次异或的 $x$ 不同，一个节点对应的区间中的元素顺序会被打乱，每个节点对应的答案也不是唯一的，此时我们显然无法对于每个节点储存单一的答案。

这里给出一个结论：如果一个节点对应的区间长度为 $l$，那么对这个区间有用的 $x$ 只有 $l$ 种！

这是为什么呢？考虑询问的是 $\texttt{0 1 2 3}$ 这一段区间，$x = 5$，此时区间长度 $l$ 为 $4$，区间内下标异或上 $x$ 后结果是 $\texttt{5 4 7 6}$，正好对应区间 $\texttt{4 5 6 7}$ 在 $x = 1$ 时的答案！

我们发现，对于 $x\geq l$ 的部分，我们其实相当于将该区节点对应区间的答案转化为了线段树上同一层另一个节点在 $x' = x \bmod l$ 时的答案，而这个节点通过位运算是不难找到的。

于是对于每个节点，我们只需要维护 $0\sim l - 1$ 这 $l$ 种不同的 $l$ 对应的答案，查询时只需计算出另一个节点的位置，并查询其在 $x' = x \bmod l$ 的答案即可。

由于线段树一共 $\log n$ 层，每层节点的总长度之和为 $n$，于是时间复杂度和空间复杂度均为 $\mathcal{O}(n\log n)$。

代码中线段树的实现是左闭右开。

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 3e5 + 5, LOG = 20;

int o, k, m, n;
int a[N], sum[N], M[LOG][N];
std::vector<int> f[N << 2];

#define ls(u) (u << 1)
#define rs(u) (u << 1 | 1)

void build(int u, int l, int r) {
	int len = r - l, bit = std::__lg(len); f[u].resize(len); M[bit][l] = u;
	if (len == 1) return f[u][0] = 0, void();
	int mid = (l + r) >> 1;
	build(ls(u), l, mid); 
	build(rs(u), mid, r);
	for (int x = 0; x < len; x++) {
		if (x < len / 2) f[u][x] = f[ls(u)][x] + f[rs(u)][x] + (a[mid ^ x] == a[(mid - 1) ^ x]);
		else f[u][x] = f[ls(u)][x - (len / 2)] + f[rs(u)][x - (len / 2)] + (a[mid ^ x] == a[(mid - 1) ^ x]);
	}
}

int query(int u, int l, int r, int ql, int qr, int y) {
	int bit = std::__lg(r - l); 
	if (ql <= l && r - 1 <= qr) return f[M[bit][l ^ (y >> bit << bit)]][y % (1 << bit)];
	int mid = (l + r) >> 1, L = 0, R = 0; bool fL = false, fR = false;
	if (ql < mid)  L = query(ls(u), l, mid, ql, qr, y), fL = true;
	if (qr >= mid) R = query(rs(u), mid, r, ql, qr, y), fR = true;
	return fL ? (fR ? L + R + (a[mid ^ y] == a[(mid - 1) ^ y]) : L) : R;
}

int main() {

	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> o >> k >> m; n = (1 << k);
	for (int i = 0; i < n; i++) std::cin >> a[i];

	build(1, 0, n);

	int lst = 0, y = 0;
	for (int i = 1; i <= m; i++) {
		int op; std::cin >> op;
		if (op == 1) {
			int x; std::cin >> x; x ^= (o * lst);
			y ^= x;
		}
		if (op == 2) {
			int l, r; std::cin >> l >> r; l ^= (o * lst), r ^= (o * lst);
			if (l > r) std::swap(l, r);
			std::cout << (lst = r - l + 1 - query(1, 0, n, l, r, y)) << "\n";
		}
	}

	return 0;
}