牛客50915题解

最新推荐文章于 2023-03-06 19:46:51 发布

红黑树的落叶

最新推荐文章于 2023-03-06 19:46:51 发布

阅读量182

点赞数 1

分类专栏：题解文章标签：线性基线段树

本文链接：https://blog.csdn.net/tyxacm/article/details/97692676

版权

题解专栏收录该内容

4 篇文章

订阅专栏

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

题目大意：

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

n $\le$ 5e4，m $\le$ 5e4，所有数值域 [0, $2^{32}$ ]。

难度：Ag+

分析：

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

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

但问题是 A $\cup$ ( B $\setminus$ 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(log $^{2}$ X)，X为数的值域。之后比较明显，我们可以用线段树来维护区间的交线性基，每个非叶节点上的线性基等于其两个子节点的交线性基，叶节点上的线性基等于对应位置上的集合的线性基。

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

至于线性基求交的正确性，我们在这里简单证明一下。线性基求交的核心思想是，找到一个所代表的线性空间等价于B的线性基B $^{'}$ ，将B $^{'}$ 中所有能被A表示的数字插入C $^{'}$ ，使得 A $\cup$ ( B $^{'}$ $\setminus$ 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 $_{1}$ 、j $_{2}$ ……然后计算 B[j $_{1}$ ]、B[j $_{2}$ ]……的异或和，记为sum，我们发现u = B[i] ^ sum（这里不太好理解，可以自己在纸上算一下）。

对于B $^{'}$ 上的每一位B $^{'}$ [i]，它要么等于B[i]，要么等于B[i] ^ B[j $_{1}$ ] ^ B[j $_{2}$ ]……（j $_{1}$ , j $_{2}$ …… < 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;
}