引子：qoj1168。引子需要的前置知识：P4151。简要题意给定\(n\)个点\(m\)条边的无向联通图\(G\)，边有边权。其中\((u,v)\)的距离\(d(u,v)\)定义为\(u\tov\)的最大\(\text{xor}\)路径。\(q\)次询问\(l,r\)，求\(\bigoplus\limits_{l\lei<j\ler}d(i,j)\)的值。\(1

线性基线性基是一种擅长处理异或问题的数据结构.设值域为\([1,N]\)，就可以用一个长度为\(⌈\text{log}_2N⌉\)的数组来描述一个线性基。特别地，线性基第\(i\)位上的数二进制下最高位也为第ii位。一个线性基满足，对于它所表示的所有数的集合\(S\)，\(S\)中任意多个数异或所得的结

基本对于一个值域为1-N的集合S它的线性基的值域与S相同它的线性基中的元素个数小于等于logN集合S中任意数异或和存在于线性基中线性基任意数异或和存在于集合S中插入首先，线性基大体长这样XXXXX称为第[线性基中数的个数]个数口XXXX口口口XX口口口口X称为第1个数d[i]

问题：洛谷P3812给定一个长度为\(n\)的序列，值域\(2^50\)，求在序列中选出若干个数的异或和最大值。思路:使用线性基，流程为，枚举\(n\)个数，每个数从二进制最高位向低位枚举，如果这个数含有这一位且这一位未放入任何数，直接放入，如果这个数有这一位但是放入了数，这个数就异或上已经放入的

我废话怎么这么多wwwwwwwwwww\(\color{white}地址\)rebuild思想就是使满足线性基的条件下，使每一个二进制位只在一个位置上为1。可以用高斯消元直接处理出，也可以处理出任意一组线性基后从后往前扫一遍，如果\(a_i\)第\(j\)位上为\(1\)，则\(a_i\oplusa_j\toa_i\)。此时如果