Codeforces Round 781 (Div. 2) E. MinimizOR （可持久化字典树）

传送门

题目大意：

  T组测试数据每组测试数据先输入一个n表示有一个长度为n的一维数组，然后输入n个数字表示这个一维数组。紧接着输入一个k表示有k个询问，对于每个询问会输入一个l和一个r表示询问数组中[l, r]这个区间里面任意两个下标不重复的元素最小的或(|)是多少。

解题思路：

  我们可以贪心的去考虑，如果高位为0一定是最优的。考虑可持久化字典树贪心，从高位往低位尽心贪心，如果[l, r]这个区间里面第x位的代表0这颗子树的大小大于等于2就可以直接往左走最优，若不是的话我们选择直接往右走，此时我们左子树大小最大为1，若为1我们用两个数组rx和ry记录root[l - 1]和root[r]这两个版本此时往左走的编号。因为每走一步最多有一个分支，所以一次查询的时间复杂度最坏为30 * 30。可以通过此题。

#include <bits/stdc++.h>

const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using ll = long long;
typedef std::pair<int, int> PII;
using namespace std;

int n, m;

const int N = 1e5 + 10, M = 3e5 + 10;
struct Persistent_Tire{
	int ch[M * 31][2], ver[M  * 31], root[M * 31], idx, sz[M * 31];
	int sigma;
	int rx[N], ry[N];
	
	inline void Init(){
		ver[0] = -1;//边界
		idx = 0;
		sigma = 30;//位数
		ins(root[0], 0, 0, 0);//边界
	}
	
	//当前版本的root，上个版本的root，值， 当前版本的编号
    inline void ins(int &xx, int o, int v, int pos) {
        sz[xx = ++ idx] = sz[o] + 1;
		ver[idx] = pos;
        for(int d = sigma, c, x = xx; d >= 0; d --){
        	c = (v >> d) & 1;
        	ch[x][c ^ 1] = ch[o][c ^ 1];
        	sz[x = ch[x][c] = ++ idx] = sz[o = ch[o][c]] + 1;
        	ver[idx] = pos;
        }
    }
	
	inline int query(int x, int y, int d) {
		if (d < 0) return 0;
		int lsz = sz[ch[y][0]] - sz[ch[x][0]];
		//std::cout << d << ' ' << lsz << '\n';
		for (int i = 1; i <= m; i ++) 
			lsz += sz[ch[ry[i]][0]] - sz[ch[rx[i]][0]];
		
		if (lsz >= 2) {
			for (int i = 1; i <= m; i ++) {
				ry[i] = ch[ry[i]][0];
				rx[i] = ch[rx[i]][0];
			}
			
			return query(ch[x][0], ch[y][0], d - 1);
		} else {
			for (int i = 1; i <= m; i ++) {
				if (sz[ch[ry[i]][0]] - sz[ch[rx[i]][0]]) {
					ry[i] = ch[ry[i]][0];
					rx[i] = ch[rx[i]][0];
				} else {
					ry[i] = ch[ry[i]][1];
					rx[i] = ch[rx[i]][1];
				}
			}
			
			if (sz[ch[y][0]] - sz[ch[x][0]]) {
				rx[++ m] = ch[x][0];
				ry[m] = ch[y][0];
			}
			
			return (1 << d) + query(ch[x][1], ch[y][1], d - 1);
		}
	}
	
}HT;


inline void solve() {
	HT.Init();
	std::cin >> n;
	
	auto &root = HT.root;
	for (int i = 1, x; i <= n; i ++) {
		std::cin >> x;
		HT.ins(root[i], root[i - 1], x, i);
	}
	
	std::cin >> n;
	
	for (int i = 1; i <= n; i ++) {
		int l, r;
		std::cin >> l >> r;
		m = 0;
		std::cout << HT.query(root[l - 1], root[r], 30) << '\n';
	}
}


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    
    int _ = 1;
    std::cin >> _;
    while (_ --) solve();
    
    return 0;
}