异或凑数

wjh15101051's space

卧薪尝胆，厚积薄发。

异或凑数

Date: Sat Aug 25 23:00:35 CST 2018

In Category: NoCategory

Description：

从左到右一共 $n$ 个数，一共 $m$ 次询问，每次询问是否能从第 $L$ 个到第 $R$ 个数中选出一些数使得他们异或为 $K$ 。

$1\le n \le 500000$

Solution：

构造前缀线性基，对线性基中每一个数记录他的位置，如果在加入时发现这个位置已经有值，那么就把这个位置设成较靠后的一个，并把另一个继续处理后面的位，也就是说线性基中每个元素都尽量靠后。

最后在询问时照常遍历线性基，如果 $k$ 能被线性基消完，那么可以表出，但只处理 $pos\ge left$ 的，如果没有这个线性基，那么返回 $false$ 。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 500010

int a[MAXN];

#define MAXL 31

struct LinearBase

{

	int d[MAXL],p[MAXL];

	void insert(int k,int id)

	{

		for(int i = 30;i >= 0;--i)

		{

			if(k & (1 << i))

			{

				if(p[i] == 0)

				{

					d[i] = k;p[i] = id;

					break;

				}

				else

				{

					if(id > p[i]){swap(id,p[i]);swap(d[i],k);}

					k ^= d[i];

				}

			}

		}

		return;

	}

	bool query(int k,int lef)

	{

		for(int i = 30;i >= 0;--i)

		{

			if(k & (1 << i))

			{

				if(d[i] == 0 || p[i] < lef)return false;

				k ^= d[i];

			}

		}

		return true;

	}

}lb[MAXN];

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		a[i] = read();lb[i] = lb[i - 1];lb[i].insert(a[i],i);

	}

	scanf("%d",&m);

	int l,r,k;

	for(int i = 1;i <= m;++i)

	{

		l = read();r = read();k = read();

		if(lb[r].query(k,l))puts("YES");

		else puts("NO");

	}

	return 0;

}

In tag: 数学-线性基

wjh15101051