loj6144「2017 山东三轮集训 Day6」C

loj6144「2017 山东三轮集训 Day6」C

注意到修改只有位运算，容易想到将位拆开考虑。首先可以发现对某一位或上 (0) 或者是对某一位与上 (1) 是没有意义的，相当于没有操作。

如果修改只有异或，那么只需要对每一位维护一个是否翻转的标记，然后建出可持久化 ( ext{trie})，查询的时候只需要找到每一位值为 (0) 的子树（如果有标记就是 (1)，否则就是 (0)）检查子树大小是否超过 (k)，如果超过 (k) 就向 (0) 子树走，否则向 (1) 子树走即可。

接下来考虑与 (0) 操作和或 (1) 操作，实际上将所有数的这一位都变成了相同的数。那么接下来只需要直接大力维护这一位是什么，二分的时候不考虑这一位即可。具体地，由于最多会有 (log w) 次操作会使得至少一位变成相同的数，所以每次将某一位变成相同的数时直接暴力重构可持久化 ( ext{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("
",query(rt[x-1],rt[y],k));
		if(flag) build();
	}
	return 0;
}