@51nod - 1577@ 异或凑数

r囧r小猫 2021-12-03 03:51 176阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

从左到右一共 n 个数，数字下标从 1 到 n 编号。

一共 m 次询问，每次询问是否能从第 L 个到第 R 个数中（包括第 L 个和第 R 个数）选出一些数使得他们异或为 K。

**input**  
第一行一个整数 n (0<n<=500,000)。  
第二行 n 个整数，0<每个数<2^30。  
第三行一个数 m，表示询问次数 (0<m<=500,000)。  
接下来 m 行每行三个数，L, R, K (0<L<=R<=n,0<K<2^30)。

**output**  
M 行，每行为 YES 或 NO

**sample input**  
5  
1 1 2 4 6  
3  
1 2 1  
2 4 8  
3 5 7  
**sample output**  
YES  
NO  
NO

## @solution@ ##

能否选出一些数使这些数的异或和为 K。不难想到使用线性基来解决。

如果在题目给定的数据范围下想要直接构造出区间 \[L, R\] 的线性基实际上并不容易。  
带根号的比如莫队、分块肯定跑不动。在线使用线段树 O(nlog^3 n)，离线用分治可以做到 O(nlog^2 n)，能过一些点但是仍然不够优秀。  
关键在于我们想要构造出 \[L, R\] 的线性基，涉及到会合并两个线性基的操作，而这个操作复杂度始终是 log^2 n 降不下来。

不妨换个角度：我们给定 R 与 K，可以发现 L 越往左能异或出的值越多。于是我们可以尝试去找第一个可以异或出 K 的 L'，然后再比较 L 与 L' 的大小判断合法性。  
我们尝试对于每一个 R 维护出最靠近 R 的若干线性无关的数构成的线性基。这个思路类似于 bzoj3514 的解题思路。

具体操作来说，我们从左往右扫，由 R-1 的线性基递推出 R 的线性基。  
我们在线性基从高位往低位。如果当前的数在第 i 位为 1，再看线性基的第 i 位是否已经有数了。如果没有数则直接放进去，如果有数则比较当前的数和线性基里的数哪一个更靠近 R，将更靠近的放入线性基，另一个继续执行插入操作。  
有点像冒泡排序，更靠近的 R 的数将其他数挤了出去。

同时，我们可以发现线性基中的高位取了尽量靠近 R 的数。  
所以当我们尝试异或出 K 时，如果遇到某一位的数的位置小于 L，并且这一位数是我们在异或出 K 时所需要的，可以直接判定为“NO”。  
说实话这里严格证明起来很麻烦。我能力有限，无法找到一个较为简洁的该算法正确性证明。  
毕竟线性基也是线性代数啊。怎么可能会很简单。

## @accepted code@ ##

#include<cstdio> #include<algorithm> using namespace std; const int MAXN = 500000; int read() { int x = 0; char ch = getchar(); while( ch > '9' || ch < '0' ) ch = getchar(); while( '0' <= ch && ch <= '9' ) x = 10*x + ch - '0', ch = getchar(); return x; } void insert(int *pos, int *b, int x, int p) { for(int i=29;i>=0;i--) { if( x & (1<<i) ) { if( b[i] == 0 ) { b[i] = x; pos[i] = p; } else if( pos[i] < p ) { swap(pos[i], p); swap(b[i], x); } x ^= b[i]; } } } bool search(int *pos, int *b, int x, int p) { for(int i=29;i>=0;i--) { if( x & (1<<i) ) { if( b[i] == 0 || pos[i] < p ) return false; x ^= b[i]; } } return true; } int pos[MAXN + 5][30], b[MAXN + 5][30]; int main() { int n, m; n = read(); for(int i=1;i<=n;i++) { int x = read(); for(int j=29;j>=0;j--) pos[i][j] = pos[i-1][j], b[i][j] = b[i-1][j]; insert(pos[i], b[i], x, i); } m = read(); for(int i=1;i<=m;i++) { int L = read(), R = read(), K = read(); puts(search(pos[R], b[R], K, L) ? "YES" : "NO"); } }

## @details@ ##

好久没复习线性基了。。。写这个题的时候搞出了一个假的线性基。。。于是 WA 的很惨烈。。。

线性基的插入可以类比为动态加入方程的高斯消元。不过因为我们需要构造出特殊的线性基（即要求线性基的第 i 位的数二进制下最高位的 1 在第 i 位。。。好像有些绕口），所以写高斯消元无法满足这些性质。  
另外线性基还可以再特殊一点（类比高斯消元化至最简形式），即要求线性基第 i 位上如果有数，则其他位置的二进制下第 i 位上为 0。

好像很多人都是离线做的，不过这道题可以通过存储每个位置的线性基做到在线来着。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11123375.html