从高位开始,尽量与$b$错开地来安排$c-x$。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int N=2e5+5,mod=1e9+7;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>
void qw(o x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct HJT{int l,r,s;}t[N<<5];int root[N];int cnt;
void update(int l,int r,int &x,int y,int pos)
{
t[x=++cnt]=t[y];++t[x].s;
if(l==r)return ;
int mid=l+r>>1;
if(pos<=mid)update(l,mid,t[x].l,t[y].l,pos);
else update(mid+1,r,t[x].r,t[y].r,pos);
}
int query(int x,int l,int r,int L,int R)
{
if(L<=l&&R>=r)return t[x].s;
int val=0,mid=l+r>>1;
if(L<=mid)val+=query(t[x].l,l,mid,L,R);
if(R>mid)val+=query(t[x].r,mid+1,r,L,R);
return val;
}
int a[N];
int main()
{
//freopen("food1.in","r",stdin);
int n,m,mx=0;qr(n),qr(m);
for(int i=1;i<=n;i++)qr(a[i]),mx=max(a[i],mx);
for(int i=1;i<=n;i++)update(1,mx,root[i],root[i-1],a[i]);
for(int i=1;i<=m;i++)
{
int b,x,ld,rd,c=0;qr(b),qr(x),qr(ld),qr(rd);
for(int j=17;~j;j--)
{
int l,r;
if(b>>j&1)l=(c-x),r=(c-x)+(1<<j)-1;//查询是否存在aj属于[c-x,c-x+(1<<j)-1]这个区间。
else l=(c-x)+(1<<j),r=(c-x)+(1<<(j+1))-1;//与上同理。
l=max(l,1);r=min(mx,r);
if(query(root[rd],1,mx,l,r)-query(root[ld-1],1,mx,l,r))c|=((b>>j&1)^1)<<j;
else c|=(b>>j&1)<<j;
}
qw(c^b);puts("");
}
return 0;
}
最后一次更新于2020-03-22
0 条评论