「2017 山东三轮集训 Day6」C（0/1 Trie）

本文主要是介绍「2017 山东三轮集训 Day6」C（0/1 Trie），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

如果没有与和或的话可以用可持久化 $\ trie$ 和异或 $t a g$ 解决这个问题
考虑与和或操作
与1和或0是没有意义的，与 0 和或 1 的意义就在于把某一位全部变成 0 或 1
而某一位全部一样过后我们就可以直接记录这一位的状态
于是修改后当某一位由不一样变成完全一样的时候，我们就暴力重构 $t r i e$ 树，显然只会重构 $l o g$ 次
区间 $k$ 大和主席树一样，在 $0/1\ trie$ 上二分就可以了
复杂度 $O(nlog(A_i)^2)$
不对劲过后暴力重构的方法比较巧妙

#include<bits/stdc++.h>
#define cs const
using namespace std;
int read(){int cnt = 0, f = 1; char ch = 0;while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1; }while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar();return cnt * f;
}
cs int N = 5e4 + 50, M = 32;
int n, m, a[N];
int same[M], tag[M], Xor;
namespace T{cs int N = ::N * 32;int nd, rt[N], ch[N][2], sz[N];void clear(){memset(sz,0,sizeof(int)*(nd+1));memset(ch,0,sizeof(int)*(nd+1)*2);nd=rt[0]=0;}void ins(int las, int &x, int v, int i){x=++nd; sz[x] = sz[las]+1; if(i<0) return;int c=same[i]?0:((v>>i)&1); ch[x][c^1]=ch[las][c^1];ins(ch[las][c],ch[x][c],v,i-1);}int query(int a, int b, int k, int i){if(i<0) return 0;if(same[i]) return query(ch[a][0],ch[b][0],k,i-1)+(tag[i]<<i);else{int c=Xor>>i&1;int sm=sz[ch[b][c]]-sz[ch[a][c]];if(k<=sm) return query(ch[a][c],ch[b][c],k,i-1);else return query(ch[a][c^1],ch[b][c^1],k-sm,i-1)+(1<<i);} }void build(){clear();for(int i=1; i<=n; i++)ins(rt[i-1],rt[i],a[i],30);}
}
int main(){n = read(), m = read();unsigned int And=-1, Or=0; for(int i=1; i<=n; i++) a[i]=read(), And=And&a[i], Or=Or|a[i];for(int i=0; i<=30; i++) same[i]=((And>>i)==(Or>>i));T::build();while(m--){char op[5]; scanf("%s", op);if(op[1]=='o'){int x = read(); Xor ^= x;for(int i=0; i<=30; i++) if(same[i]&&(x>>i&1)) tag[i]^=1;}if(op[1]=='n'){int x = read(); bool FLAG = false;for(int i=0; i<=30; i++)if(!(x&(1<<i))){if(same[i]) tag[i] = 0;else{ FLAG=true; same[i]=1; tag[i]=0; }} if(FLAG) T::build();}if(op[1]=='r'){int x = read();bool FLAG = false;for(int i=0; i<=30; i++)if(x&(1<<i)){if(same[i]) tag[i] = 1; else{ FLAG=true; same[i]=1; tag[i]=1; }} if(FLAG) T::build();}if(op[1]=='s'){int l=read(),r=read(),k=read();cout << T::query(T::rt[l-1],T::rt[r],k,30) << '\n';}} return 0;
}