写在前面
dls：“我不会数据结构，但是APIO的数据结构场我写了，还是蛮简单的。”
T1 CF643G
Sol:
有一个(O(nlog^2n))的做法：假设将区间排好序，取六等分点，则答案一定覆盖了若干点，求区间第(k)大即可。
然而会TLE
定义绝对众数为区间中出现超过一半的数。
有一个经典的做法求绝对众数，然而它要在保证有解的时候才保证正确性。
维护当前答案和出现次数，遇到相同则(+1)，不同则(-1)，降为(-1)的时候就把当前解替换。
显然如果有解的话，答案不会被替换掉（或者最后会换回来）。
可以扩展到(p ot= frac{1}{2})的情况，维护多个答案，调整加减权重即可。
可以用线段树维护上述操作。
顺便一提dls讲题的时候翻车了23333（被打死
线段树合并两个儿子的时候，先执行替换，再全部(-1)。正确性dls也不会不屑于证。
T2 HDU6087
Sol:
不会可持久化平衡树，告辞。
T4 CF453E
Sol：
序列可以分成若干段，每段都是同一时间清空的。
显然段的总数(O(n))。
以按恢复满需要的时间为权建主席树，因为同一段恢复的时间是相同的，一次查询一整段，可以(O(nlog n))做。
T5 CF1172F
Sol：
发现每个位置都是一个分段函数。
考虑用线段树维护区间内函数复合后的结果，可以证明长度为(l)的序列，对应的分段函数最多(l+1)段。
（证明：显然(f(x)-x)始终模(p)同余，且对于更大的(x)，“减去的(p)”的个数必然不会更少。由于([l,r])最多减去(r-l+1)个(p)，故最多(r-l+2)段）
复合两个函数的时候可以双指针法，每次遇到左边的断点就在右边暴力回退，可以证明回退次数最多一次。
（这里本来应该有一个证明，可是它咕了）（貌似和上面证明有关？）
T6 CF1178G
Sol：
dls:“这题透露着一股垃圾题的气息。果然，(n^2)能过。”
标程是分块+凸包，lxl可能会喜欢
绝对值因为每个数只会变(O(1))次，暴力做就好了。
对((a_i, a_ib_i))建凸包，由于(t_i)单调，每次最大值只会右移。
复杂度(O(nsqrt n))，据说带(log)会被卡。
有一个非常有趣的邪道解法：
线段树维护凸包，每个节点计算一个(wait)，表示再增加多少之后，这个节点的某个子树中，左右儿子大小关系就会改变。
每次修改只要不超过(wait)就可以打标记。
复杂度不会证明，但是跑的飞快。
T7
题意：维护一个序列，支持：
① 区间每个位置变成下标(xor X)的位置的值
② 区间每个下标(xor X)的位置变成这个位置的值
③ 区间xor
④ 区间下标二进制有奇数个1的位置的权值和
Sol:
可持久化trie维护一下，每次①②操作是一个子树复制，可能需要打标记啥的，dls懒得搞了（
T8 CF297E
Sol：
共有五种可能的情况，其中有一种很好算。
把线段看成点，两两之间如果相交连红边，否则连蓝边。
转化为统计同色三角形个数。
同色三角形(=C(n,3)-)异色三角形。
发现每个异色三角形恰好有两个异色角。
对每个点统计两种颜色的边个数即可。
T9 CF997E
Sol:
扫描线，对每个左端点维护到当前右端点的点数-边数((x,x+1))，记作(cnt)。
假设新加入了(x)，将新加边的区间(cnt)修改。
线段树可以支持一种标记：对区间(cnt)最小值，(ans+k)。
然后就做完了。
T10 CF1034D
Sol:
(k)这么大，显然不能拿堆做。
可以二分答案。
判断的时候可以双指针。
每次加入(r)的时候把(r)对应的区间全部覆盖，判断的时候只需要知道(>l)的和。
可以用set维护，但是发现每次二分的时候，操作序列都是不变的。
因此预处理出每次操作之后的序列即可，复杂度(O(nlog n + nlog T))。
T11 CF896E
Sol:
分块，用链表记录每块中为(x)的数。
在值域中启发式合并。
这样可以在(O(x))内把某块的值域缩小(x)。
T12
题意：一个长为(n)的序列，支持对([1,m],[m,r])归并排序（然而原序列无序，所以排序完也不一定有序），询问(a_i)
Sol:
发现可以划分成若干个段，每次按照段头归并。
可能会拆分若干段，但是每次最多合并一段。
平衡树维护即可。
T13 CF1148H
Sol:
不会。