数据结构杂题精选

~~你们不会真的要我讲分块吧~~ 随便理一理不错的题目 难度较低，题目都比较 **基础** ## 信心题、[CF785E Anton and permutation](https://www.luogu.com.cn/problem/CF785E) ### 简要题意 一个操作 1. 交换 $(a_x, a_y)$ （其实可以看做单点修改） 每次修改后输出全局逆序对数量 ### 限制 $1 \le n, m\le 10^5, 1\le a_i, x \le 10^9$ 。 顺便考虑一下 **线性空间，强制在线** 怎么做。 ## 0、[P7446 [Ynoi2007] rfplca](https://www.luogu.com.cn/problem/P7446) ### 简要题意 给你一棵以 $1$ 为根的有根树，用一个序列表示， $a_i$ 为 $i$ 的父亲结点。 两个操作 1. 区间中 $a_i\leftarrow \max\{a_i-x, 1\}$ 2. 求 $u, v$ 的 LCA ### 限制 $1 \le n, m, a_i, x \le 4\times 10^5, 2 \le l, r\le n$ 线性空间，强制在线 ## 1、[P5312 [Ynoi2011]竞赛实验班](https://www.luogu.com.cn/problem/P5312) ### 简要题意 四个操作 1. 在末尾 **添加** 一个 $x$ 2. 查询区间和 3. 全局异或 4. 全局排序 ### 限制 $1 \le n, m, \le 10^5, 0\le a_i, x\le 10^9$ ## 2、[P4117 [Ynoi2018]五彩斑斓的世界](https://www.luogu.com.cn/problem/P4117) ### 简要题意 两个操作 1. 区间中 $> x$ 的数减去 $x$ 2. 区间中某个数出现次数 ### 限制 时限 $8s$ ，空间 $O(n)$ $1 \le n \le 10^6, 1 \le m \le 5\times 10^5$ $1 \le l, r\le n, 0 \le a_i, x \le 10^5 + 1$ ## 3、[P7447 [Ynoi2007] rgxsxrs](https://www.luogu.com.cn/problem/P7447) ### 简要题意 两个操作 1. 区间中 $> x$ 的数减去 $x$ 2. 区间和，区间最大值，区间最小值 ### 限制 时限 $6s$ ，强制在线 $1 \le n, m \le 5\times 10^5$ $1 \le l, r\le n, 1 \le a_i, x \le 10^9$ 这道题原题是把空间卡到 $64\text{MB}$ 的，但是好像和空间复杂度没什么关系所以就放在这里了（（ ## 4、[P4690 [Ynoi2016] 镜中的昆虫](https://www.luogu.com.cn/problem/P4690) ### 简要题意 两个操作： 1. 区间推平 2. 区间数颜色 ### 限制 所有数在 $[1, 1e5]$ 以内。 空间 $O(n)$ ，不强制在线（存在强制在线的非线性空间做法） ## 5、[P5048 [Ynoi2019模拟赛]Yuno loves sqrt technology III](https://www.luogu.com.cn/problem/P5048) ### 简要题意 一个操作： 1. 区间众数 ### 限制 所有数在 $[1, 1e5]$ 以内。 空间 $O(n)$ ，强制在线 ## 6、[P5397 [Ynoi2018]天降之物](https://www.luogu.com.cn/problem/P5397) ### 简要题意 两个操作 1. 全局 $x$ 变 $y$ 2. 全局满足 $a_i=x, a_j=y$ 的最小 $|i-j|$ ### 限制 所有数在 $[1, 1e5]$ 以内，强制在线 顺便考虑改成区间修改区间查询怎么做 ## 7、[P6272 [湖北省队互测2014]没有人的算术](https://www.luogu.com.cn/problem/P6272) ### 简要题意 定义 $0$ 是一个数，除此之外的每一个数 $x$ 用一个二元组 $(y, z)$ 表示，其中 $y, z$ 也必须是数。 比较两个数大小则先比较第一关键字，若相等则比较第二关键字，特殊的， $0$ 小于任何数。 两个操作 1. $a_x$ 变成 $(a_y, a_z)$ 2. 区间最小值的下标 ### 限制 $1\le n \le 10^5, 1 \le m \le 5\times 10^5$ ，存在在线做法，空间 $O(n)$ ## 8、[P3710 方方方的数据结构](https://www.luogu.com.cn/problem/P3710) ### 简要题意 四个操作 1. 区间乘 2. 区间加 3. 单点查询 4. 单点撤销（保证只撤销 1, 2 操作且每个操作最多被撤销一次） ### 限制 $1 \le n, m, \le 1.5\times 10^5$ ，值域有取模所以不重要 原题保证数据随机，但其实并不需要 不强制在线 ## 9、[P4119 [Ynoi2018] 未来日记](https://www.luogu.com.cn/problem/P4119) ### 简要题意 两个操作 1. 区间 $x$ 变 $y$ 2. 区间第 $k$ 小 ### 限制 所有数在 $[1, 1e5]$ 内，没记错的话可以在线 ## 10、[P5113 Sabbat of the witch](https://www.luogu.com.cn/problem/P5113) ### 简要题意 三个操作 1. 区间推平 2. 区间和 3. 撤销某个没撤销过的区间推平 ### 限制 $1 \le n, m, \le 10^5, 1 \le a_i, x \le 10^9$ ，推平不超过 $65000$ 次 强制在线 ## 11、[P6019 [Ynoi2010] Brodal queue](https://www.luogu.com.cn/problem/P6019) ### 简要题意 两个操作 1. 区间推平 2. 区间 $i < j$ 且 $a_i=a_j$ 二元组个数 ### 限制 所有数在 $[1, 2e5]$ 内，空间限制 1GB 强制在线