数据结构 2021 小作业 5 Hint

[wennitao]

数据结构 $2021$ 小作业 $5$ Hint

1143

将点按$x$为第一关键字，$y$为第二关键字排序。用树状数组统计即可。

（注意题意问题，位于同一位置的战壕不能互相保护）

1121

将边上的权值转化为点上的权值（如赋在较深的点上）。

按LCA的倍增预处理方式即可。（$val[u][k]$表示节点$u$到其$2^k$祖先路径上的异或和）

1145

经典区间RMQ。ST表即可。（倍增）

1146

按二叉搜索树模拟即可。

1147

正经做法应该是树hash。

直接维护每棵子树的hash值即可（同时计算左中右和右中左两种顺序的hash值）。

（实际上暴力也能过（可以思考一下暴力的复杂度）

1148

hash后暴力二分答案即可。

1149

很显然每次选中的值比之前选过的值都要大时才会对答案造成影响。因此考虑如何维护位置与值的对应关系。

考虑维护已经被排过序的值的位置。

不妨假设$v$是$n$的一个排列。

假设$1 \dots i$已经被排好序，现在要计算将$1 \dots i + 1$排好序后的答案。

将$i + 1$加入，对答案的贡献是$1 \dots i$中位置在$i + 1$位置右侧的个数。

因此用树状数组维护哪些位置已经被排过序即可。

（实际情况$v_i \le 10^9$，需要离散化）

1150

可以将题意转化为：

给定一棵树，每条边初始权值都为$1$。询问分为以下三种

1. $p$到$q$路径上的权值和是否等于路径长度
2. 将$p$和$q$之间的边的权值设为$0$
3. 将$p$和$q$之间的边的权值设为$1$

将边的权值变为点的权值后，树链剖分即可。

1151

按位置下标为关键字建平衡树。

注意区间覆盖和区间加等差数列lazy tag的pushdown。