1 해설
-
1
前言
思路
注意到本题不弱于区间 K 小值。()
试图直接考虑高明做法。结果你发现本题 很小。
于是你对着 这一维建主席树(可持久化 Trie),至于 这一维暴力多树二分就好了。
具体地,从高位向低位考虑,先考虑可否答案此位为 ,若是就是,若否则不是。
然后就做完力。
总复杂度 。
Code
由于使用指针实现,时空常数较大,在 Hydro 上跑不过去的说……
#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[1005],Y[300005]; struct node { friend uint size(node*p){return p==NULL?0:p->siz;} uint siz;node*son[2]; node():siz(0){son[0]=son[1]=NULL;} }; uint cnt=0; node*R[300005],*Now[2005]; int main() { uint n,m;scanf("%u%u",&n,&m); for(uint i=0;i<n;i++)scanf("%u",X+i); for(uint i=0;i<m;i++)scanf("%u",Y+i); R[0]=new node; for(uint i=0;i<m;i++) { uint v=Y[i]; *(R[i+1]=new node)=*R[i]; node*p=R[i],*q=R[i+1]; q->siz++; for(uint i=30;~i;i--) { uint op=v>>i&1; q=q->son[op]=new node; if(p!=NULL)p=p->son[op]; if(p!=NULL)*q=*p; q->siz++; } } uint q;scanf("%u",&q); while(q--) { uint u,d,l,r,k; scanf("%u%u%u%u%u",&u,&d,&l,&r,&k),u--,l--,k--; for(uint i=0;i<n;i++)Now[i<<1]=R[l],Now[i<<1|1]=R[r]; uint ans=0; for(uint i=30;~i;i--) { uint s=0; for(uint j=u;j<d;j++) { uint op=X[j]>>i&1; if(Now[j<<1]!=NULL)s-=size(Now[j<<1]->son[!op]); if(Now[j<<1|1]!=NULL)s+=size(Now[j<<1|1]->son[!op]); } if(k<s){ ans+=1u<<i; for(uint j=u;j<d;j++) { uint op=X[j]>>i&1; if(Now[j<<1]!=NULL)Now[j<<1]=Now[j<<1]->son[!op]; if(Now[j<<1|1]!=NULL)Now[j<<1|1]=Now[j<<1|1]->son[!op]; } } else{ k-=s; for(uint j=u;j<d;j++) { uint op=X[j]>>i&1; if(Now[j<<1]!=NULL)Now[j<<1]=Now[j<<1]->son[op]; if(Now[j<<1|1]!=NULL)Now[j<<1|1]=Now[j<<1|1]->son[op]; } } } printf("%u\n",ans); } return 0; }
- 1
정보
- ID
- 4103
- 시간
- 1000ms
- 메모리
- 256MiB
- 난이도
- 7
- 태그
- (N/A)
- 제출 기록
- 21
- 맞았습니다.
- 8
- 아이디