1 条题解
-
1
前言
思路
考虑二分答案。
对答案 从高位到低位考虑,直接考虑 的取值范围。
考虑低位任意,高位已定,直接易得 之值域亦为低位任意,高位已定。
于是立刻得到 的值域,拿颗主席树判断一下该区间内是否存在该值即可。
复杂度 。
Code
由于使用指针实现,时空常数较大。
#include <algorithm> #include <stdio.h> #include <vector> typedef long long llt; typedef unsigned uint;typedef unsigned long long ullt; typedef bool bol;typedef char chr;typedef void voi; typedef double dbl; template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;} template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;} template<typename T>T power(T base,T index,T mod){return((index<=1)?(index?base:1):(power(base*base%mod,index>>1,mod)*power(base,index&1,mod)))%mod;} template<typename T>T lowbit(T n){return n&-n;} template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;} template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;} template<typename T>T exgcd(T a,T b,T&x,T&y){if(!b)return y=0,x=1,a;T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;} uint X[300005]; struct node { friend uint size(node*p){return p==NULL?0:p->siz;} uint siz,dep;node*son[2]; node(uint d):siz(0),dep(d){son[0]=son[1]=NULL;} uint find(uint l,uint r) { if(l>=r)return 0; if(!l&&r==(1u<<(dep+1)))return siz; if(l<(1u<<dep)) if(r<=(1u<<dep))return son[0]==NULL?0:son[0]->find(l,r); else return(son[0]==NULL?0:son[0]->find(l,1u<<dep))+(son[1]==NULL?0:son[1]->find(0,r-(1u<<dep))); else return son[1]==NULL?0:son[1]->find(l-(1u<<dep),r-(1u<<dep)); } }; uint cnt=0; node*R[300005]; int main() { uint n,q;scanf("%u%u",&n,&q); for(uint i=0;i<n;i++)scanf("%u",X+i); R[0]=new node(20); for(uint i=0;i<n;i++) { uint v=X[i]; *(R[i+1]=new node(20))=*R[i]; node*p=R[i],*q=R[i+1]; q->siz++; for(uint i=20;~i;i--) { uint op=v>>i&1; q=q->son[op]=new node(i-1); if(p!=NULL)p=p->son[op]; if(p!=NULL)*q=*p; q->siz++; } } while(q--) { uint b,x,l,r;scanf("%u%u%u%u",&b,&x,&l,&r),l--; uint ans=0; for(uint i=20;~i;i--) { uint p=ans|(1u<<i); p^=b&~((1u<<i)-1); uint q=p+(1u<<i); if(p>x)p-=x;else p=0; if(q>x)q-=x;else q=0; if(R[r]->find(p,q)>R[l]->find(p,q)) ans|=1u<<i; } printf("%u\n",ans); } return 0; }
- 1
信息
- ID
- 4571
- 时间
- 3000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- (无)
- 递交数
- 24
- 已通过
- 15
- 上传者