2021“MINIEYE杯”中国大学生算法设计超级联赛（2）1004 - I love counting trie操作好题

本文主要是介绍2021“MINIEYE杯”中国大学生算法设计超级联赛（2）1004 - I love counting trie操作好题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题意：
一个长度为\(n\)的序列，每个位置\(i\)有一个权重\(w_i\)，然后有\(Q\)个询问，每次询问包含\(l,r,a,b\)四个参数，其询问含义为区间\([l,r]\)有多少种权值\(w_i\)使得，\(w_i⊕a \le b\)。

思路：
这个题其实一看到的话找出符合特定大小关系的异或值，就会往\(trie\)树上考虑，又看到询问让我们处理的是区间内不同种类的数，也就是相同的数我们不能重复计算，这里之前也做过类似套路的题，记录一下前缀和后缀，然后查询其实就变成了询问区间\([l,r]\)内，后继节点位置\(> r\)的数有哪些，我们只统计这些数对于答案的贡献即可。
但是比赛时，一直不会处理这个区间问题，想到上可持久化\(trie\)但是苦于不会在前缀关系中维护这个贡献，故只能学习\(std\)的做法。

首先题目没要求我们带修，那么就是可以离线处理的了。
再看每个询问，看似是一个区间问题，但是考虑到\(trie\)的构造过程，每个数都会在其二进制位下被分成\(log\)份，所以每个询问的\(a,b\)其实就可以对应\(trie\)的\(log\)个节点。然后我们再把每个权值\(w_i\)对应到\(trie\)的\(log\)个节点中。这样每个节点就会保存当前节点对应的数的位置和这一二进制位上的\(0/1\)值，总个数是一定不会超过\(nlog_2^{w_i}\)的。所以我们询问\(trie\)树的所有节点，对每个节点我们暴力的更新这个节点对应的数和询问，询问完之后，再暴力的消除影响，这个区间统计和单点更新的过程我们就可以用树状数组解决，总复杂度\(O(n*log_2^{w_i}*log_2^n)\)。

下面详述一下，把一个询问挂在\(trie\)某个节点的具体过程，对于\(a,b\)的当前二进制位\(v_a,v_b\)来说。

• \(v_b= 1\)，那么如果我们去找\(v_a\)对应的相同值，它和\(v_a\)异或在一起很明显是\(=0\)的，那么不用继续向下搜了，这个位置对应的数一定是满足条件的，因为对于这一位来说\(0 < 1\)成立了，此时我们就把当前询问的信息即\(l,r,id\)存入这个节点表示，这个节点内对于这个询问来说是有合法贡献的。然后去看向另一个节点走即可。
• \(v_b = 0\)，那么我们要想小于等于它，那就一定要向和\(v_a\)相同的方向，这条分支就不涉及存入节点信息这个操作了，继续向下一位二级制走就可以了。

这样最后我们就会把一个询问最多存入\(trie\)的\(log\)个节点中，表示这些节点中的数会对这个询问产生部分的贡献，只需要最后对每个节点做一次统计，那么最后得出的就是每个询问的完整贡献。

再说区间内的不同种类数是如何保证的，这样想，对于每个\(trie\)的节点，我们存的信息既有对应权值节点\(w_i\)的信息，也有对应询问\(q_i\)的信息。我们通过排序保证询问前的插入节点均为合法即可，哪些是合法的呢，上面已经提到过，维护一个后继节点的位置，位置\(>r\)的即为合法权值。把不合法的插入值放入对应询问的后面即可，这样就保证了再离线处理每个询问的时候的正确性。

ps：这道题涉及到的处理方法和小技巧还是很巧妙的，思路也很妙，把一个询问拆成几个部分，一个个部分去做，最后加和贡献，特别的存入\(trie\)节点的操作，有助于帮助进一步理解\(trie\)

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define eb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;
const int N = 1e5 + 10;
int n,c[N],m,bit[N],ans[N];
struct node {
	int l,r,np,id;//np代表当前节点的后继节点的位置
	bool operator < (const node &u) const {
		if(np != u.np) return np > u.np;//只统计后继节点不在当前统计区间内的点
		else if(id != u.id) return id > u.id;//相等时把询问放在前面
		else return l < u.l;//只出现一次的节点 直接按大小排即可
	}
};

std::vector<node>root[N*20];
int lowbit(int x) { return x & (-x); }
void add(int p,int v) {
	while(p <= n) { bit[p] += v; p += lowbit(p); }
}
int query(int p) {
	int ans = 0;
	while(p) { ans += bit[p]; p -= lowbit(p); }
	return ans;
}
int trie[N * 20][2],tot,last[N],nxt[N];
void insert(int x,int id) {
	int p = 0;
	for(int i = 20;i >= 0;i --) {
		int v = (x >> i) & 1;
		if(!trie[p][v]) trie[p][v] = ++tot;
		p = trie[p][v];
		root[p].pb(node{id,0,nxt[id],0});
	}
}

void query(int l,int r,int x,int y,int id) {
	int p = 0;
	for(int i = 20;i >= 0;i --) {
		int v1 = (x >> i) & 1,v2 = (y >> i) & 1;
		if(v2 == 1) {
			if(trie[p][v1]) root[trie[p][v1]].pb(node{l,r,r,id});//走这边一定小对应 0 < 1 故可以提前算入答案
			p = trie[p][v1^1];
			if(!p) break;
		}
		else {
			p = trie[p][v1];
			if(!p) break;
		}
	}
	// cout << p << '\n';
	root[p].pb(node{l,r,r,id});//在结尾处添加询问
}

void solve() {
	scanf("%d",&n); 
	for(int i = 1;i <= n;i ++) {
		scanf("%d",&c[i]);
	}
	//求区间内只出现一次的数的处理时 是可以相当于前驱和后继节点的判断来处理的
	for(int i = n;i >= 1;i --) {
		if(!last[c[i]]) nxt[i] = n + 1;
		else nxt[i] = last[c[i]];
		last[c[i]] = i;
	}
	for(int i = 1;i <= n;i ++) insert(c[i],i);
	scanf("%d",&m);
	int l,r,a,b;
	for(int i = 1;i <= m;i ++) {
		scanf("%d%d%d%d",&l,&r,&a,&b);
		query(l,r,a,b,i);
	}
	// cout << tot << '\n';
	for(int i = 1;i <= tot;i ++) {
		sort(root[i].begin(),root[i].end());
		for(int j = 0;j < sz(root[i]);j ++) {
			// cout << i << " : " << root[i][j].l << ' ' << root[i][j].r << ' ' << root[i][j].np << ' ' << root[i][j].id << '\n';
			if(root[i][j].id == 0) {//代表是插入 先做插入
				add(root[i][j].l,1);
			}
			else {
				// cout << query(root[i][j].r) - query(root[i][j].l-1)
				ans[root[i][j].id] += query(root[i][j].r) - query(root[i][j].l-1);
			}
		}
		for(int j = 0;j < sz(root[i]);j ++) if(root[i][j].id == 0) add(root[i][j].l,-1);
	}
	for(int i = 1;i <= m;i ++) printf("%d\n",ans[i]);
	return ;
}

int main() {
	int T = 1;
	while(T--) {
		solve();
	}
	return 0;
}

这篇关于2021“MINIEYE杯”中国大学生算法设计超级联赛（2）1004 - I love counting trie操作好题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！