Problem

题目传送门

给一个序列\(\{ a\}\)，长度为n.

有m个操作.

1.在序列末尾添加一个x.

2.找到一个\(p∈[l,r]\)，使得\(a[p]⊕a[p+1]⊕...⊕a[N]⊕x\)最大，其中N为序列的长度。

Solution

记\(all\)为\(a[1]⊕a[2]⊕a[3]...⊕a[N]\)

询问即为找到一个\(p∈[l,r]\) 使得\(a[1]⊕a[2]⊕a[3]...⊕a[p]⊕all⊕x\)最大。

所以，我们只需要维护序列\(\{a\}\)的前缀异或和即可。

这里引出了一个算法：

可持久化Trie

听起来十分高大上。

其实就是用一颗01Trie维护每一位的出现次数。

和可持久化主席树的实现差不多。

网上的板子都过于优秀（神仙）

受到右边大佬启发后,开始研究如何像写主席树一样写可持久化Trie.

个人感觉很好理解。

Code

#include <bits/stdc++.h> using namespace std; #define DEBUG(...) fprintf(stderr, __VA_ARGS__) #define mp make_pair #define fst first #define snd second template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } inline int read(){ int res = 0, fl = 1; char r = getchar(); for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1; for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48; return res * fl; } typedef long long LL; typedef pair<int, int> pii; int INF = (1 << 25) - 1; const int Maxn = 3e5 + 10, Log = 25; struct SGT{ int ls, rs, sum; }tre[Maxn << 6]; int cnt, p[Maxn << 1], Pow[30], root[Maxn << 1]; void build(int &rt, int grt,int pos, int T){ tre[rt = ++cnt] = tre[grt]; tre[rt].sum++; if(T < 0) return; if(!(pos & Pow[T])) build(tre[rt].ls, tre[grt].ls, pos, T - 1); else build(tre[rt].rs, tre[grt].rs, pos, T - 1); } int Query(int a, int b, int pos, int T){ if(T < 0) return 0; bool l = (tre[tre[b].ls].sum - tre[tre[a].ls].sum > 0); bool r = (tre[tre[b].rs].sum - tre[tre[a].rs].sum > 0); bool now = (pos & Pow[T]) > 0; if(!r) return (now) * Pow[T] + Query(tre[a].ls, tre[b].ls, pos, T - 1); if(!l) return (!now) * Pow[T] + Query(tre[a].rs, tre[b].rs, pos, T - 1); //一边没有数，显然只能往另一边走。 if(now) return Pow[T] + Query(tre[a].ls, tre[b].ls, pos, T - 1); return Pow[T] + Query(tre[a].rs, tre[b].rs, pos, T - 1); //贪心过程，因为位数高具有绝对优势。 } void init(int n){ p[0] = 0, Pow[0] = 1; build(root[0], 0, 0, Log); for (int i = 1; i <= Log; ++i) Pow[i] = Pow[i - 1] << 1; for (int i = 1; i <= n; ++i){ p[i] = read() ^ p[i - 1]; build(root[i], root[i - 1], p[i - 1], Log); } } int main() { #ifndef ONLINE_JUDGE freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); #endif int n = read(), m = read(); init(n); int num = n; while(m--){ char opt = getchar(); while(opt != 'A' && opt != 'Q') opt = getchar(); if(opt == 'A') { ++num,p[num] = p[num - 1] ^ read(); build(root[num],root[num - 1], p[num - 1], Log); } else { int l = read(), r = read(), x = read(); printf("%d\n",Query(root[l - 1], root[r], x ^ p[num], Log)); } } return 0; }

转载于:https://www.cnblogs.com/LZYcaiji/p/10397861.html