題目描述

Jim是一個(gè)熱愛打游戲的小伙子，可惜他的游戲水平不太行，以至于經(jīng)常在游戲里被別人欺負(fù)。而且Jim不僅游戲玩的菜，他還很愛噴人，但是由于自己的垃圾操作，他又噴不過別人。為了改善這種局面，Jim決定成為一個(gè)腿部掛件（俗稱抱大腿）。
已知現(xiàn)在有N個(gè)選手可供Jim選擇，每位選手的能力值為 ai。N位選手不一定每位選手都有時(shí)間配Jim玩游戲而且Jim的狀態(tài)也時(shí)好時(shí)壞，所以Jim有Q個(gè)詢問，每個(gè)詢問是3個(gè)數(shù)X、L、R，求第L個(gè)人到第R個(gè)人這R-L+1個(gè)人中與Jim配合后的能力值最大是多少，Jim 與第i位選手配合后的能力值為ai與X進(jìn)行異或運(yùn)算（Xor）。

輸入

第1行：2個(gè)數(shù)N, Q中間用空格分隔，分別表示選手個(gè)數(shù)及查詢的數(shù)量(1≤N≤200000,1≤Q≤200000)。?
第2 行：共N個(gè)數(shù)為每個(gè)選手能力值中間用空格分隔，對應(yīng)ai(0≤a[i]≤10^9)。?
第N+2 - N+Q+1行：每行3個(gè)數(shù)X, L, R，中間用空格分隔。（0≤X≤10^9，0≤L≤R<N)

輸出

輸出共Q行，對應(yīng)每次詢問所能得到的最大能力值。

樣例輸入?

9 8 2 15 4 12 0 6 0 16 12 2 2 5 4 8 8 16 5 8 16 6 8 1 0 5 12 3 4 15 1 1 5 0 4

樣例輸出

14 8 28 28 14 12 0 10

提示

對于第一個(gè)詢問 2 與{4 12 0} 最大的能力值組合為 2 xor 12 = 14 注意 L R標(biāo)號(hào)從 0 開始

對于20%的數(shù)據(jù)保證 (1≤N≤5000, 1≤Q≤5000)。?
對于45%的數(shù)據(jù)保證 (1≤N≤50000, 1≤Q≤50000)。?
對于100%的數(shù)據(jù)保證 (1≤N≤200000, 1≤Q≤200000)。

---

題目大意：給出n個(gè)數(shù)，在給出m個(gè)查詢，每次查詢的形式是x,l,r，輸出在閉區(qū)間[l,r]內(nèi)與x異或后最大的結(jié)果

題目分析：這個(gè)題如果是按點(diǎn)給分制的題目，我們完全可以暴力跑過數(shù)據(jù)比較水的測試點(diǎn)，但當(dāng)n和m比較大的時(shí)候，n*n的暴力就顯然無法通過所有測試點(diǎn)了，因?yàn)橹皩W(xué)了一波如何線性查找任意兩個(gè)數(shù)異或的最大值，知道了字典樹可以處理異或最大值或最小值的問題，這個(gè)題也是那種問題的進(jìn)階版，因?yàn)樯婕暗搅藚^(qū)間，所以也就需要將字典樹可持久化，那么這個(gè)題目的正解也就是可持久化01字典樹，構(gòu)造完字典樹后對應(yīng)輸出即可，第一次接觸，掛個(gè)板子，以后若有需要再深入學(xué)習(xí)

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e5+100;int trie[N*32][2];int sum[N*32];int root[N];int cnt=1;//這里注意一定要從1開始，因?yàn)樗衪rie的初始化為0，如果第0號(hào)節(jié)點(diǎn)設(shè)上數(shù)了，會(huì)對后續(xù)節(jié)點(diǎn)產(chǎn)生影響void insert(int pre,int& cur,int step,int x) {cur=cnt++;//新建一個(gè)版本 trie[cur][0]=trie[pre][0];trie[cur][1]=trie[pre][1];//復(fù)制前一個(gè)節(jié)點(diǎn)的信息sum[cur]=sum[pre]+1;//加上當(dāng)前新建的鏈if(step<0)//x到最后一位了return;int to=(x>>step)&1;//提取出x的當(dāng)前位insert(trie[pre][to],trie[cur][to],step-1,x);//遞歸建樹 }int search(int l,int r,int step,int x) {if(step<0)return 0;int to=(x>>step)&1;if(sum[trie[r][!to]]>sum[trie[l][!to]])//說明有可以異或的這條路 return search(trie[l][!to],trie[r][!to],step-1,x)+(1<<step);elsereturn search(trie[l][to],trie[r][to],step-1,x); } int main() { // freopen("input.txt","r",stdin);int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int num;scanf("%d",&num);insert(root[i-1],root[i],30,num);}while(m--){int l,r,x;scanf("%d%d%d",&x,&l,&r);l++,r++;printf("%d\n",search(root[l-1],root[r],30,x));}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的中石油训练赛 - 腿部挂件(可持久化字典树)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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