A
发现实际上是一个直角边与坐标系垂直的直角三角形，直角顶左上且其上字符为 J，右边的字符是 O，底下的字符是 I。于是可以在 J 处统计贡献，另外两个做后缀和处理即可。
B
卡常做法里不要写 #define int long long !!!
\(O(n\log n)\)：所有数按数值从大到小排序，从后往前扫，依次删除当前数所在下标，然后往前找 \(1 \cdots lim\) 阶前驱，可以使用链表维护。
\(O(nlim)\)：注意到若一个点后面有多于 \(lim\) 个大于等于它的，则这个点不会再产生贡献，可以直接删掉。于是可以维护一个链表，对于每个点直接暴力跳前驱，若这个前驱权值大于等于当前点权值，则统计答案，统计到 \(lim\) 个答案后就可以 break 了。若小于等于，则增加其标记，若标记等于 \(lim\) 则直接删。复杂度均摊为 \(O(nlim)\)。
C
写的是贪心做法。考虑到肯定先给能更快收到水的叶子供水（即 \(dep[i]\) 更小的），我们将所有叶子按深度排序，从前往后保证每片叶子的供水。一片叶子的供水量是其到根的路径上流量最小值，可以直接暴力跳父亲统计。然后再把到根路径上的所有流量减掉该叶子的供水量。考虑如何统计答案。发现前 \(n\) 个时间点所有叶子收到水的总量可能会变（因为可能有的叶子预定的供水量还在路上），所以先枚举前 \(n\) 个时间点。在 \(n\) 个时间点之后，由于所有叶子每个时刻收到的总水量都固定了，所以可以直接算。时间复杂度 \(O(n^2)\)。
D
考试的时候甚至没有往二叉树那方面想？！
观察题目，发现每次翻转的区间都很整齐。如果把整个序列看成一棵二叉树，会发现每次翻转的实际上是某一层连续的若干子树（所代表的区间）。如果 \(l_i = r_i\) 的话，其实可以线段树维护区间逆序对数和跨区间中点的顺、逆序对数（下称 \(v_0, v_1\)）。然后发现翻转操作只会将跨过区间中点的顺、逆序对互换，于是就很好维护。对于 \(l_i, r_i\) 不相等的情况，考虑线段树维护区间内的子树翻转。发现任意一条线段树扔到线段树上都会变成 \(log\) 条线段。而翻转的子树区间也一样。只不过更大的线段（子树）代表若干包含于其中的线段（子树）的 LCA。于是问题变成给 \(x\) 子树内（全局）深度为 \(d\) 的所有后代的子树都执行翻转，然后维护区间逆序对。先考虑如果只翻转一棵后代 \(y\) 的子树是什么情况。显然 \(x\) 子树内逆序数的变化就等于 \(y\) 的子树内逆序数的变化。所以我们可以在 \(x\) 处维护 \(y\) 的 \(v_0, v_1\)。同样，如果翻转某一深度 \(d\) 的全部子树，那 \(x\) 子树内逆序数的变化就等于这些子树内逆序数的变化量加起来。所以我们只需要在 \(x\) 处维护其子树内所有深度的 \(v_0, v_1\) 即可。然后对 \(x\) 子树内的每个深度 \(d\) 开 \(tag\) （用 int 状压）记录 \(d\) 是否要被翻转。打 \(tag\) 的时候直接遍历一遍深度看这个深度要不要被翻转即可。复杂度 \(O(n2^n + n^2m)\)。
标签：20231024,子树,子树内,线段,叶子,区间,集训,翻转 From： https://www.cnblogs.com/forgotmyhandle/p/18000269