2020-2021:teams:farmer_john:2020暑假精选题目:数据结构
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020暑假精选题目:数据结构 [2020/09/05 10:59] jjleo [题解] |
2020-2021:teams:farmer_john:2020暑假精选题目:数据结构 [2020/09/05 11:23] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 23: | 行 23: | ||
| 给定一个长度为$2^n$的序列，维护一个数据结构支持以下几种操作。\\ | 给定一个长度为$2^n$的序列，维护一个数据结构支持以下几种操作。\\ | ||
| 1.单点赋值。\\ | 1.单点赋值。\\ | ||
| - | 2.给定$k$，翻转所有$[(i-1) \cdot 2^k+1, i \cdot 2^k]$区间。\\ | + | 2.给定$k$，对于所有$i \ge 1$，翻转$[(i-1) \cdot 2^k+1, i \cdot 2^k]$区间。\\ |
| - | 3.给定$k$，将所有$[(2i-2) \cdot 2^k+1, (2i-1) \cdot 2^k]$区间和$[(2i-1) \cdot 2^k+1, 2i \cdot 2^k]$区间交换。\\ | + | 3.给定$k$，对于所有$i \ge 1$，将$[(2i-2) \cdot 2^k+1, (2i-1) \cdot 2^k]$区间和$[(2i-1) \cdot 2^k+1, 2i \cdot 2^k]$区间交换。\\ |
| 4.区间求和。\\ | 4.区间求和。\\ | ||
| $(0 \le n \le 18,1 \le q \le 10^5)$ | $(0 \le n \le 18,1 \le q \le 10^5)$ | ||
| ====题解==== | ====题解==== | ||
| - | 我们将序列从$0$开始编号，可以发现操作2和操作3分别等价于将$a_i$变为$a_{i\text{^}(2^k-1)}$和$a_{i\text{^}(2^k)}$。 | + | 我们将序列从$0$开始编号，可以发现操作2和操作3分别等价于将$a_i$变为$a_{i\text{^}(2^k-1)}$和$a_{i\text{^}(2^k)}$。因此我们可以维护一个$x$，初始值为$0$，当进行2和3操作时根据上述规律对$x$进行异或，进行1或4操作时只需将对$a_i$的操作改为对$a_{i\text{^}x}$的操作即可。这样我们只需要考虑如何维护原序列而不用考虑元素之间的交换问题。 |
| + | |||
| + | 考虑对1的操作，因为是单点赋值，我们直接将$a_{i\text{^}x}$改为对应的值即可。 | ||
| + | |||
| + | 考虑对4的操作，我们现在需要求出$$\sum_{i=l}^r a_{i\text{^}x}$$我们可以先建出一棵$[0,2^n-1]$的线段树，可以看除这棵树所有节点的对应的区间长度均为$2$的次幂。接下来将$[l,r]$类似线段树查询那样分成$O(\log n)$个区间进行查询。对于每一个区间我们可以发现都有如下性质：该区间内所有数的二进制可以表示成如下形式$$P00 \cdots 00, P00 \cdots 01, P00 \cdots 10, \ldots , P11 \cdots 11$$其中$P$是一个公共前缀，所以它们在异或$x$后也构成了一个连续的区间，设$Q$是一个前缀，为$P$这个前缀与$x$对应位异或所得，则对应的连续区间为$$Q00 \cdots 00, Q00 \cdots 01, Q00 \cdots 10, \ldots , Q11 \cdots 11$$因为后面的部分两两都不相同，由异或的性质可得它们依旧构成形如上述的序列，因此我们再开一个线段树/树状数组查询$[Q00 \cdots 00,Q11 \cdots 11]$的值即可，总复杂度$O(n \log ^2 n)$。 | ||
2020-2021/teams/farmer_john/2020暑假精选题目/数据结构.1599274784.txt.gz · 最后更改: 2020/09/05 10:59 由 jjleo
