太弱小了! 没有力量!
(又迟到了)
队友在激烈讨论签到题F, 我来了以后看榜去读题, 发现J很可做, 稍微推一下知道了是两个平均值最大子串, 印象里是二分平均值然后减去, 但是忘记接下来怎么做了. 蒋叶桢 30min 过了F, 后来又 1h2min +1 过 I, 然后我去问他, 最后想到了做法, 1h15min 过了 J. 之后蒋叶桢去玩构造了, 1h36min 过了. 之后开了B和E, B看上去是个期望, 但是平方搞不来. 我推了半天推出来一个贡献不是平方的🤣. E 也不会, 大概想到了连续区间异或同一个数之后的区间也是连续的, 没有想明白是怎么个连续法. 然后大家就下班了.
太菜了, 知识水平不足, 没人会期望数数这方面的东西; 不会思考, 关于异或的性质也不能很好地挖掘.
$n$ 个点的树, 每个点有一个区间 $[l_i, r_i]$, 同时还有边权$w_i$, 要给每个点确定一个值, 这个值要在 $[l_i, r_i]$ 之间, 同时满足和他相邻的点的值为这个值异或上邻接的边(相邻的点也要满足在他自己的区间范围内). 问有多少种情况.
$1 \le n \le 10^5, 0 \le l_i < r_i < 2^30, 0 \le w_i < 2^30$
(当时想到了某一段区间异或上同一个数还是一段连续的区间, 但是没有想明白是怎样的区间, 然后就光荣下班了.
第二天还是第三天有场cf, 就又遇到这样的问题, 连续区间异或同一个数, 然后推了挺久的, 给推出来了.)
先来看前几步思考. 首先可以发现, 两点之间的路径是唯一的, 所以任意两点都满足异或某个值的关系, 而这个值就是边上的权值异或起来. 这样这题就和树没什么关系了.
然后只要确定一个点, 那么接下来所有点都确定了. 那么一个区间里的数, 同时异或上某个值, 得到的是另一个点的取值范围限制, 这个限制当然要和本身的限制取一个交集. 如果把所有点的限制都通过其他点的限制区间异或得到的区间, 加上自己的区间, 取一个交集来找到, 那么最终每个点的取值范围, 也都满足异或的这个条件. 而每个点的取值个数都应该是相同的(否则不满足异或的这个条件). 所以我们可以把所有区间都异或到某个点, 然后做区间交, 得到的交集大小就是答案了.
(emm好像说的不是很好, 算了)
接下来手玩一下可以发现, 一个连续区间, 异或上同一个数, 得到的区间也可能是连续的. 比如 $[0, 7]$ 这个区间, 随便异或哪一个数, 得到的区间都是连续的. 为什么呢, 把他写成二进制来看:
$$
\begin{aligned}
0000 \\
0001 \\
0010 \\
0011 \\
0100 \\
0101 \\
0110 \\
0111
\end{aligned}
$$
可以发现, 这些数的前 $3$ 位(第 $0, 1, 2$ 位)恰好含有所有的情况, 即 $2^3$ 个, 第 $3$ 位以上都是一样的. 那么这些位同时异或上一个数, 得到的结果是, 这些数的前三位还是恰好所有情况. 而第 $3$ 位往上还是一样的, 所以这些数又连续了.
那么可以很容易发现, 如果从 $0$ 开始, 到某一个数 $x$, 就可以和"倍增"一样取一段区间, 这样就有 $O(\log x)$ 个区间.
举个例子, $[0, 14]$ 分成 $[0, 7], [8, 12], [13, 14]$ 这三个区间, 这三个区间异或上同一个数, 还是连续的三个区间, (可能会因为恰好连续是两个甚至一个, 但是不管怎么样一定是三个连续的区间组合).
但题目是考虑 $[l, r]$ 的区间, 这要怎么做呢? 可以先考虑 $[0, r]$ 的区间的贡献, 然后再减去 $[0, l-1]$ 的贡献.
算区间交集可以用权值线段树, 把 $[0, r]$ 异或得到的 $\log$ 个区间的位置都加 $1$, $[0, l-1]$ 异或得到的 $\log$ 个区间的位置都减 $1$. 由于不好离散化, 所以考虑动态开点. 记录最大值和最大值出现次数, 这个和第二场A差不多. 最后只需要看一下根的最大值是不是 $n$, 是的话输出次数, 不是的话输出 $0$.
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
|
struct Node {
int l, r, mid; // 不再利用完全二叉树的下标性质
int lch, rch; // 而是直接分配下标, 从而动态开点
int mx, tag, cnt; // 初始值需要满足可以在开点时赋值, 如全0
} t[MAXM]; // 预先估计一下点的个数
int idx = 0, root = -1;
/* 动态开点, 左右儿子没开, 为0; 返回新建节点标号 */
int newNode(int l, int r) {
t[++idx] = Node{l, r, (l+r)>>1, 0, 0, 0, 0, r-l+1};
return idx;
}
/* 初始化线段树, 建立一个 [1, n] 区间的节点 */
void init(int _n) {
root = newNode(1, _n);
}
/* 更新一条完整的线段 */
void updateNode(int u, int d) {
t[u].mx += d;
t[u].tag += d; //打上标记, 不再往下
}
/* 将标记下放 */
void pushDown(int u) {
if (!t[u].lch) // 第一次访问, 开点
t[u].lch = newNode(t[u].l, t[u].mid);
updateNode(t[u].lch, t[u].tag);
if (!t[u].rch)
t[u].rch = newNode(t[u].mid+1, t[u].r);
updateNode(t[u].rch, t[u].tag);
t[u].tag = 0;
}
/* 由左右儿子线段合并更新当前线段 */
void pushUp(int u) {
t[u].cnt = 0;
t[u].mx = max(t[t[u].lch].mx, t[t[u].rch].mx);
if (t[u].mx == t[t[u].lch].mx)
t[u].cnt += t[t[u].lch].cnt;
if (t[u].mx == t[t[u].rch].mx)
t[u].cnt += t[t[u].rch].cnt;
}
/* 区间修改 */
void update(int l, int r, int d, int u = -1) {
if (u == -1) u = root;
if (t[u].l == l && t[u].r == r)
updateNode(u, d); // 找到对应线段更新
else {
pushDown(u); // 访问u的儿子线段, 需要先下放标记更新
if (l > t[u].mid)
update(l, r, d, t[u].rch); //更新的线段全在该区间右边
else if (r <= t[u].mid)
update(l, r, d, t[u].lch); // 全在左边
else { // 跨越了左右两边
update(l, t[u].mid, d, t[u].lch);
update(t[u].mid+1, r, d, t[u].rch);
}
pushUp(u); // 由儿子线段的更新后的值计算当前线段值
}
}
int n, w[MAXN];
PII range[MAXN];
vector<PII> G[MAXN];
void dfs(int u, int f, int d) {
w[u] = d;
for (auto[v, x] : G[u]) if (v != f)
dfs(v, u, d ^ x);
}
vector<PII> getRange(int x, int m) {
vector<PII> res;
int p = 0;
m++;
for (int k = 30; ~k; k--) {
if (m >= (1<<k)) {
int t = p ^ x;
t = (t>>k)<<k;
res.emplace_back(t, t + (1<<k) - 1);
p += 1<<k;
m -= 1<<k;
}
}
return res;
}
void add(int x, int m, int d) {
vector<PII> rg = getRange(x, m);
for (auto[l, r] : rg)
update(l+1, r+1, d);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int l, r;
scanf("%d%d", &l, &r);
range[i] = {l, r};
}
for (int i = 1; i < n; i++) {
int u, v, x;
scanf("%d%d%d", &u, &v, &x);
G[u].emplace_back(v, x);
G[v].emplace_back(u, x);
}
dfs(1, 0, 0);
init(1<<30);
for (int i = 1; i <= n; i++) {
auto[l, r] = range[i];
add(w[i], r, 1);
if (l)
add(w[i], l-1, -1);
}
printf("%d\n", t[root].mx == n ? t[root].cnt : 0);
return 0;
}
|