题解 Xor-Forces

rui_er · 2024-08-10 18:36:48 · 题解

本题解为 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;
}