改死我了，没用一点。（正解）
于是乎,随便打了个暴力碰运气
// 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位
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,那么我们希望它是长这样的
(min)a[j]+x:−−−0 0 0 0
(max)a[j]+x:−−−0 1 1 1
容易求出a[i]∈[ans−x,ans−x+(1<<i)−1]
同理当b的第i位是0时
a[i]∈[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(lr) 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||num0) 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;
}
