The 10th Shandong Provincial Collegiate Programming Contest

https://codeforces.com/gym/104459 *G. Heap 题意 有一个初始序列，现将每个元素插入堆中。每个元素插入时会按照大根堆或小根堆的规则插入。给出初始序列和最终序列，问每次插入是将它视作大根堆还是小根堆，若有多种可能，输出字典序最小的。 题解 由于每次插入只会影响从当前位置到根的路径上的点，所以直接模拟就可以了。倒序枚举每个元素，找到当前元素最终落在了路径上的哪
ACM
#线段树 #贪心 #欧拉回路 #数论

UESTC 2023 Summer Training

雄关漫道真如铁，而今迈步从头越。 Day1 ### E. Jewel of Data Structure Problems 题意 定义一个数组是奇的当且仅当它的逆序对数为奇数。定义一个排列的美丽度为它的最长奇子序列的长度，如果不存在则为 −1-1−1。给出一个排列 ppp 和 qqq 次更新，每次更新交换排列中两个数的位置。要求输出每次更新后 ppp 的美丽度。 题解 用到了一些关于逆序对的性质
ACM
#训练

AtCoder Beginner Contest 309

F - Box in Box 题意 给出 nnn 个长方体。问是否存在两个长方体，其中一个的长宽高均严格小于另一个。 题解 三维偏序问题。由于题目中是严格小于，所以直接套cdq分治好像不太正确。可以这样考虑：先按照 xxx 进行排序，然后建一棵线段树，代表区间 [1,y][1,y][1,y] 上 zzz 的最小值。每次查询的时候在小于 yyy 的区间上查询。注意，当相同的坐标全部查询完后才能进
ACM
#线段树

AtCoder Beginner Contest 279

感觉ABC的质量还是很高的啊。 F - BOX 题意 有 nnn 个盒子，一开始盒子 iii 内装有小球 iii。每次执行以下三种操作之一： 将盒子 yyy 内的所有小球放入盒子 xxx。 记当前所有盒子内的小球个数为 kkk，将小球 k+1k+1k+1 放入盒子 xxx。 询问小球 xxx 在哪个盒子中。 题解 一道并查集应用的好题。 由于询问操作和合并操作，很容易能想到并查集。但是直接
ACM
#dp #并查集 #生成函数

树上启发式合并

树上启发式合并 注意事项：多测时，需要清空dfn和big，同时要将对根的 dfs1 的 keep 标记置为 0。 树上启发式合并一般解决的是不带修改对子树内的询问，可以通过对所有儿子暴力求答案，但删除轻儿子的结果，保留重儿子的结果，从而保证了复杂度。 树上启发式合并的流程为： 遍历轻子树，递归求解答案，不保留它们的影响。 遍历重子树，递归求解答案，保留它们的影响。 再遍历轻子树，保留它们的影响。
ACM
#树上启发式合并