主席树题解

P3293 [SCOI2016] 美味

前置知识：0-1 Trie 求最大（小）异或值。这个应该所有人都会了，但是这里怕你们说我不负责讲一讲。0-1 Trie 把存进去的每个整数由高位向低位存储二进制值，前面没有就补齐 0。当需要在 Trie 存储的数中找到一个使它与给定数的异或值最大时，从高到低位遍历给定数并从根节点遍历 Trie. 如果当前位为 0 就寻找 Trie 的当前节点有没有值为 1 的儿子，否则查找有没有值为 0 的儿子（与给定数正好相反）。如果有就递归与原数相反的位，否则就只能递归另一个位了。这个贪心确保了最高位的值。

此题只是加了一个 $x_i$. 怎么做呢？依旧遍历 $b_i$ 的位。如果是 1，我们希望能找到一个此位为 0 的 $a_i$. 如图：

我们要找最小 a 和最大 a 之间有没有值。注意到最小 a 正好就是当前的 ans, 最大值可以算出是 $ans+2^i-1$ ，其中 i 是当前位到最右端的距离。

于是我们只需要求在两个区间 $[l,r]$ 和 $[ans,ans+2^i-1]$ 的约束条件下有没有值即可。如果 b 的当前位是 0，我们也可以计算出对应的左右端点，具体看代码。有两个区间的约束条件，考虑主席树。下面的主席树使用了一种类似 0-1 Trie 的存储方法，但其实和主席树的普通写法是一样的。我原先是求具体有多少个值再判断，但是这个玩意似乎可以直接返回 bool 值然后通过短路的性质优化。于是我就从 2.50s 加速到了 1.80s.

$Code:$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define mid (l+r>>1)
#define k (sum[v]-sum[u])
#define enter putchar_unlocked('\n')
int n,m,N,a[500005],cnt,t[9000005],ch[9000005][2],sum[9000005],b,x,l,r,ans;
void update(int pre,int &cur,int l,int r,int x){
    cur=++cnt,ch[cur][0]=ch[pre][0],ch[cur][1]=ch[pre][1],sum[cur]=sum[pre]+1;
    if(l==r)return;
    if(mid>=x)update(ch[pre][0],ch[cur][0],l,mid,x);
    else update(ch[pre][1],ch[cur][1],mid+1,r,x);
}
bool qry(int u,int v,int l,int r,int L,int R){
    if(R<l||L>r||!k)return 0;
    if(L<=l&&r<=R)return 1;
    return (bool)qry(ch[u][0],ch[v][0],l,mid,L,R)||(bool)qry(ch[u][1],ch[v][1],mid+1,r,L,R);
}
il int read(){
    re int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
il void write(int x){
    x<0?x=-x,putchar_unlocked('-'):0;static short st[50],top(0);
    do st[++top]=x%10,x/=10;while(x);
    while(top)putchar_unlocked(st[top--]|48);
}
signed main(){
    n=read(),m=read();
    for(re int i=1;i<=n;++i)N=max(N,a[i]=read());
    for(re int i=1;i<=n;++i)update(t[i-1],t[i],0,N,a[i]);
    while(m--){
        b=read(),x=read(),l=read(),r=read(),ans=0;
        for(re int i=18;i>=0;--i){
            ans+=(1<<i)*(int)(b&(1<<i)&&!qry(t[l-1],t[r],0,N,ans-x,ans-x+(1<<i)-1));
            ans+=(1<<i)*(int)(!(b&(1<<i))&&qry(t[l-1],t[r],0,N,ans-x+(1<<i),ans-x+(1<<(i+1))-1));
        }
        write(ans^b),enter;
    }
    return 0;
}