可持久化Trie (Codeforces 781 E. MinimizOR)

题目链接

Problem

定义$f\{A\}=min\{x | y,x,y\in{A}\}$

$a$为一个长度为$n$的非负整数序列，有$q$次询问，对于每次询问$(l,r)$，子序列$f\{a_l,a_{l + 1},…{a_r}\}$

Data Rang

$ 1\leq n,q\leq 2\times 10^5$

$0\leq a_i < 2^{30}$

Solution

首先不考虑时间复杂度，只构造一种可以解决问题的思想：按照二进制位进行考虑，从最高位往下分析，以最高位为0或者1可以将这些数分为两个集合$S_{i, 0},S_{i,1}$。如果$|S_{i,0}|\geq 2$，为了使与操作后的值更小，我们选择的两个数只可能来自$S_{i,0}$，于是可以舍弃$S_{i,1}$，这一位对答案产生的贡献为$0$，再向下一位迭代；如果$|S_{i,0}|<2$，则这两个数可能来自$S_{i,0}$或者$S_{i,1}$，于是我们将两个集合合为一个集合，这一位产生的贡献为$2^i$，再向下一位迭代。

从上述思路看，我们可以发现这种按照数位为$0$或$1$分集合的方式，和$01-Trie$算法很像。因为每次询问是一段子序列，所以扩展到可持久化$Trie$即可解决子序列的问题。上述思想中唯一$Trie$算法不能解决的问题就是两个集合合并，但是我们发现其中一个集合最大大小为$1$，于是我们在$Trie$插入时，把最后插入的那个数存下来，然后需要集合合并时，我们把集合大小为1的那个数直接取出，之后每次迭代时，再单独把取出的数考虑进去，因为每层最多取出一个数，最多就30个数，时间复杂度为$O(n\log^2n)$。

Code

/*************************************************************************
	> 求区间[l,r]中min{a_u|a_v}	
	> Author: Knowledge_llz
	> Mail: 925538513@qq.com 
	> Blog: https://www.cnblogs.com/Knowledge-Pig/ 
	> Created Time: 2022/4/8 23:50:47
 ************************************************************************/

#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
const int maxx = 5e5;
int n, ch[maxx * 32][2], rt[maxx], sz[maxx * 32], a[maxx * 32], b[maxx], np;
void pushup(int now, int x){
	sz[now] = sz[ch[now][0]] + sz[ch[now][1]];
	a[now] = x;
}
void insert(int pre, int &now, int i, int x){
	now = ++np;
	sz[now] = sz[pre];
	if(i < 0){
		sz[now]++;
		return;
	}
	int d = (x >> i) & 1;
	ch[now][d ^ 1] = ch[pre][d ^ 1];
	insert(ch[pre][d], ch[now][d], i - 1, x);
	pushup(now, x);
}
void cl(int now){
	sz[now] = a[now] = 0;
	if(ch[now][0]) cl(ch[now][0]);
	else if(ch[now][1]) cl(ch[now][1]);
	ch[now][0] = ch[now][1] = 0;
}
multiset<int> s;
int query(int l, int r, int i){
	if(i < 0) return 0;
	int num = sz[ch[r][0]] - sz[ch[l][0]];
	bool flag;
	if(num > 1) flag = 0; // return query(ch[l][0], cj[r][0], i - 1);
	else{
		for(auto u: s){
			int d = (u >> i) & 1;
			if(!d) ++num;
		}
		if(num > 1) flag = 0; // return query(ch[l][0], ch[r][0], i - 1);
		else{
			if(sz[ch[r][0]] - sz[ch[l][0]] > 0) s.insert(a[ch[r][0]]);
			flag = 1;
		}
	}
	if(!flag){
		queue<int> q;
		for(auto u : s){
			int d = (u >> i) & 1;
			if(d) q.push(u);
		}
		while(!q.empty()){
			if(s.count(q.front())) s.erase(q.front());
			q.pop();
		}
		return query(ch[l][0], ch[r][0], i - 1);
	}
	else return query(ch[l][1], ch[r][1], i - 1) + (1 << i);
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
#endif
	int T, Q; cin >> T;
	while(T--){
		cin >> n; np = 0;
		for(int i = 1; i <= n; ++i){
			cin >> b[i];
			insert(rt[i - 1], rt[i], 30, b[i]);
		}
		cin >> Q;
		while(Q--){
			int l, r;
			s.clear();
			cin >> l >> r;
			cout << query(rt[l - 1], rt[r], 30) << endl;
		}
		for(int i = 1; i <= n; ++i){
			cl(rt[i]);
			rt[i] = 0;
		}
	}
	return 0;
}