数据结构 2021 小作业1 Hint #1
Description
数据结构 2021 小作业1 Hint
由于不能透露题解所以只是部分题目的提示，具体细节希望大家动动脑筋思考～
有些地方可能讲的不是很清楚，如果有什么疑问的话随时都欢迎大家来问。
因为难度较大的题目大部分是 A 班的所以可能会涉及到一些 B 班同学还没有接触过的知识，如果有兴趣的话可以百度了解一下，应该不会太难理解，也可以找答疑组的同学问。
1087. 基础数据结构
n,q 数据范围是 600w，所以需要线性复杂度常数优秀的夏天同学用快排通过了这道题。
难点在于求最大值，正序删除维护最大值比较困难，可以尝试倒序插入同时记录最大值。
1088. 春樱对决
M 可以对 2 * (当前人数 - 1）取模。
难点在每次怎么找到第 x 个出局的人，可以在树状数组上二分找到，复杂度 O(nlogn)。
Bonus：有线性做法，设 f(n, dic, pre) 表示当前还剩 n 个人，dic 表示报数的方向，pre 表示上一个出局的是哪个人，f 返回的值是在这 n 个人里面最后出局的人的是 这 n 个人里的 第几个。
1090. Bang
这题我的做法写起来有点复杂，希望有更简单做法的同学和我交流一下。
Hint1: 不能被二分图染色的图答案恒为 0，能被二分图染色并且两个起点同色的话答案也为 0。
Hint2: 难点在求分别在两个集合里的数的最小差值，答案一定是互为前驱后继的一对数，用平衡树维护和每个数互为前驱后继的是哪个数即可。
1094. pyramid
设在金字塔并且不在墓室里的格子个数为 m，这个数是固定的。
满足题设条件的是金字塔中的数字和与墓室中的数字和模 m 同余，枚举可能的每个金字塔位置，对每个金字塔都找到同余的内部数字和最小的墓室即可。
这个大概只能用数据结构维护带个 log 来做，不知道有没有不带 log 的做法...