2019牛客暑期多校訓練營（第四場） B xor 線性基求交+線段樹

傳送門

題意：對于一個集合，若該集合的某個子集的異或和等于x，則稱該集合可以“表示”x，給定個n個集合和m次詢問，每次詢問給定l,r,x，表示詢問對于任意i∈[l,r] 第i個集合中的數能否表示x。1≤n,m≤50000 。

大佬題解

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=5e4+10;
struct node{
    ll b[35];
    node(){memset(b,0,sizeof(b));}
    void insert(int x)
    {
        for(int i=31;i>=0;i--)
        {
            if(x>>i)
            {
                if(!b[i])
                {
                    b[i]=x;
                    break;
                }
                x^=b[i];
            }
        }
    }
    int check(int x)
    {
        for(int i=31;i>=0;i--)
        {
            if(x>>i)
            {
                if(!b[i])
                    return 0;
                x^=b[i];
            }
        }
        return 1;
    }
}a[maxn<<2];
void pushup(int rt)// 更新操作
{
        node t1,t2;
	int ls=rt<<1,rs=rt<<1|1;
	for(int i=0;i<32;i++)
	t1.b[i]=t2.b[i]=a[ls].b[i];
	for(int i=0;i<32;i++)
	{
		if(a[rs].b[i])
		{
			int x=a[rs].b[i],tp=0;
			for(int j=31;j>=0;j--)
			{
				if(x>>j)
				{
					if(!t1.b[j])
					{
						t1.b[j]=x,t2.b[j]=tp;
						break;
					}
					x^=t1.b[j],tp^=t2.b[j];//tp=
				}
			}
			if(!x)
			a[rt].insert(tp);
		}
	}
}
void build(int l,int r,int rt)
{
	if(l==r)
	{
		int sz,tp;
		scanf("%d",&sz);
		for(int i=0;i<sz;i++)
		{
			scanf("%d",&tp);
			a[rt].insert(tp);
		}
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	pushup(rt);
}
bool query(int L,int R,int val,int l,int r,int rt)
{
	if(L <=l&&R>=r)
	{
	    return a[rt].check(val);
	}
	int mid=(l+r)>>1;
	bool res=1;
	if(L<=mid)
	res&=query(L,R,val,l,mid,rt<<1);
	if(R>mid)
	res&=query(L,R,val,mid+1,r,rt<<1|1);
	return res;
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	build(1,n,1);
	for(int i=1;i<=m;++i)
	{
		int x,y;
		int val;
		scanf("%d%d%d",&x,&y,&val);
		if(query(x,y,val,1,n,1))
		printf("YES\n");
		else
		printf("NO\n");
	}
	return 0;
}