[CC-MINXOR]XOR Minimization

题目大意：

有一个长度为\(n\)的数列\(A_{1\sim n}\)。\(q\)次操作，操作包含以下两种：

询问\(A_{l\sim r}\)中最小值及其出现次数；
将\(A_{l\sim r}\)中每个数字异或上\(k\)。

\(n\le250,000;q\le50,000;0\le A_i,k<2^{16}\)

思路：

分块+字典树

源代码：

#include<cmath>

#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=250000,B=500,K=1<<16;

int n,a[N],tag[B],bel[N],beg[B],end[B];

struct Node {

	int val,cnt;

};

class Trie {

	private:

		int val[K<<1];

	public:

		void reset() {

			memset(val,0,sizeof val);

		}

		void insert(const int &x) {

			for(register int i=15,p=1;i>=0;i--) {

				p=p<<1|((x>>i)&1);

				val[p]++;

			}

		}

		Node query(const int &x) const {

			int p=1,ret=0;

			for(register int i=15;i>=0;i--) {

				p<<=1;

				if(val[p|((x>>i)&1)]) {

					p|=(x>>i)&1;

				} else {

					ret|=1<<i;

					p|=((x>>i)&1)^1;

				}

			}

			return (Node){ret,val[p]};

		}

};

Trie t[B];

inline void rebuild(const int &k) {

	t[k].reset();

	for(register int i=beg[k];i<=end[k];i++) {

		t[k].insert(a[i]);

	}

}

inline void modify(const int &l,const int &r,const int &k) {

	if(bel[l]==bel[r]) {

		for(register int i=beg[bel[l]];i<=end[bel[l]];i++) {

			a[i]^=tag[bel[l]];

		}

		tag[bel[l]]=0;

		for(register int i=l;i<=r;i++) {

			a[i]^=k;

		}

		rebuild(bel[l]);

		return;

	}

	for(register int i=beg[bel[l]];i<=end[bel[l]];i++) {

		a[i]^=tag[bel[l]];

	}

	tag[bel[l]]=0;

	for(register int i=l;i<=end[bel[l]];i++) {

		a[i]^=k;

	}

	rebuild(bel[l]);

	for(register int i=bel[l]+1;i<bel[r];i++) {

		tag[i]^=k;

	}

	for(register int i=beg[bel[r]];i<=end[bel[r]];i++) {

		a[i]^=tag[bel[r]];

	}

	tag[bel[r]]=0;

	for(register int i=beg[bel[r]];i<=r;i++) {

		a[i]^=k;

	}

	rebuild(bel[r]);

}

inline Node query(const int &l,const int &r) {

	Node ans=(Node){K,0};

	if(bel[l]==bel[r]) {

		for(register int i=l;i<=r;i++) {

			if((a[i]^tag[bel[i]])<ans.val) {

				ans=(Node){a[i]^tag[bel[i]],0};

			}

			if((a[i]^tag[bel[i]])==ans.val) {

				ans.cnt++;

			}

		}

		return ans;

	}

	for(register int i=l;i<=end[bel[l]];i++) {

		if((a[i]^tag[bel[i]])<ans.val) {

			ans=(Node){a[i]^tag[bel[i]],0};

		}

		if((a[i]^tag[bel[i]])==ans.val) {

			ans.cnt++;

		}

	}

	for(register int i=bel[l]+1;i<bel[r];i++) {

		const Node tmp=t[i].query(tag[i]);

		if(tmp.val<ans.val) {

			ans=(Node){tmp.val,0};

		}

		if(tmp.val==ans.val) {

			ans.cnt+=tmp.cnt;

		}

	}

	for(register int i=beg[bel[r]];i<=r;i++) {

		if((a[i]^tag[bel[i]])<ans.val) {

			ans=(Node){a[i]^tag[bel[i]],0};

		}

		if((a[i]^tag[bel[i]])==ans.val) {

			ans.cnt++;

		}

	}

	return ans;

}

int main() {

	n=getint();

	const int q=getint(),block=sqrt(n);

	for(register int i=0;i<n;i++) {

		bel[i]=i/block;

		a[i]=getint();

		t[bel[i]].insert(a[i]);

		if(i&&bel[i]!=bel[i-1]) {

			beg[bel[i]]=i;

		}

		end[bel[i]]=i;

	}

	for(register int i=0;i<q;i++) {

		const int opt=getint(),l=getint()-1,r=getint()-1;

		if(opt==1) {

			const Node ans=query(l,r);

			printf("%d %d\n",ans.val,ans.cnt);

		}

		if(opt==2) {

			modify(l,r,getint());

		}

	}

	return 0;

}

巴特西

[CC-MINXOR]XOR Minimization

[CC-MINXOR]XOR Minimization

题目大意：

思路：

源代码：

最新文章

热门文章