線性基

定義

競賽中一般用到的都是異或空間線性基。線性基可以看作針對一個數(shù)集 \(S\) 而產(chǎn)生的新集合，滿足線性基中的任意數(shù)能產(chǎn)生的異或和的種類數(shù)和原集合能產(chǎn)生的異或和的種類數(shù)相同，且線性基的大小最小。

由此可以得出線性基中的幾條性質(zhì)（記線性基為 \(P\)）：

• 等價性。在原集合 \(S\) 上進(jìn)行異或運(yùn)算，和線性基 \(P\) 上進(jìn)行異或運(yùn)算的結(jié)果相同。

• 最小性。即線性基的大小是極小的。

• 線性基 \(P\) 中不存在異或和為 \(0\) 的子集。

  證明可以使用反證法：若存在 \(p_1\oplus p_2\oplus\cdots\oplus p_n\oplus p_x=0\)，則 \(p_1\oplus p_2\oplus\cdots\oplus p_n=p_x\)，則 \(p_x\) 是多余的，不滿足最小性。

構(gòu)造

可以使用貪心法構(gòu)造線性基。假設(shè)我們已經(jīng)構(gòu)造好了 \(P\) 的一部分，現(xiàn)在要插入 \(x\)。按位從高到低枚舉 \(P_i\)，若第 \(i\) 位上 \(x\) 的值為 \(1\)，就判斷此時 \(P_i\) 的情況：若 \(P_i\) 沒有值就插入，否則就將 \(x\) 異或 \(P_i\)。

這樣構(gòu)造的正確性在于：不管插入的成功與否，我們都可以保證 \(x\) 被成功表示。如果插入成功，則插入前一路走來的 \(P_i\) 和插入的位置異或起來可以得到 \(x\)；否則代表 \(x\) 本身就可以表示。

ll p[MAXN];
void ins(ll x){
	for(int i=50;~i;i--){
		if(!(x>>i)) continue;
		if(!p[i]) return p[i]=x,void();
		x^=p[i];
	}
}

不難發(fā)現(xiàn)單次插入的時間復(fù)雜度是 \(O(\log V)\)，總空間復(fù)雜度也是 \(O(\log V)\)。

應(yīng)用

求異或最大值

不僅可以求一個數(shù)集 \(S\) 中任意數(shù)的異或最大值，還可以求任意數(shù)異或一個給定的 \(x\) 的異或最大值。具體而言，從高到低枚舉二進(jìn)制位，貪心地，盡量讓當(dāng)前位置是 \(1\) 即可。因?yàn)榫€性基第 \(i\) 位的數(shù)一定滿足第 \(i\) 位是 \(1\) 且之前的位都是 \(0\)，所以具體實(shí)現(xiàn)上直接讓 \(\mathit{ans}\) 和異或 \(P_i\) 后的值取最大值即可。

ll sum(){
    ll res=0;
    for(int i=60;~i;i--) res=max(res,res^p[i]);
    return res;
}

求異或最小值

直接將上面的 \(\max\) 改為 \(\min\) 即可。

特殊地，如果是單純求一個數(shù)集 \(S\) 中的異或最小值，可以直接輸出線性基中的最小值。但是，如果這個數(shù)集中存在有數(shù)插入失敗的情況，那么異或最小值就是 \(0\)。

線性基合并

直接把一個線性基中的所有元素往另一個線性基中插一遍即可。復(fù)雜度 \(O(\log^2V)\)。

實(shí)現(xiàn)的時候可以直接封裝起來。

LB operator+(const LB&b){
    LB res=*this;
    for(int i=0;i<=60;i++){
        if(!b.p[i]) continue;
        res.ins(b.p[i],i);
    }
    return res;
}

求排名

對于去重的排名，考慮對于任意一個 \(P_i\)，我們只關(guān)心它有沒有值。如果有，說明 \(i\) 這一位可以選擇是否異或來選擇成為 \(0/1\)，反之選擇是固定的。所以我們從小到大枚舉每一位，假設(shè)當(dāng)前枚舉到第 \(k\) 個有值的線性基，如果此時 \(x\) 同樣有值，排名會加上 \(2^{k-1}\) 表示這一位為 \(0\) 的情形，反之不予操作即可。

int rnk(int x){
	int res=0,sm=1;
	for(int i=0;i<=30;i++){
		if(!p[i]) continue;
		if(x>>i&1) res=(res|sm)%MOD;
		sm<<=1;
	}
	return res;
}

對于不去重的排名，考慮在線性基中若有 \(k\) 個數(shù)插入失敗，則這 \(k\) 個數(shù)都能任意組合選擇和線性基內(nèi)的一些數(shù)異或得到 \(0\)。那么任選方案有 \(2^k\) 種，用上面的 rnk 函數(shù)求出來的答案記為 \(s\)，則最終答案是 \((s-1)\times2^k+1\)。

帶刪除線性基

對于一些類似線段樹分治一樣的表述，不僅能用線段樹分治解決，還能用帶刪除線性基解決。

仍然需要離線。首先需要知道每個時間點(diǎn)都干了些什么，如果是加了個數(shù)就需要預(yù)處理出這個數(shù)會在哪里被刪掉。處理好這個之后，我們?nèi)匀话凑諘r間處理操作，但是需要給插入線性基的數(shù)一個時間戳表示這個數(shù)被刪除的時間，查詢的時候只查詢時間戳在當(dāng)前時間之后的。對于線性基的每一位，時間戳應(yīng)優(yōu)先保留靠后的一個。

具體見代碼：（BZOJ4184 shallot）

constexpr int MAXN=5e5+5;
int n,a[MAXN],del[MAXN];
unordered_map<int,int>mp;
struct{
	int p[32],t[32];
	void ins(int x,int tim){
		for(int i=30;~i;i--){
			if(!(x>>i)) continue;
			if(tim>t[i]) swap(x,p[i]),swap(tim,t[i]);
			if(!tim) return;
			x^=p[i];
		}
	}
	int ask(int tim){
		int res=0;
		for(int i=30;~i;i--) if(tim<t[i]) res=max(res,res^p[i]);
		return res;
	}
}LB;

int main(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		if(a[i]>0) mp[a[i]]=i,del[i]=n+1;
		else del[mp[-a[i]]]=i;
	}
	for(int i=1;i<=n;i++){
		if(a[i]>0) LB.ins(a[i],del[i]);
		write(LB.ask(i));
	}
	return fw,0;
}