牛客50915题解

题目链接（可能需要权限）

题目大意：

给你n个集合，每个集合中都有不超过32个数，总共询问m次，每次询问区间 [L, R] 中的所有集合，是否都有一个异或和等于X的子集。

n 5e4，m 5e4，所有数值域 [0, ]。

难度：Ag+

分析：

这个题很明显，要求线性基的交，也就是说假设有A，B两个线性基，要求出一个线性基C，使得C表示的线性空间既包含于A所表示的线性空间，也包含于B所表示的线性空间。

下面先说线性基怎么求交。如果我们有A，B两个线性基，要求它们的交线性基C，那么显然B中所有能被A线性基表示的数，都要插入C中，之后如果 A ( B C ) 线性无关（B C 代表B中所有不能被A线性基表示的数），则C就是A，B的交线性基。

但问题是 A ( B C ) 未必线性无关，所以我们采取下面这种做法。再额外创建一个线性基D，同时D上每一位再额外保存一个值v，一开始把A中所有的数字 A[i] 插入D，并把对应插入位置的v也改为 A[i]。之后从低位到高位，将B中每一个数字 B[i] 插入D，每次插入时，维护一个u值，u一开始等于1，插入时每访问到D的某一位，u就等于u异或对应位上的v。

如果 B[i] 可以被D表示，那么插入一定失败，把 u 插入C；如果 B[i] 不可以被D表示，那么一定会将一个值X插入D中某一位，同时把对应位的v值改为u。这样将B遍历完毕之后，C就是A和B的交线性基。

现在我们会求线性基的交了，可以看出求两个线性基的交，时间复杂度为O(logX)，X为数的值域。之后比较明显，我们可以用线段树来维护区间的交线性基，每个非叶节点上的线性基等于其两个子节点的交线性基，叶节点上的线性基等于对应位置上的集合的线性基。

本题只有一种操作，就是询问区间 [L, R] 中的所有集合，是否都有一个异或和等于X的子集。如果每次询问时，先在线段树上把区间 [L, R] 的交线性基求出来，则对于单次询问，时间复杂度为O(logn * logX)，n为集合数。但事实上，根本没有必要求出区间 [L, R] 的交线性基，区间 [L, R] 在线段树上会被分成一些子区间，直接在这些子区间对应的节点上的线性基里面查询即可。单次询问时间复杂度O(logn * logX)，总时间复杂度O(nlogX + mlognlogX)，n为集合数，m为操作数，X为数字的值域。

至于线性基求交的正确性，我们在这里简单证明一下。线性基求交的核心思想是，找到一个所代表的线性空间等价于B的线性基B，将B中所有能被A表示的数字插入C，使得 A ( B C) 线性无关。这样C就是交线性基。

我们从低位到高位，将B中每一个数字 B[i] 插入D。如果 B[i] 不可以被D表示，那么把 B[i] 加入B；如果可以，那么把u插入B，接下来我们只需要证明B所表示的线性空间等价于B所表示的。注意到u一定是D中某些位的v值的异或和，D中的这些位，可能原本来自于A，也可能来自于B[j] (j < i) 的插入，我们找到所有这样的 j，记为 j、j……然后计算 B[j]、B[j]……的异或和，记为sum，我们发现u = B[i] ^ sum（这里不太好理解，可以自己在纸上算一下）。

对于B上的每一位B[i]，它要么等于B[i]，要么等于B[i] ^ B[j] ^ B[j]……（j, j…… < i），那么显然，B能由B经过初等变换得到，因此B所表示的线性空间等价于B所表示的。证毕。

代码：

# include <bits/stdc++.h>
# define MAXN 50005
# define ls (cur << 1)
# define rs ((cur << 1) | 1)

typedef unsigned uint;

struct SGT
{
    int n;
    uint a[MAXN << 2][32];    //记录每个节点上的线性基

    void insert(uint x, int cur)
    {
        for (int i = 31; i >= 0; --i)
            if (x >> i)
            {
                if (!a[cur][i])
                {
                    a[cur][i] = x;
                    break;
                }
                x ^= a[cur][i];
            }
    }

    void push_up(int cur)    //非叶节点上的线性基等于它的子节点的交线性基
    {
        uint t1[32], t2[32];
        for (int i = 0; i < 32; ++i)
            t1[i] = t2[i] = a[ls][i];
        for (int i = 0; i < 32; ++i)
            if (a[rs][i])
            {
                uint x = a[rs][i], tmp = 0;
                for (int j = 31; j >= 0; --j)
                    if (x >> j)
                    {
                        if (!t1[j])
                        {
                            t1[j] = x;
                            t2[j] = tmp;
                            break;
                        }
                        x ^= t1[j];
                        tmp ^= t2[j];
                    }
                if (!x)
                    insert(tmp, cur);
            }
    }

    void build(int left, int right, int cur)
    {
        if (left == right)    //叶节点上的线性基等于对应集合的线性基
        {
            int sz;
            scanf("%d", &sz);
            uint tmp;
            for (int i = 0; i < sz; ++i)
            {
                scanf("%u", &tmp);
                insert(tmp, cur);
            }
            return;
        }
        int mid = (left + right) >> 1;
        build(left, mid, ls);
        build(mid + 1, right, rs);
        push_up(cur);
    }

    void build(int size)
    {
        n = size;
        build(1, n, 1);
    }

    char query(int x, int y, uint val, int left, int right, int cur)
    {
        if (left >= x && right <= y)    //直接在子区间对应的节点上的线性基中检查
        {
            for (int i = 31; i >= 0; --i)
                if (val >> i)
                    val ^= a[cur][i];
            return val == 0;
        }
        int mid = (left + right) >> 1;
        char ret = 1;
        if (x <= mid)
            ret &= query(x, y, val, left, mid, ls);
        if (y > mid)
            ret &= query(x, y, val, mid + 1, right, rs);
        return ret;
    }

    char query(int x, int y, uint val)
    {
        return query(x, y, val, 1, n, 1);
    }
};

SGT s;

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    s.build(n);
    int x, y;
    uint val;
    for (int i = 0; i < m; ++i)
    {
        scanf("%d %d %u", &x, &y, &val);
        printf("%s\n", s.query(x, y, val) ? "YES" : "NO");
    }

    return 0;
}