咕了两天的内容
和主席树的思想差不多，当前节点有的边就往下连，没有的边就连到之前的trie上
最大异或和：https://www.luogu.org/problem/P4735
处理前缀异或和，则问题为求p在[l - 1,r - 1]内，s[p] ^ (s[n] ^ x)的最大值
考虑到右边是定值，转化为求区间内异或定值的最大值，可持久化Trie板子
细节看代码
// luogu-judger-enable-o2 #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<queue> #include<map> using namespace std; typedef long long ll; typedef double db; #define llinf 9000000000000000000LL #define B cout << "breakpoint" << endl; #define O(x) cout << #x << " " << x << endl; inline int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op; } const int maxn = 6e5 + 5; int sum[maxn],tot; int ch[maxn * 27][2],cnt[maxn * 27],rt[maxn]; void insert(int a,int b,int t,int x) { if(t < 0) return; int i = (x >> t) & 1; ch[a][!i] = ch[b][!i]; ch[a][i] = ++tot; cnt[ch[a][i]] = cnt[ch[b][i]] + 1; insert(ch[a][i],ch[b][i],t - 1,x); } int query(int a,int b,int t,int x) { if(t < 0) return 0; int i = (x >> t) & 1; if(cnt[ch[b][!i]] - cnt[ch[a][!i]] > 0) return (1 << t) + query(ch[a][!i],ch[b][!i],t - 1,x); else return query(ch[a][i],ch[b][i],t - 1,x); } int n,m; int main() { char op[5]; int x,l,r; n = read(),m = read(); rt[0] = ++tot; insert(rt[0],0,25,0); for(int i = 1;i <= n;i++) { x = read(); sum[i] = sum[i - 1] ^ x; rt[i] = ++tot; insert(rt[i],rt[i - 1],25,sum[i]); } while(m--) { scanf("%s",op); if(op[0] == 'A') { x = read(); n++; sum[n] = sum[n - 1] ^ x; rt[n] = ++tot; insert(rt[n],rt[n - 1],25,sum[n]); } else { l = read(),r = read(),x = read(); l--,r--; if(l == 0) printf("%d ",query(0,rt[r],25,x ^ sum[n])); else printf("%d ",query(rt[l - 1],rt[r],25,x ^ sum[n])); } } }
异或粽子：https://www.luogu.org/problem/P5283
时隔好久2333
依旧套路处理前缀异或和，然后考虑固定右端点求出每个右端点最大值，放入堆中
维护一个堆，每次把当前K大值取出来，加入答案，再向堆中扔入K+1大值
如何求区间内异或定值的K大值也是板子，细节在代码
// luogu-judger-enable-o2 #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<queue> #include<map> using namespace std; typedef long long ll; typedef int mainint; #define int long long typedef double db; #define pii pair<int,int> #define mp make_pair #define llinf 9000000000000000000LL #define B cout << "breakpoint" << endl; #define O(x) cout << #x << " " << x << endl; inline int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op; } const int maxn = 6e5 + 5; int sum[maxn],tot; int ch[maxn * 40][2],cnt[maxn * 40],rt[maxn],num[maxn]; int n,k; void insert(int a,int b,int t,int x) { if(t < 0) return; int i = (x >> t) & 1; ch[a][!i] = ch[b][!i]; ch[a][i] = ++tot; cnt[ch[a][i]] = cnt[ch[b][i]] + 1; insert(ch[a][i],ch[b][i],t - 1,x); } int query(int a,int b,int t,int x,int num) { if(t < 0) return 0; int i = (x >> t) & 1; int tp = cnt[ch[b][!i]] - cnt[ch[a][!i]]; if(tp >= num) return (1ll << t) + query(ch[a][!i],ch[b][!i],t - 1,x,num); else return query(ch[a][i],ch[b][i],t - 1,x,num - tp); } mainint main() { ll ans = 0; n = read(),k = read(); rt[0] = ++tot; insert(rt[0],0,34,0); for(int i = 1;i <= n;i++) { int x = read(); sum[i] = sum[i - 1] ^ x; rt[i] = ++tot; insert(rt[i],rt[i - 1],34,sum[i]); num[i] = 1; } priority_queue<pii> q; for(int i = 1;i <= n;i++) q.push(mp(query(0,rt[i - 1],34,sum[i],num[i]),i)); for(int i = 1;i <= k;i++) { int u = q.top().second; ans += q.top().first; q.pop(); num[u]++; q.push(mp(query(0,rt[u - 1],34,sum[u],num[u]),u)); } printf("%lld",ans); }