51nod 1577 异或凑数

思路真的是挺巧妙的。

让我惊叹，原来线性基还能这么做？！？！

好吧，这种取若干个数异或凑数的题目怎么能少的了线性基呢？

但是，问题集中在于怎么快速提取一个区间的线性基

暴力n^2

线段树维护线性基？分区间logn，合并一次logn^2 O（nlogn^3）GG

然后就一脸不可做了。

题解：
“容易”想到，一个线性基里面的元素可以用线性基外的元素替换的。

只要保证还能表示出原来的线性空间，那么一定可以替换。

所以，我们给每个点维护一个线性基。

lb[r]表示，由1~r的所有元素选择构成的线性基，其中元素尽可能地靠后。

当lb[r-1]转移到lb[r]的时候，

可以把r-1的所有元素拿出来，把a[r]拿出来，按照位置排序，贪心加入lb[r]。

这样，预处理O(nlogn^2)

查询呢？直接把lb[r]中的元素拿出来，根据位置是否大于等于l放进一个临时线性基里。

之后把k尝试加入线性基，能加入就说明无法表出，否则可以。

O(nlogn^2)

但是还是过不去？！~？！？

发现，我们转移lb，查询的时候，真的是非常暴力的操作。

能不能再少一个log？

发现，lb[r-1]->lb[r]不就是可能多了一个a[r]吗？

所以有一个贪心策略：

首先复制过来lb[r-1],尝试加入x=a[r]

如果x有j位的1，lb中没有，加进去，break。

如果lb中有，如果lb的j这个位置的元素实际位置更靠前，那么可能询问的时候取不到，就和x换一下，然后继续放下一位（记得无论如何要异或一下）。

并且发现，我们这样做，会使得高位的位置尽可能靠后。

所以询问的时候，从高位到低位，如果没有这一位，那么直接NO就可以了。

如果一直可以，那么就是YES

Code：

#include<bits/stdc++.h>

#define numb ch-'0'

#define ri register int

#define il inline

using namespace std;

const int N=+;

const int M=;

int n,m;

int a[N];

char ch;

il void rd(int &x){

    x=;

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

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

}

struct node{

    int lin[M];

    int pos[M];

}lb[N];

int main()

{

    rd(n);

    for(ri i=;i<=n;i++){

        rd(a[i]);

    }

    for(ri i=;i<=n;i++){

        lb[i]=lb[i-];

        int tmp=a[i];

        int po=i;

        for(ri j=;j>=;j--){

            if(tmp&(<<j)){

                if(lb[i].lin[j]==){

                    lb[i].lin[j]=tmp;

                    lb[i].pos[j]=po;

                    break;

                }

                else {

                    if(po>lb[i].pos[j])

                    {

                    swap(tmp,lb[i].lin[j]);

                    swap(po,lb[i].pos[j]);

                    }

                    tmp^=lb[i].lin[j];

                }

            }

        }

    }

    rd(m);

    int l,r,k;

    for(ri i=;i<=m;i++){

        rd(l),rd(r),rd(k);

        bool fl=true;

        for(ri j=;j>=;j--){

            if(k&(<<j)){

                if(lb[r].lin[j]==){

                    fl=false;break;

                }

                else{

                    if(lb[r].pos[j]<l){

                        fl=false;break;

                    }

                    else{

                        k^=lb[r].lin[j];

                    }

                }

            }

        }

        if(fl){

            puts("YES");

        }

        else puts("NO");

    }

    return ;

}

upda：2016.6.10

其实就是一个套路，维护最晚时间线性基

只要证明两个事：

1.合法的区间一定合法，不合法的区间一定还是不合法

2.线性基里可以取的元素一定是[L,R]元素暴力加入后的线性基（相当于可以代替暴力插入[L,R]的元素）

先证明2

设R的最晚线性基为B，把[L,R]元素暴力插入的线性基是S

发现可以取的元素，如果形如a^b^c^d（不妨认为，出现时间a<b<c<d）那么如果这个元素可以保留，那么b,c,d有关的都可以保留，

所以一定是S的子集

又如果是真子集，即存在一个元素属于S，却不属于B，那么这个元素，一定可以顶替掉B中<L的一个元素，与最晚时间线性基矛盾

由于2成立，1自然就成立了。

巴特西

51nod 1577 异或凑数

最新文章

热门文章