CF526F Pudding Monsters
典题，发现这本质上是一个一维问题，一个区间合法当且仅当 \(\max - \min = r - l\)，枚举右端点维护左端点的变化量，用两个单调栈维护到 \(r\) 的最大最小，用线段树维护区间最小值及其个数，由于 \([r, r]\) 满足条件且 \(\max -\min - r + l\geq 0\)，因此每次累加最小值个数即可。
时间复杂度 \(\mathcal O(n\log n)\)。
CF603E Pastoral Oddities
先找“每个点度数均为奇数”的充要条件，容易发现是“加入所有边后不存在奇连通块”。
证明是简单的。
充分性：显然对于每个连通块独立，随便找一个点当根求出一棵生成树，自底向上考虑每个非根的点，若儿子度数为偶数则加上其与父亲的连边，否则删去这条边，此时除了根所在连通块都满足条件，同时注意到总度数为偶数，有奇数个点的度数为奇数，必然根的度数也为奇数。
必要性：若存在奇数连通块，则要求总度数为奇数，无论怎么删去边，总度数都为奇数，显然非法。
注意到能合并就合并是最优的，因为无论是偶 + 偶，奇 + 偶，奇 + 奇都不会增加奇数个数，于是对于单次询问，可以考虑类似 Kruskal 的过程得到答案。
注意到答案单调不升，可以考虑整体二分。
注意到每次加边的变化只有当两边子树都是奇数才有用，可以直接上 LCT。
注意到若我们从后往前处理，将边集排序后维护一个指针表示当前答案，对于已经加入答案的边而言我们需要在某一时间段维护其合法范围，就可以直接线段树分治维护。
时间复杂度 \(\mathcal O(n\log n \log m)\)。
CF1446D2 Frequency Problem (Hard Version)
容易用调整法证明两个答案其中一个为全局众数，设为 \(maj\)。
暴力就是再枚举另一个元素 \(x\)，将 \(x\) 看做 1，\(maj\) 看做 -1，答案就是最长的和为 0 的段。
还有一个暴力：直接枚举出现次数 \(cnt\)，双指针枚举 \(maj\) 的第一次出现位置，对 \([l, r]\) 的这些数开桶记录出现次数为 \(i\) 的有多少个，当 最大值恰为 \(cnt\) 且个数 \(\geq 2\) 则存在。
结合上面两个算法，考虑根号分治，对于 \(occ_i > B\) 的数直接 \(\mathcal O(n)\) 算，否则直接枚举 \(cnt\)，也可以 \(\mathcal O(n)\) 算。
时间复杂度 \(\mathcal O(n\sqrt n)\)。