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=500000+10;
const int M=32;
int n,m;
int a[N];
char ch;
il void rd(int &x){
    x=0;
    while(!isdigit(ch=getchar()));
    for(x=numb;isdigit(ch=getchar());x=x*10+numb);
}
struct node{
    int lin[M];
    int pos[M];
}lb[N];
int main()
{
    rd(n);
    for(ri i=1;i<=n;i++){
        rd(a[i]);
    }
    for(ri i=1;i<=n;i++){
        lb[i]=lb[i-1];
        int tmp=a[i];
        int po=i;
        for(ri j=29;j>=0;j--){
            if(tmp&(1<<j)){
                if(lb[i].lin[j]==0){
                    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=1;i<=m;i++){
        rd(l),rd(r),rd(k);
        bool fl=true;
        for(ri j=29;j>=0;j--){
            if(k&(1<<j)){
                if(lb[r].lin[j]==0){
                    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 0;
}      

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的一個元素，與最晚時間線性基沖突