struct SegBase { using ll = long long; bool zero; // 判断线性基中有无0出现 // maxsiz = log2(值域上边界) #define maxsiz 64 vector<ll> segbase; // 线性基本身 vector<ll> newbase; // 重构后的线性基 // 初始化线性基大小 SegBase(int n = maxsiz) { segbase = vector<ll>(n); } // 构建线性基 void insert(ll x) { if(x == 0) return ; int k = log2(x); if(!segbase[k]) return segbase[k] = x, void(); insert(segbase[k] ^ x); } // 查询一个元素是否可以被异或出来 int ask(ll x) { for(int i = maxsiz - 1; i >= 0; i--) if(x >> i & 1) x ^= segbase[i]; return x == 0; } // 查询异或最大值 ll askmax() { ll res = 0; for(int i =maxsiz - 1; i >= 0; i--) if(res ^ segbase[i] > res) res ^= segbase[i]; return res; } // 查询异或最小值，（一般来说就是线性基里的最小元素） ll askmin() { if(zero) return 0; for(int i = 0; i < maxsiz; i++) if(segbase[i]) return segbase[i]; } // 查询异或第k小 void rebuild() {// 重构线性基使得segbase[i]只留下第i位的1，使得他们互不影响 int cnt = 0, top = 0; for(int i = maxsiz - 1; i >= 0; i--) { for(int j = i - 1; j >= 0; j--) { if(segbase[i] >> j & 1) segbase[i] ^= segbase[j]; } } for(int i = 0; i < maxsiz; i++) if(segbase[i]) newbase.push_back(segbase[i]); } ll kth(int k) {// 互不影响之后就可以根据k的二进制选值了，注意线性基是否含0 if(k >= (1 << newbase.size())) return -1; ll res = 0; for(int i = maxsiz - 1; i >= 0; i--) if(k >> i & 1) res ^= newbase[i]; } int rank(ll x) {// kth函数的逆操作 int res = 0; for(int i = maxsiz - 1; i >= 0; i--) if(x >= newbase[i]) res |= 1 << i, x ^= newbase[i]; return res; } } ;