数据结构杂题精选

DPair · 2021-03-19 19:02:06 · 个人记录

你们不会真的要我讲分块吧

随便理一理不错的题目

难度较低，题目都比较 基础

信心题、CF785E Anton and permutation

简要题意

一个操作

1. 交换 (a_x, a_y) （其实可以看做单点修改） 每次修改后输出全局逆序对数量

   限制

顺便考虑一下 线性空间，强制在线 怎么做。

0、P7446 [Ynoi2007] rfplca

简要题意

给你一棵以 1 为根的有根树，用一个序列表示， a_i 为 i 的父亲结点。

两个操作

1. 区间中 a_i\leftarrow \max\{a_i-x, 1\}
2. 求 u, v 的 LCA

限制

线性空间，强制在线

1、P5312 [Ynoi2011]竞赛实验班

简要题意

四个操作

1. 在末尾 添加 一个 x
2. 查询区间和
3. 全局异或
4. 全局排序

限制

2、P4117 [Ynoi2018]五彩斑斓的世界

简要题意

两个操作

1. 区间中 > x 的数减去 x
2. 区间中某个数出现次数

限制

时限 8s ，空间 O(n)

3、P7447 [Ynoi2007] rgxsxrs

简要题意

两个操作

1. 区间中 > x 的数减去 x
2. 区间和，区间最大值，区间最小值

限制

时限 6s ，强制在线

这道题原题是把空间卡到 64\text{MB} 的，但是好像和空间复杂度没什么关系所以就放在这里了（（

4、P4690 [Ynoi2016] 镜中的昆虫

简要题意

两个操作：

1. 区间推平
2. 区间数颜色

限制

所有数在 [1, 1e5] 以内。

空间 O(n) ，不强制在线（存在强制在线的非线性空间做法）

5、P5048 [Ynoi2019模拟赛]Yuno loves sqrt technology III

简要题意

一个操作：

1. 区间众数

限制

所有数在 [1, 1e5] 以内。

空间 O(n) ，强制在线

6、P5397 [Ynoi2018]天降之物

简要题意

两个操作

1. 全局 x 变 y
2. 全局满足 a_i=x, a_j=y 的最小 |i-j|

限制

所有数在 [1, 1e5] 以内，强制在线

顺便考虑改成区间修改区间查询怎么做

7、P6272 [湖北省队互测2014]没有人的算术

简要题意

定义 0 是一个数，除此之外的每一个数 x 用一个二元组 (y, z) 表示，其中 y, z 也必须是数。

比较两个数大小则先比较第一关键字，若相等则比较第二关键字，特殊的， 0 小于任何数。

两个操作

1. a_x$ 变成 $(a_y, a_z)
2. 区间最小值的下标

限制

8、P3710 方方方的数据结构

简要题意

四个操作

1. 区间乘
2. 区间加
3. 单点查询
4. 单点撤销（保证只撤销 1, 2 操作且每个操作最多被撤销一次）

限制

2. 区间第 k 小

限制

所有数在 [1, 1e5] 内，没记错的话可以在线

10、P5113 Sabbat of the witch

简要题意

三个操作

1. 区间推平
2. 区间和
3. 撤销某个没撤销过的区间推平

限制