腿部挂件「NOIP多校联考 2019」

题意

给定序列以及若干询问，每次询问格式为X L R，询问区间[L,R]中与X最大的异或值。

---

思路

看到异或很容易想到01trie，由于询问[L,R]，所以需要可持久化。

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

	template<typename T>inline void read (T &x) {
		x=0;T f=1;char c=getchar();
		for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
		for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
		x*=f;
	}

	template<typename T>inline void write (T x) {
		if (x<0) putchar('-'),x*=-1;
		if (x>=10) write(x/10);
		putchar(x%10+'0');
	}

}

using namespace StandardIO;

namespace Project {
	
	const int N=200200;
	
	int n,q;
	int tot;
	int root[N];
	struct node {
		int cnt;
		int ch[2];
	} trie[N<<5];
	
	void update (int dep,int x,int &pos) {
		trie[++tot]=trie[pos],pos=tot,++trie[pos].cnt;
		if (dep==-1) return;
		update(dep-1,x,trie[pos].ch[(x>>dep)&1]);
	}
	int query (int dep,int x,int last,int cur) {
		if (dep==-1) return 0;
		int o=(x>>dep)&1;
		if (trie[trie[last].ch[o^1]].cnt<trie[trie[cur].ch[o^1]].cnt) return query(dep-1,x,trie[last].ch[o^1],trie[cur].ch[o^1])|(1<<dep);
		return query(dep-1,x,trie[last].ch[o],trie[cur].ch[o]);
	}

	inline void MAIN () {
		read(n),read(q);
		for (register int i=1,x; i<=n; ++i) {
			read(x);
			root[i]=root[i-1];
			update(31,x,root[i]);
		}
		while (q--) {
			int x,l,r;
			read(x),read(l),read(r);
			write(query(31,x,root[l],root[r+1])),putchar('
');
		}
	}
	
}

int main () {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	Project::MAIN();
}