題目 FOTILE得到了一個(gè)長(zhǎng)為N的序列A，為了拯救地球，他希望知道某些區(qū)間內(nèi)的最大的連續(xù)XOR和。
輸入格式 第一行兩個(gè)整數(shù)N和M。
輸出格式 共M行，第i行一個(gè)正整數(shù)表示第i個(gè)詢問(wèn)的結(jié)果。
輸入樣例 3 3
1 4 3
0 1
0 1
4 3
輸出樣例 5
7
7
提示 HINT
N=12000，M=6000，x,y,Ai在signed longint范圍內(nèi)。
題解 區(qū)間異或和最大，轉(zhuǎn)化為兩個(gè)前綴和
多次詢問(wèn)不同區(qū)間，用可持久化trie樹
但每次要任意選出兩個(gè)數(shù)，而常規(guī)的trie樹只支持一個(gè)數(shù)詢問(wèn)區(qū)間和它的最大異或值，不能處理區(qū)間內(nèi)任意兩個(gè)數(shù)異或和最大值
我們不可能每次詢問(wèn)\(O(n^2logn)\) 枚舉其中一個(gè)數(shù)\(O(n^2logn)\) 預(yù)處理，\(O(1)\) 查詢
能不能均攤一下？\(f[i][j]\) 表示\(i\) 塊開頭位置到\(j\) 中所有數(shù)異或的最大值，記塊頭為\(u\) ，則\(f[i][j]\) 即為區(qū)間\([u,j]\) 的答案\(f[i][j]\) 只需要枚舉每個(gè)\(j\) 就可以了\(f[i][j] = max(f[i][j - 1],query(j，區(qū)間[u,j - 1]))\)
那么每次詢問(wèn)的時(shí)候，對(duì)于\(l\) 之后的第一個(gè)塊頭\(u\) ，可以得到出后面的答案\(f[u][r]\) \([l,u - 1]\) 的數(shù)與其后面的數(shù)的最大異或值\(\sqrt{n}\) ，所以可以直接統(tǒng)計(jì)
總的復(fù)雜度\(O(n\sqrt{n}logn)\)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long int
using namespace std;
const int maxn = 12005,Bit = 31,maxm = 6000000,INF = 100000000;
inline LL read(){LL out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}return out * flag;
}
LL n,m,A[maxn],sum[maxn],bin[40];
LL f[200][maxn],block[maxn],B,lans;
struct trie{int ch[maxm][2],sum[maxm],rt[maxn],cnt;int ins(int pre,int x){int tmp,u;tmp = u = ++cnt;for (int i = Bit; i >= 0; i--){ch[u][0] = ch[pre][0];ch[u][1] = ch[pre][1];sum[u] = sum[pre] + 1;LL t = x & bin[i]; t >>= i;pre = ch[pre][t];u = ch[u][t] = ++cnt;}sum[u] = sum[pre] + 1;return tmp;}LL query(int u,int v,int x,int dep){if (dep < 0) return 0;LL t = x & bin[dep]; t >>= dep;if (sum[ch[u][t ^ 1]] - sum[ch[v][t ^ 1]])return bin[dep] + query(ch[u][t ^ 1],ch[v][t ^ 1],x,dep - 1);return query(ch[u][t],ch[v][t],x,dep - 1);}
}T;
int main(){bin[0] = 1; for (int i = 1; i <= Bit; i++) bin[i] = bin[i - 1] << 1;n = read(); m = read(); B = (int)sqrt(n) + 1;n++;for (int i = 2; i <= n; i++) A[i] = read();for (int i = 1; i <= n; i++){sum[i] = sum[i - 1] ^ A[i];T.rt[i] = T.ins(T.rt[i - 1],sum[i]);block[i] = i / B;}for (int i = 1; i <= n; i++){if (i == 1 || block[i] != block[i - 1]){int b = block[i];for (int j = i; j <= n; j++){f[b][j] = max(f[b][j - 1],T.query(T.rt[j - 1],T.rt[i - 1],sum[j],Bit));}}}n--;LL l,r,x,y;while (m--){x = read(); y = read();l = min (((x + lans) % n) + 1, ((y + lans) % n) + 1);r = max (((x + lans) % n) + 1, ((y + lans) % n) + 1) + 1;lans = 0;if (block[l] != block[r]) lans = f[block[l] + 1][r];for (int i = l; block[i] == block[l] && i < r; i++){lans = max(lans,T.query(T.rt[r],T.rt[i],sum[i],Bit));}printf("%lld\n",lans);}return 0;
}
轉(zhuǎn)載于:https://www.cnblogs.com/Mychael/p/8711218.html
總結(jié)
以上是生活随笔 為你收集整理的BZOJ2741 【FOTILE模拟赛】L 【可持久化trie + 分块】 的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔 網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔 推薦給好友。
