Luogu

LOJ

分析

考虑沿用 $x=0$ 时的贪心，则我们需要判断是否存在 $a_i+x$ 在某个区间内。

具体地，假设当前位是 $1$，则我们需要判断是否有一个 $a_i+x$ 的这一位为 $0$。假设前面已经确定的位加上当前位的最优解是 $t$，则 $a_i+x\in[t,t+2^i-1]$ 都满足条件，我们只需要判断是否存在 $a_i\in[t-x,t+2^i-1-x]$，主席树即可。当前位是 $0$ 的情况同理。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10,L=100000;

int n,m;

#define ls(o) ch[o][0]
#define rs(o) ch[o][1]
int rt[N],tot=0;
int ch[N*30][2],sumv[N*30];
void modify(int& o,int f,int l,int r,int p,int w) {
    o=++tot,ls(o)=ls(f),rs(o)=rs(f),sumv[o]=sumv[f]+w;
    if (l==r) return;
    int mid=(l+r)>>1;
    if (p<=mid) modify(ls(o),ls(f),l,mid,p,w);
    else modify(rs(o),rs(f),mid+1,r,p,w);
}
int query(int o,int l,int r,int ql,int qr) {
    if (!o) return 0;
    if (ql<=l&&r<=qr) return sumv[o];
    int mid=(l+r)>>1,res=0;
    if (ql<=mid) res+=query(ls(o),l,mid,ql,qr);
    if (qr>mid) res+=query(rs(o),mid+1,r,ql,qr);
    return res;
}
int query(int l,int r,int ql,int qr) {
    ql=max(0,ql),qr=min(qr,L);
    if (ql>qr) return 0;
    return query(rt[r],0,L,ql,qr)-query(rt[l-1],0,L,ql,qr);
}

int main() {
    n=read(),m=read();
    for (int i=1;i<=n;++i) modify(rt[i],rt[i-1],0,L,read(),1);
    while (m--) {
        int b=read(),x=read(),l=read(),r=read(),ans=0;
        for (int i=17;~i;--i) {
            int now=ans+((b&(1<<i))?0:(1<<i));
            if (query(l,r,now-x,now+(1<<i)-1-x)) ans=now;
            else ans+=((b&(1<<i))?(1<<i):0);
        }
        printf("%d\n",ans^b);
    }
    return 0;
}