自动搬运

查看原文

来自洛谷，原作者为

	XY_cpp **

搬运于2025-08-24 21:47:24，当前版本为作者最后更新于2019-08-03 11:22:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这题调了一个上午不知哪里错了，可能我写代码像c*k

十年生死两茫茫，BUG何处藏，唯有泪千行

于是乎,随便打了个暴力碰运气,吸一口氧气,还不够,再吸一口臭氧

// luogu-judger-enable-o2
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
int a[N],b[N],x[N],l[N],r[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;++i)
        scanf("%d%d%d%d",&b[i],&x[i],&l[i],&r[i]);
    for(int i=1;i<=m;++i)
    {
        int res=0;
        for(int j=l[i];j<=r[i];++j)
        {
            int now=b[i]^(a[j]+x[i]);
            res=max(res,now);
        }
        printf("%d\n",res);
    }
    return 0;
}

然后我发现我愉快的$AC$了

正所谓

n方过百万,暴力碾标算

不过如果你像我一样，是个求知若渴，勤奋好学的好孩子，请看下面的正解

---

我来口胡一下正解

睡了一个中午醒来看了一眼题面,发现$a[i]$可以是$0$,于是恍然大悟大雾,把左边端点改成$0$,宝宝就愉快的$AC$了

题目要求$b_i\ xor\ (a_j+x_i)$ 显然不能硬求,看到异或,考虑按照位处理

假设从高到低处理到第$i$位(从右往左数,个位是第$0$位),

设之前求出的$a[i]$的答案为$ans$(如果你不太明白这个变量的意思,请看下面的例子,前提是你要知道基本的$xor$性质)

---

当前处理到第$2$位

$$\ \ \ \ b:1010**\ *$$ $$ans:0101** \ *$$

所以当前$ans$记录的是一个满足题目限制的$a[j]+x_i$,使得$b$ $xor$ $a[j]+x_i$的$3-7$位达到最大值,我们之所以要从高到低枚举,就是因为要贪心的求,先让高位满足最大值.

这时,聪明的你就要发问了:万一没有一个$a[j]+x_i$能使某一位达到最大值,那怎么办呢?

答:没有办法,$b$ $xor$ $a[j]+x_i$之后的这一位只能为$0$

---

经过一番分析之后,我们得出核心思路:

若第 $b$的第$i$位是$1$,那么我们希望它是长这样的

$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ b:---1**\ * $$$$(min)a[j]+x:---0\ 0\ 0\ 0$$ $$(max)a[j]+x:---0\ 1\ 1\ 1$$

容易求出$a[i] \in [ans-x,ans-x+(1<<i)-1]$

同理当$b$的第$i$位是$0$时

$a[i] \in [ans-x+(1<<i),ans-x+(1<<i+1)-1]$

我们可以直接主席树上查询对于第$i$个人的$[l_i,r_i]$内有无$a[i]$满足上述条件

• 当$b$的第$i$位是$1$时，若有这样一个$a[i]$，$ans+=0<<i$，反之$ans+=1<<i$
• 当$b$的第$i$位是$0$时，若有这样一个$a[i]$，$ans+=1<<i$，反之$ans+=0<<i$

---

关于主席树部分，因为有区间内查询的约束，所以我们首先想到的是主席树

首先按照套路把$l-1$，$r$提出来，$sum$相减后得出这段区间内的数值个数，然后按照一般套路分成两半往下找就可以了

如果你连主席树部分都不能理解，建议先把模版切熟练

---

上代码，很短，暴力更短

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N],rt,t[N<<5],ch[N<<5][2],sum[N<<5];
void update(int pre,int &k,int l,int r,int x)
{ 
    if(r<x||l>x) return ;
    k=++rt,ch[k][0]=ch[pre][0],ch[k][1]=ch[pre][1],sum[k]=sum[pre]+1;
    if(l==r) return;
    int mid=(l+r)>>1;
    update(ch[pre][0],ch[k][0],l,mid,x);
    update(ch[pre][1],ch[k][1],mid+1,r,x);
}
int query(int u,int v,int l,int r,int x,int y)
{
    int num=sum[v]-sum[u],mid=(l+r)>>1;
    if(y<l||x>r||num==0) return 0;
    if(x<=l&&r<=y) return num;
    return query(ch[u][0],ch[v][0],l,mid,x,y)+query(ch[u][1],ch[v][1],mid+1,r,x,y);
}
int main()
{
    int n,m,q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),m=max(a[i],m);
    for(int i=1;i<=n;i++)
        update(t[i-1],t[i],0,m,a[i]);
    while(q--)
    {
        int b,x,l,r,ans=0;
        scanf("%d%d%d%d",&b,&x,&l,&r);
        for(int i=18;i>=0;i--)
        {
            if(b&(1<<i)&&!query(t[l-1],t[r],0,m,ans-x,ans-x+(1<<i)-1)) ans+=(1<<i);//之前就是这写错了
            if(!(b&(1<<i))&&query(t[l-1],t[r],0,m,ans-x+(1<<i),ans-x+(1<<(i+1))-1)) ans+=(1<<i);
        }      
        printf("%d\n",ans^b);
    }
    return 0;
}