线段树套线性基——题解P4839 P哥的桶

文章历史

2022-08-03: 文章初稿，由于对算法介绍过于少而被管理员打回重造。

2020-08-06：将算法介绍进行扩写，并删除了一些可有可无的内容或玩梗内容。

管理员审核题解辛苦了。

简要题意

（这道题描述是真的长）

你需要维护一个数据结构，支持单点异或和区间求最大异或和。

思路

思维过程

对于这种区间问题，最容易想到的就是线段树。

而对于复杂的异或问题，最容易想到的就是线性基。

合在一起，就是线段树套线性基，类似经典的树套树。

详细思路

线段树大家应该都会，如果不会建议学习一下，这是一个很有用的数据结构。

线性基大家应该都会，如果不会可以看这篇博客。

首先，每一个线段树节点，都保存一个线性基。（单个线性基空间复杂度为 \(O(\log\max\{x\})\)，是可以接受的，不用担心会MLE）

首先，对于修改操作，我们不方便 \(\operatorname{pushup}\)，那么我们可以想到一个更好的方法：就是我们线段树DFS到的每一个区间节点都包含着修改值，那么我们考虑像权值线段树那样，经过一个点都把修改的元素插入节点线性基。

查询，我们可以考虑实现一个操作 \(\operatorname{expand}\)，表示用一个新的线性基扩展原来的线性基（说人话：将另一个线性基的所有元素都插入原来的线性基）

\(\operatorname{expand}\) 操作有一个简单有效的优化常数的方法，就是遍历线性基数组时，仅插入非 \(0\) 值。

然后，我们就可以像经典的线段树那样实现，只不过将维护信息并的运算符换成 \(\operatorname{expand}\) 即可。

（注：有的同学可能习惯将我的 \(\operatorname{expand}\) 操作换成类似线性基加法的 \(\operatorname{merge}\)，这一点看大家个人喜好）

时间复杂度 \(O(n\log m\log^{2}\max\{x\})\)，空间复杂度 \(O(n\log\max\{x\})\)，可以通过本题。

代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

namespace Basis{

	const int MAX_BIT = 60;

	struct Basis{

		int p[MAX_BIT+5];

		int _how_many_numbers_can_xor;

		void clear(){

			memset(p,0,sizeof(p));

			_how_many_numbers_can_xor=0;

		}

		Basis(){

			clear();

		}

		void insert(int x){

			for(int i=MAX_BIT;i>=0;i--){

				if(!(x>>i))continue;

				if(!p[i]){

					p[i]=x;

					_how_many_numbers_can_xor++;

					break;

				}

				x^=p[i];

			}

		}

		int max_xor(){

			int ans=0;

			for(int i=MAX_BIT;i>=0;i--){

				if((ans^p[i])>ans){

					ans^=p[i];

				}

			}

			return ans;

		}

		bool can_be_xor(int x){

			for(int i=MAX_BIT;i>=0;i--){

				if(x&(1ll<<i))x^=p[i];

			}

			return x==0;

		}

		int numbers_can_xor(){

			return (1ll<<_how_many_numbers_can_xor);

		}

		void expand(Basis &x){

			for(int i=MAX_BIT;i>=0;i--){

				if(x.p[i]){

					insert(x.p[i]);

				}

			}

		}

	};

}

namespace sgt{

	Basis::Basis t[200005];

	void update(int x,int v,int i,int l,int r){

		t[i].insert(v);

		if(l==r){

			return;

		}

		int mid=(l+r)>>1;

		if(x<=mid){

			update(x,v,i<<1,l,mid);

		}

		else{

			update(x,v,i<<1|1,mid+1,r);

		}

	}

	Basis::Basis result;

	void query(int ql,int qr,int i,int l,int r){

		if(ql<=l&&qr>=r){

			result.expand(t[i]);

			return;

		}

		int mid=(l+r)>>1;

		if(ql<=mid){

			query(ql,qr,i<<1,l,mid);

		}

		if(qr>mid){

			query(ql,qr,i<<1|1,mid+1,r);

		}

	}

}

int n,m;

signed main(){

	ios::sync_with_stdio(false);

	cin.tie(0);cout.tie(0);

	cin>>n>>m;

	while(n--){

		int op,a,b;

		cin>>op>>a>>b;

		if(op==1){

			sgt::update(a,b,1,1,m);

		}

		else{

			sgt::result.clear();

			sgt::query(a,b,1,1,m);

			cout<<sgt::result.max_xor()<<'\n';

		}

	}

	return 0;

}

加强版：P5607 [Ynoi2013] 无力回天 NOI2017

如果将单点修改变成区间修改，那么应该如何处理呢？可以思考一下。（提示：想想差分）

P5607 [Ynoi2013] 无力回天 NOI2017 题解

巴特西