本題鏈接：https://www.lydsy.com/JudgeOnline/problem.php?id=3261

題目描述

給定一個非負整數序列{a}，初始長度為N。 有M個操作，有以下兩種操作類型： 1、Ax：添加操作，表示在序列末尾添加一個數x，序列的長度N+1。 2、Q l r x：詢問操作，你需要找到一個位置p，滿足l<=p<=r，使得： a[p] xor a[p+1] xor ... xor a[N] xor x 最大，輸出最大是多少。

輸入

第一行包含兩個整數 N? ，M，含義如問題描述所示。???
第二行包含 N個非負整數，表示初始的序列 A 。?
接下來 M行，每行描述一個操作，格式如題面所述。???

輸出

假設詢問操作有 T個，則輸出應該有 T行，每行一個整數表示詢問的答案。

樣例輸入

5 5
2 6 4 3 6
A 1
Q 3 5 4
A 4
Q 5 7 0
Q 3 6 6
對于測試點 1-2，N,M<=5 。
對于測試點 3-7，N,M<=80000 。
對于測試點 8-10，N,M<=300000 。
其中測試點 1, 3, 5, 7, 9保證沒有修改操作。
0<=a[i]<=10^7。

樣例輸出

4
5
6
?

題解：

在這道題目之前，我想讀者需要一個前置知識便于理解。請看我的另一篇博客：https://www.cnblogs.com/xxzh/p/9178838.html 如果學會了這個知識的話，也就是知道了如何使用一顆01 Trie樹 那么考慮這道題，很顯然，現在我們需要維護一顆可持久化trie樹。如果不清楚靜態主席樹原理的，請移步我的另一篇博客：https://www.cnblogs.com/xxzh/p/9158819.html 正式開始對這題講解： 對于每次操作Q，它給的算式太鬼了，實際上應該化成max(?(a[n] xor x)xor a[p-1]?) p∈[l,r]; ? 對每個前置建立Trie，建立原理參考主席樹博客。 在建樹的過程中，很重要的一點就是我們每次插入的節點其實是原來a數組中的前綴。也就是說我們維護的是前綴和的前綴（有點繞讀者仔細琢磨） ? 然后注意看算式，我們每次找的其實是p-1，注意是p-1而不是p。 也就是本來我們query查找的應該是l-1到r，由于是p-1我們現在查找的是l-2到r-1 當然，對于處理p-1我們也有方法，只需要在原來的數組a之前加一個0，這樣的話就可以直接算l-1到r了 ? 具體的操作還是貪心的從高位到低位建立Trie，查詢的時候注意減一下 下面附上代碼： #include<bits/stdc++.h> using namespace std;const int maxn=6e5+15; int n,m,sz; int t[maxn<<5][2],sum[maxn<<5],b[maxn],q[maxn]; inline int read(){char ch=getchar();int s=0,f=1;while (!(ch>='0'&&ch<='9')) {if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}return s*f; } int ins(int last,int val) {int res,k;res=k=++sz;for (int i=23;i>=0;i--){sum[k]=sum[last]+1;t[k][0]=t[last][0];t[k][1]=t[last][1];bool d=val&(1<<i);k=t[k][d]=++sz;last=t[last][d];}sum[k]=sum[last]+1;return res; } int query(int k1,int k2,int val) {int res=0;for (int i=23;i>=0;i--){bool d=val&(1<<i);if (sum[t[k2][d^1]]-sum[t[k1][d^1]]>0){res|=(1<<i);k1=t[k1][d^1];k2=t[k2][d^1];}else k1=t[k1][d],k2=t[k2][d];}return res; } int main() {n=read()+1;m=read();q[1]=ins(q[0],b[1]);for (int i=2;i<=n;i++){b[i]=b[i-1]^read();//注意插入trie的是前綴和 q[i]=ins(q[i-1],b[i]);}for (int i=1;i<=m;i++){char ch=getchar();while (!(ch=='A'||ch=='Q')) ch=getchar();if (ch=='A') {++n;b[n]=b[n-1]^read();q[n]=ins(q[n-1],b[n]);}else {int l=read(),r=read(),x=read();printf("%d\n",query(q[l-1],q[r],x^b[n]));}}return 0; }

?

轉載于:https://www.cnblogs.com/xxzh/p/9188295.html

總結

以上是生活随笔為你收集整理的BZOJ3261 最大异或和 解题报告(可持久化Trie树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。