正題

題目鏈接:https://www.luogu.com.cn/problem/P3293

---

題目大意

給出一個長度為$n$的序列，$m$次詢問給出$b,x,l,r$表示詢問在$[l,r]$中找到一個數(shù)字$a$使得$bxor(a+x)$的值最大。

$1\le n,m\le 2\times 10^5,0\le a,b,x<10^5$

---

解題思路

往$Trie$上想就很容易卡思路，考慮正常情況下我們是怎么求$bxora$最大的。

其實在$Trie$樹上條等價于每次詢問一個區(qū)間內(nèi)有沒有值然后再選擇往左或者往右，現(xiàn)在這個$x$就是相當于把我們詢問的區(qū)間移動了，既然$Trie$樹解決不了這樣的問題那么就考慮一下主席樹。

定義一下$z$表示異或的那個數(shù)的基數(shù)（前面枚舉的位已經(jīng)確定），從大到小枚舉$i$，若$b$的第$i$位有那么最好是讓$a+x$的第$i$位沒有，也就是詢問$[z?x,z?x+2^i)$。如果第$i$位沒有那么最好是$a+x$的第$i$位有，那么詢問$[z?x+2^i,z?x+2^{i+1})$就好了。

時間復雜度$O(n{\log }^{2}n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e5+10,M=N<<5,Li=1e5; int n,m,cnt,rt[N],w[M],ls[M],rs[M]; int Change(int x,int L,int R,int pos){int now=++cnt;w[now]=w[x]+1;if(L==R)return now;int mid=(L+R)>>1;if(pos<=mid)ls[now]=Change(ls[x],L,mid,pos),rs[now]=rs[x];else rs[now]=Change(rs[x],mid+1,R,pos),ls[now]=ls[x];return now; } int Ask(int x,int y,int L,int R,int l,int r){if(!(w[y]-w[x]))return 0;if(L==l&&R==r)return w[y]-w[x];int mid=(L+R)>>1;if(r<=mid)return Ask(ls[x],ls[y],L,mid,l,r);if(l>mid)return Ask(rs[x],rs[y],mid+1,R,l,r);return Ask(ls[x],ls[y],L,mid,l,mid)+Ask(rs[x],rs[y],mid+1,R,mid+1,r); } int Query(int L,int R,int l,int r){if(l<0)l=0;if(r>Li)r=Li;if(r<l)return 0;return Ask(rt[L-1],rt[R],0,Li,l,r); } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int x;scanf("%d",&x);rt[i]=Change(rt[i-1],0,Li,x);}while(m--){int b,a,l,r,z=0,ans=0;scanf("%d%d%d%d",&b,&a,&l,&r);for(int i=17;i>=0;i--){if((b>>i)&1){if(Query(l,r,z-a,z-a+(1<<i)-1))ans|=(1<<i);else z|=(1<<i);}else{if(Query(l,r,z-a+(1<<i),z-a+(1<<i+1)-1))ans|=(1<<i),z|=(1<<i);}}printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的P3293-[SCOI2016]美味【主席树】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。