专栏文章
题解：AT_abc223_h [ABC223H] Xor Query
AT_abc223_h题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miouvpfw
- 此快照首次捕获于
- 2025/12/03 01:32 3 个月前
- 此快照最后确认于
- 2025/12/03 01:32 3 个月前
一道很水的 ABC 压轴题，正好让我从刚刚离开初中的感觉回到了才来初中的感觉。
感觉区分了做过 Ivan and Burgers 和没做过的人。
Ivan and Burgers前缀线性基
就是针对于求静态区间 线性基的一种利器。
前缀线性基仍然维护的是 的线性基，但是除了维护线性基内的值而外，还要维护它来自哪个位置的数。
举个例子，一段区间为 ，它的线性基为：
\dots & 2 & 1\\
\dots & 2 & 1
\end{matrix}$$
看起来两行是一样的，其实**截然不同**。
第一行代表的是普通线性基里面的值，第二行代表它从哪个地方转移而来。
再考虑另外一个例子：$[3,2]$。
首先插入 $3$：
$$\begin{matrix}
\dots & 3 &\dots\\
\dots & 1 &\dots
\end{matrix}$$
接下来插入 $2$ 的时候，我们考虑如果之后查询区间 $[2,n]$（默认 $n$ 的值很大），按照普通的把 $2$ 与 $3$ 异或得到 $1$ 的思路有问题：可能在需要用位置 $2$ 影响 $2^1$ 数位时，无法发挥其作用。就考虑把 $2$ 放在 $2^1$ 数位上，$3$ 变成 $1$ 放在 $2^0$ 数位上。
组成的线性基又变成了：
$$\begin{matrix}
\dots & 2 & 1\\
\dots & 2 & 1
\end{matrix}$$
正常的异或操作要照常进行。
等于是说：保证总体值最大的情况下，尽量把偏后的数放在线性基的高位。
在本题中，$l$ 和 $r$ 都是变化的，所以要储存每一个位置的线性基。
接下来，因为我们搞的到 $r$ 的线性基，所以我们就利用 $r$ 的线性基计算能否凑出 $x$。
一种有趣的做法是从高位向低位判断，若将目前的数异或上线性基这个位置的数，会使目前的数和 $x$ 异或值变小就异或。注意不要单纯判断与值或者或值的变化。
若之后能把原数变成 $x$ 则可以实现。时间复杂度 $O(n\log V+q\log V)$。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int a=0,b=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-') b=-1;
c=getchar();
}
while(isdigit(c)){
a=(a<<1)+(a<<3)+(c-'0');
c=getchar();
}
return a*b;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>=10) write(x/10);
putchar(x%10+48);
}
inline void write1(int x){
write(x),putchar(' ');
}
inline void write2(int x){
write(x),putchar('\n');
}
const int N=4*114514;
int n,q;
int a[N];
int pow2[N]; //处理 2 的次幂
int xxj[N][70]; //前缀线性基 构造方案跟着发生转变
int xxj2[N][70]; //记录数所在的位置
void insert(int sum,int rank,int rank1){
//前缀线性基 插到真正的空位才停下来
//保证高位的 rank 尽量在后面
//rank1 代表的是目前的情况
for(int i=62;i>=0;i--){
if(sum>=pow2[i]&&rank>xxj2[rank1][i]){
int sum2=xxj[rank1][i]; //至关重要！这里的 rank1 存下来就是为了防止在迭代时发生变化。
int rank2=xxj2[rank1][i]; //记录新的替换下来的数
xxj[rank1][i]=sum;
xxj2[rank1][i]=rank; //新的线性基记录
if(sum2){
//一个重要条件就是 sum2 真实存在
sum=sum2^xxj[rank1][i],rank=rank2; //遇到新的再插进去即可
}
else{
sum=0,rank=0;
}
}
else if(sum>=pow2[i]) sum^=xxj[rank1][i];
}
// for(int i=10;i>=0;i--){
// cout<<'#'<<i<<' '<<xxj[rank1][i]<<' '<<xxj2[rank1][i]<<endl;
// }
// cout<<endl;
}
void solve(int l,int r,int x){
// for(int i=10;i>=0;i--){
// cout<<'!'<<i<<' '<<xxj[r][i]<<' '<<xxj2[r][i]<<endl;
// }
//接下来要跑的是 [1,r] 的线性基
int include13=0; //这就是目前的数
for(int i=62;i>=0;i--){
if(xxj2[r][i]>=l){
//一个重要的前提条件就是线性基里面有这个值
int now=xxj[r][i];
// if(((include13^now)&x)>(include13&x)){
// include13^=now;
// }
// else if(((include13^now)|x)<(include13|x)){
// include13^=now;
// }
// if(((include13^now)|x)<(include13|x)){
// include13^=now;
// }
// else if(((include13^now)&x)>(include13&x)){
// include13^=now;
// }
if(((include13^now)^x)<(include13^x)){
include13^=now;
}
// cout<<'@'<<now<<' '<<include13<<endl;
}
}
if(include13==x) puts("Yes");
else puts("No");
// putchar('\n');
}
void init(){
pow2[0]=1;
for(int i=1;i<=62;i++){
pow2[i]=pow2[i-1]*2; //处理 2 的次幂
}
}
signed main(){
init();
n=read(),q=read();
for(int i=1;i<=n;i++){
for(int j=0;j<=68;j++){
xxj[i][j]=xxj[i-1][j]; //先把上一个线性基拷贝过来
xxj2[i][j]=xxj2[i-1][j];
}
a[i]=read();
insert(a[i],i,i);
}
while(q--){
int l=read(),r=read(),x=read(); //先输入若干个数
solve(l,r,x);
}
putchar('\n');
return 0;
}//信誓旦旦给了承诺 却被时间扑了空
```相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...