题解 P3293 【[SCOI2016]美味】

· · 题解

这题调了一个上午不知哪里错了，可能我写代码像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]满足上述条件

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

首先按照套路把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;
}