题解：P11071 「QMSOI R1」 Distorted Fate

· · 题解

奇异幽默搞笑题。CSP-S 出这个我得乐开花了。

  • 维护一个序列，支持区间异或一个数、查询区间所有前缀或的和。

考虑每一位 w 的贡献，找到她在区间中最左边出现的位置 p，则终点位于 p 及其右边的所有前缀的这一位上均为 1，剩余的为 0。那么这一位的贡献就是 2^w\times(r-p+1)。

考虑线段树，维护区间内每一位 w 为 0/1 出现的最左边位置 L_{0/1,w}（为 0 表示不存在这一位）。合并的时候考虑左儿子中是否有这一位，有就选择左儿子中这一位最左边的位置，否则选择右儿子的。

考虑怎样修改，异或对于每一位而言就是不变或 0/1 取反。枚举要异或的数的每一位，如果她为 0 则这一位信息不用变，否则 0/1 信息互换。维护区间异或懒标记即可。代码里写的标记永久化。

如果到这里就结束未免太容易了。这个做法的空间是 \mathcal{O}(n\log |V|) 的，但是线段树自带 4 倍常数、L 带 2 倍常数，无法通过本题。

但是可以动态开点啊，这样线段树空间只带二倍常数了，而存储左右孩子编号的数组不带 \log |V| 就不考虑了。没实现过，估计能压线过。

更优雅的方式是查理线段树。即，对于一个结点 (x,l,r)，m=\left\lfloor\dfrac{l+r}{2}\right\rfloor，令其左孩子编号为 2m，右孩子编号为 2m+1 即可。容易证明任意两个不同的区间对应的结点编号都是不同的。

这样已经可以压线空间通过本题了。但是无法通过加强版。

我们发现空间的大头在于 L 数组，而 L 数组中的信息显然是 \le n 的，就是说她们的二进制位数最多为 18。考虑将 L 数组中相邻三个下标的 int 数压进一个 long long 里面，这样实际只占用两个 int 的空间。就可以通过加强版了。时间复杂度为 \mathcal{O}(n\log n\log |V|)。

代码：

#include <bits/stdc++.h>
#define ll long long
template<class T> void read(T &x) {
    x = 0; T f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - 48; x *= f;
}
template<class T> void write(T x) {
    if (x > 9) write(x / 10); putchar(x % 10 + 48);
}
template<class T> void print(T x, char ed = '\n') {
    if (x < 0) putchar('-'), x = -x; write(x), putchar(ed);
}
using namespace std; const int N = 200005, V = 30, K = 10; 
const ll A[] = {0x3ffffffffc0000, 0x3ffff00003ffff, 0xfffffffff}; int n, q, a[N];
struct smallarr {
    ll a[K]; smallarr() { memset(a, 0, sizeof a); }
    int qry(int x) {
        return a[x / 3] >> (18 * (x % 3)) & ((1ll << 18) - 1);
    }
    void mdf(int x, int v) {
        a[x / 3] &= A[x % 3]; a[x / 3] |= (1ll * v) << ((x % 3) * 18);
    }
};
struct node { smallarr l0, l1; };
node operator+(node u, node v) {
    node ret;
    for (int i = 0; i < V; ++i)
        ret.l0.mdf(i, u.l0.qry(i) ? u.l0.qry(i) : v.l0.qry(i)),
        ret.l1.mdf(i, u.l1.qry(i) ? u.l1.qry(i) : v.l1.qry(i));
    return ret;
}
struct SGT {
    node s[N << 1]; int tg[N << 1];
    int ls(int x) { return x << 1; } int rs(int x) { return x << 1 | 1; }
    void build(int x, int l, int r) {
        if (l == r) {
            for (int i = 0; i < V; ++i)
                if (a[l] >> i & 1) s[x].l1.mdf(i, l); else s[x].l0.mdf(i, l);
            return;
        }
        int m = l + r >> 1; build(ls(m), l, m); build(rs(m), m + 1, r);
        s[x] = s[ls(m)] + s[rs(m)];
    }
    void mdf(int x, int l, int r, int ql, int qr, int v) {
        if (ql <= l && r <= qr) {
            tg[x] ^= v;
            for (int i = 0, a, b; i < V; ++i)
                if (v >> i & 1)
                    a = s[x].l1.qry(i), b = s[x].l0.qry(i),
                    s[x].l1.mdf(i, b), s[x].l0.mdf(i, a);
            return;
        }
        int m = l + r >> 1;
        if (ql <= m) mdf(ls(m), l, m, ql, qr, v);
        if (qr > m) mdf(rs(m), m + 1, r, ql, qr, v); s[x] = s[ls(m)] + s[rs(m)];
        for (int i = 0, a, b; i < V; ++i)
            if (tg[x] >> i & 1)
                a = s[x].l1.qry(i), b = s[x].l0.qry(i),
                s[x].l1.mdf(i, b), s[x].l0.mdf(i, a);
    }
    node qry(int x, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return s[x]; int m = l + r >> 1; node ret;
        if (qr <= m) ret = qry(ls(m), l, m, ql, qr);
        else if (ql > m) ret = qry(rs(m), m + 1, r, ql, qr);
        else ret = qry(ls(m), l, m, ql, qr) + qry(rs(m), m + 1, r, ql, qr);
        for (int i = 0, a, b; i < V; ++i)
            if (tg[x] >> i & 1)
                a = ret.l1.qry(i), b = ret.l0.qry(i),
                ret.l1.mdf(i, b), ret.l0.mdf(i, a);
        return ret;
    }
} tr;
signed main() {
    read(n); read(q); for (int i = 1; i <= n; ++i) read(a[i]); tr.build(1, 1, n);
    for (int op, l, r, x, la = 0; q--;) {
        read(op); read(l); read(r);
        l = (l ^ la) % n + 1; r = (r ^ la) % n + 1; if (l > r) swap(l, r);
        if (op & 1) read(x), tr.mdf(1, 1, n, l, r, x);
        else {
            node t = tr.qry(1, 1, n, l, r); ll ans = 0;
            for (int i = 0; i < V; ++i)
                if (t.l1.qry(i)) ans += (1ll << i) * (r - t.l1.qry(i) + 1);
            print(la = (ans & ((1ll << V) - 1)));
        }
    }
    return 0;
}