loj6144「2017 山东三轮集训 Day6」C
注意到修改只有位运算，容易想到将位拆开考虑。首先可以发现对某一位或上 \(0\) 或者是对某一位与上 \(1\) 是没有意义的，相当于没有操作。
如果修改只有异或，那么只需要对每一位维护一个是否翻转的标记，然后建出可持久化 \(\text{trie}\)，查询的时候只需要找到每一位值为 \(0\) 的子树（如果有标记就是 \(1\)，否则就是 \(0\)）检查子树大小是否超过 \(k\)，如果超过 \(k\) 就向 \(0\) 子树走，否则向 \(1\) 子树走即可。
接下来考虑与 \(0\) 操作和或 \(1\) 操作，实际上将所有数的这一位都变成了相同的数。那么接下来只需要直接大力维护这一位是什么，二分的时候不考虑这一位即可。具体地，由于最多会有 \(\log w\) 次操作会使得至少一位变成相同的数，所以每次将某一位变成相同的数时直接暴力重构可持久化 \(\text{trie}\)。为了方便，可以将已经全都相同的位默认设为 \(0\)，然后用另一个变量存储这些位的值，最后直接加上即可。
时间复杂度 \(\mathcal{O}(n \log^2 w)\)。
code
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T>inline bool read(T &x){
x=0;
char ch=getchar();
bool flag=0,ret=0;
while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(),ret=1;
x=flag?-x:x;
return ret;
}
template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
return read(a)&&read(args...);
}
template<typename T>void prt(T x){
if(x>9) prt(x/10);
putchar(x%10+'0');
}
template<typename T>inline void put(T x){
if(x<0) putchar('-'),x=-x;
prt(x);
}
template<typename T>inline void put(char ch,T x){
if(x<0) putchar('-'),x=-x;
prt(x);
putchar(ch);
}
template<typename T,typename ...Args>inline void put(T a,Args ...args){
put(a);
put(args...);
}
template<typename T,typename ...Args>inline void put(const char ch,T a,Args ...args){
put(ch,a);
put(ch,args...);
}
inline void put(string s){
for(int i=0,sz=s.length();i<sz;i++) putchar(s[i]);
}
inline void put(const char* s){
for(int i=0,sz=strlen(s);i<sz;i++) putchar(s[i]);
}
}
using namespace IO;
#define N 50005
#define M 3200005
#define K 31
#define int unsigned
int n,m,w[N],rt[N],trie[M][2],siz[M],idx;
int vis,rev,tag;
inline void insert(int x,int y,int val){
if(!rt[x]) rt[x]=++idx;
x=rt[x],y=rt[y];
siz[x]=siz[y]+1;
for(int i=K;~i;i--){
int c=val>>i&1;
if(vis>>i&1) c=0;
trie[x][c^1]=trie[y][c^1];
trie[x][c]=++idx;
x=trie[x][c],y=trie[y][c];
siz[x]=siz[y]+1;
}
}
inline int query(int x,int y,int k){
int res=0;
for(int i=K;~i;i--){
if(vis>>i&1){
res|=tag&(1u<<i);
x=trie[x][0],y=trie[y][0];
continue;
}
int c=rev>>i&1;
int lsiz=siz[trie[y][c]]-siz[trie[x][c]];
if(lsiz<k) res|=1u<<i,c^=1,k-=lsiz;
x=trie[x][c],y=trie[y][c];
}
return res;
}
inline void build(){
memset(rt,0,sizeof(rt));
memset(trie,0,sizeof(trie));
memset(siz,0,sizeof(siz));
idx=0;
for(int i=1;i<=n;i++) insert(i,i-1,w[i]^=rev);
rev=0;
}
char s[6];
signed main(){
read(n,m);
for(int i=1;i<=n;i++) read(w[i]);
build();
for(int i=1,x,y,k;i<=m;i++){
scanf("%s",s),read(x);
bool flag=0;
if(s[1]=='o') rev^=x,tag^=x;
else if(s[1]=='n'){
tag&=x;
for(int j=0;j<=K;j++)
if(!(x>>j&1)){
if(!(vis>>j&1)) vis|=1u<<j,flag=1;
rev-=rev&(1u<<j);
}
}else if(s[1]=='r'){
tag|=x;
for(int j=0;j<=K;j++)
if(x>>j&1){
if(!(vis>>j&1)) vis|=1u<<j,flag=1;
rev|=1u<<j;
}
}else read(y,k),put('\n',query(rt[x-1],rt[y],k));
if(flag) build();
}
return 0;
}