【线段树维护区间覆盖】2021牛客暑期多校训练营4 E Tree Xor
2021-08-27 15:30:00 # ACM

题链

题目解析

给定 $n$ 个节点的树，每个节点有取值区间 $[L,R]$，每条边都有一个权值 $w$，表示 $u,v$ 异或值为 $w$，询问有多少种构造方式；

首先确定了一个点的值，那么整棵树的各个点的权值就确定了，不妨以 $1$ 号点为根，计算出根节点到其他点路径异或和 $d_i$，如果根节点取 $a$，那么其他点的值 $d_i$ 都要异或上 $a$；

问题变为求合法 $a$ 的数量；

一个区间的值都异或上同一个值，会得到若干个连续区间，可以通过每个点的取值区间异或上 $d_i$ 得到对根节点的种种约束条件，那么可以用线段树的递归结构 (在 $[0,2^{30}-1]$ 上划分) 将点 $i$ 的取值区间划分为若干个小区间，这样若干个小区间异或上同一值都能得到一个个连续的区间，这些就是对根节点的约束条件，在权值线段树上做覆盖，最后查找被覆盖 $n$ 次的有多少个值就是答案了；

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include<bits/stdc++.h>
using namespace std;
#define LL long long 
#define ls rt<<1
#define rs rt<<1|1
#define eps 1e-8
#define mod 1000000007
#define MAXN (1<<30)-1
#define MS 100009

int n,m;
struct node{//
	int l,r;// 
}c[MS]; 	// 每个节点的取值区间 

struct nod{			//
	int poi,val;	//
};					//
vector<nod > vc[MS];// 存图以及边权val 

struct tree{	// 权值线段树 
	int l,r,val;//
}p[MS<<6];		//
int tot;		// tot  用于动态开点 
int root;		// root 根节点 

int d[MS]; // 点 1=>i 的路径异或和 

// bfs => d[]: bfs 得到 d[] 数组 
// vis 表示点 i 是否被访问 
int vis[MS];
queue<nod > Q;
void bfs(){
	Q.push({1,0});
	vis[1] = 1;
	while(!Q.empty()){
		nod t = Q.front();
		Q.pop();
		d[t.poi] = t.val;
		for(auto nb:vc[t.poi]){
			if(!vis[nb.poi]){
				vis[nb.poi] = 1;
				Q.push({nb.poi, t.val^nb.val});
			}
		}
	}
}

// 区间覆盖 
void modify(int L,int R,int l,int r,int &rt){
	if(!rt) rt = ++tot;
	if(L <= l && r <= R){
		p[rt].val++;
		return;
	}
	int m = l+r>>1;
	if(m >= L) modify(L,R,l,m,p[rt].l);
	if(m <  R) modify(L,R,m+1,r,p[rt].r);
}

// 查找权值线段树, 寻找覆盖次数为 n 的区间 
int get_sum(int l,int r,int rt,int cnt){
	cnt += p[rt].val;
	if(cnt == n){
		return (r-l+1);
	}
	int m = l+r>>1;
	int ans = 0;
	if(p[rt].l) ans += get_sum(l,m,p[rt].l,cnt);
	if(p[rt].r) ans += get_sum(m+1,r,p[rt].r,cnt);
	return ans;
}

// 将区间 [l,r] ^ val => [L,R]; 
void cal(int l,int r,int val){
	/*	方式: 
		 	1.在区间[l,r]中寻找一个值, 使得 num^val 最小
			2.按位分类讨论, 枚举第i位:
				如果l的第i位 和 R的第i位相同, 则num的第i位只能与lr的相同
				否则就到了第i位可以0/1任选的地方了, 往后与val的第i位相同即可
			3.[L,R]的区间长度与[l,r]相同, L = num^val 
	*/
	
	int t = ( ~(l^r) ) & ( (1ll<<31)-1 ); 
	int L = l ^ (t&val);
	int R = L + (r-l);
//	cout << "[" << L << "," << R << "] ";
	// 在权值线段树上覆盖[L,R]区间 
	modify(L,R,0,MAXN,root);
}

// 将[L,R]划分为多个连续的区间 [l1,r1],[l2,r2]...[ln,rn]; 
// 使得 [li,ri]^val 都能得到一段连续的区间 
// [l,r] 有这样的性质:
// 		l的前 k位与r相同, 后 31-k 位取值范围为 00..0 ~ 11..1 
// 线段树的划分方式很合适 
void divide(int L,int R,int l,int r,int val){
	if(L <= l && r <= R){
//		cout << "[" << l << "," << r << "] ^ " << val << " = ";
		cal(l, r, val);
//		cout << "\n";
		return;
	}
	int m = l+r>>1;
	if(m >= L) divide(L,R,l,m,val);
	if(m <  R) divide(L,R,m+1,r,val);
}

int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i=1;i<=n;i++){
		int l,r;
		cin >> l >> r;
		c[i] = {l,r};
	}
	for(int i=2;i<=n;i++){
		int u,v,val;
		cin >> u >> v >> val;
		vc[u].push_back({v,val});
		vc[v].push_back({u,val});
	}
	bfs();
	
//	for(int i=1;i<=n;i++){
//		cout << d[i] << " ";
//	}
//	cout << "\n";
	
	for(int i=1;i<=n;i++){
//		cout << "poi = " << i << "\n";
//		cout << "[" << c[i].l << "," << c[i].r << "] : \n";
		divide(c[i].l, c[i].r, 0, MAXN, d[i]);
//		cout << "\n\n";
	}
	int ans = get_sum(0, MAXN,root, 0);
	cout << ans << "\n";
	
	
	
	
	
	return 0;
}
Prev
2021-08-27 15:30:00 # ACM
Next