1 条题解
-
1
#include<cstdio> #include<algorithm> using namespace std; const int N=5e5+5; const int M=N*20; int a[N],root[N]; int n,m,totn=0,T_cnt=1; struct President_Tree{ int L,R,sum; }T[M]; int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();} while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return x*f; } void insert(int &now,int index,int l=0,int r=totn){ T[T_cnt++]=T[now];now=T_cnt-1; T[now].sum++; if (l==r)return; int mid=(l+r)>>1; if (index<=mid)insert(T[now].L,index,l,mid); else insert(T[now].R,index,mid+1,r); } int query(int i,int j,int ql,int qr,int l=0,int r=totn){ if (ql<=l && r<=qr)return T[j].sum-T[i].sum; int mid=(l+r)>>1,tt=0; if (ql<=mid)tt+=query(T[i].L,T[j].L,ql,qr,l,mid); if (mid<qr)tt+=query(T[i].R,T[j].R,ql,qr,mid+1,r); return tt; } bool find(int i,int j,int ql,int qr){ ql=max(0,ql);qr=min(qr,totn); if (ql>qr)return 0; return query(root[i],root[j],ql,qr); } int main(){ n=read(),m=read(); for (int i=1;i<=n;i++) totn=max(totn,a[i]=read()); root[0]=0; for (int i=1;i<=n;i++){ root[i]=root[i-1]; insert(root[i],a[i]); } for (int i=1;i<=m;i++){ int b=read(),x=read(),ql=read(),qr=read(),ans=0; for (int i=17;i>=0;i--){ int now=ans+((1^((b>>i)&1))<<i); if (find(ql-1,qr,now-x,now+(1<<i)-1-x))ans=now; else ans+=((b>>i)&1)<<i; } printf("%d\n",ans^b); } return 0; }
- 1
信息
- ID
- 215
- 时间
- 3000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 3
- 上传者