2020-2021:teams:farmer_john:2020暑假精选题目:数据结构
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020暑假精选题目:数据结构 [2020/09/04 10:41] jjleo |
2020-2021:teams:farmer_john:2020暑假精选题目:数据结构 [2020/09/05 11:23] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| 给定长度为$n$的序列，$q$次询问在$[l,r]$中最多能选多少数满足同一个数的出现次数不超过$k$，强制在线。$(n,q,k \le 10^5)$ | 给定长度为$n$的序列，$q$次询问在$[l,r]$中最多能选多少数满足同一个数的出现次数不超过$k$，强制在线。$(n,q,k \le 10^5)$ | ||
| ====题解==== | ====题解==== | ||
| + | 设$a_i$为第$i$个数后面第$k$个相同的数的下标，如果没有则为$n+1$。所求转化为$[l,r]$区间内有多少$a_i>r$，主席树维护即可。 | ||
| + | |||
| + | =====CF895E===== | ||
| + | ====题意==== | ||
| + | 给定一个长度为 $n$ 的数列，每次选择两个不相交区间，在两个区间中各任意选择一个数，交换两个数的位置，每次询问询问一个区间的和的期望。 | ||
| + | ====题解==== | ||
| + | 考虑左侧区间长度为 $L_1$, 右侧区间长度为 $L_2$ ,左侧区间期望和为 $E(L_1)$ ，则删除一个数之后的期望和应为 $\frac{(L_1 - 1)E(L_1)}{L_1}$，考虑右侧选择一个数 $a_i$ 对左侧区间的贡献为 $\frac{\sum_{i \in L_2} a_i}{L_2} = \frac{E(L_2)}{L_2}$ ,考虑对于左侧子区间的影响，应该考虑对左侧区间每个位置的贡献为 $\frac{E(L_2)}{L_2 L_1}$ 即可，线段树区间加区间乘维护即可。 | ||
| + | |||
| + | =====CF1401F===== | ||
| + | ====题意==== | ||
| + | 给定一个长度为$2^n$的序列，维护一个数据结构支持以下几种操作。\\ | ||
| + | 1.单点赋值。\\ | ||
| + | 2.给定$k$，对于所有$i \ge 1$，翻转$[(i-1) \cdot 2^k+1, i \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.区间求和。\\ | ||
| + | $(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)}$。因此我们可以维护一个$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暑假精选题目/数据结构.1599187291.txt.gz · 最后更改: 2020/09/04 10:41 由 jjleo
