链接:#2016. 「SCOI2016」美味 - 题目 - LibreOJ (loj.ac)
题意:给定一段序列,多次查询区间 [ l , r ] [l,r] [l,r] 内的数字 a i + x a_{i}+x ai+x 与 b b b 异或最大值,每次询问给出 b , x , l , r b,x,l,r b,x,l,r。
题解:如果不附带这个 x ,就是一道可持久化 01trie 的裸题,但加上 x 之后,按位难以判断一个特定的数。不过可以去判定一个范围,从高位往低位贪心取。每次查询若这一位取与 b 反向的值是否存在这类数,存在的话就这么取,不然反着取。同时需要把加上的 x 的影响消去。判断某个区间的某个值域是否存在数,很明显主席树维护下就可以了。复杂度 O ( n l o g n l o g w ) O(nlog\ nlog\ w) O(nlog nlog w) ,w 为值域。
#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include<iostream> #include<algorithm> #include<vector> #include<cstring> using namespace std; const int maxn=2e5+5; int a[maxn],n,m,b,x,l,r,mx; int ls[maxn*20],rs[maxn*20],sum[maxn*20],rt[maxn],now; void update(int u,int&v,int l,int r,int pos) { v=++now,ls[v]=ls[u],rs[v]=rs[u],sum[v]=sum[u]+1; if(l==r)return; int mid=l+r>>1; if(pos<=mid)update(ls[u],ls[v],l,mid,pos); else update(rs[u],rs[v],mid+1,r,pos); return; } int query(int u,int v,int l,int r,int ql,int qr) { if(ql<=l&&r<=qr)return sum[v]-sum[u]; int mid=l+r>>1,res=0; if(ql<=mid)res+=query(ls[u],ls[v],l,mid,ql,qr); if(mid<qr)res+=query(rs[u],rs[v],mid+1,r,ql,qr); return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; mx=2e5; for(int i=1;i<=n;i++) { cin>>a[i],update(rt[i-1],rt[i],1,mx,a[i]); } for(int i=1;i<=m;i++) { cin>>b>>x>>l>>r; int ans=0,res=0; for(int j=17;j>=0;j--) { int p=(b>>j&1)^1; if(query(rt[l-1],rt[r],1,mx,res+p*(1<<j)-x,res+(1+p)*(1<<j)-1-x)) { ans+=1<<j,res+=p*(1<<j); } else res+=(p^1)*(1<<j); } cout<<ans<<"\n"; } return 0; }