（果然题目描述越人畜无害，题目难度越丧心病狂）
（感觉T2大大锻炼了我的码力）
T1 辣鸡
看见自己作为题目标题出现在模拟赛中，我内心无比激动
看完题面，一个N^2暴力思路已经成形
然后开始拼命想正解...
想不出来啊，时间过的好快...
码吧...
码个暴力都用一个小时啊，凉了....
辣鸡了...
A了..正解就是暴力...
矩形内部直接算
外部只需考虑相邻的情况
先sort一遍剪枝，只枚举横坐标可能有交集的矩形
（NlogN解法的确存在，但是DeepinC&skyh打了半天被恶心死了）
T2 魔鬼毒瘤题 不会
T2 模板
请问kat大神这是什么傻逼模板题？
树上启发式合并。
和数据结构的小并大启发式合并不同，树上启发式合并是 重儿子信息保留，轻儿子信息暴力
大概流程：先dfs一遍预处理子树大小，重儿子等信息
第二次dfs，先递归到轻儿子解决轻儿子询问
不保留轻儿子数据（清空），递归到重儿子解决重儿子询问
保留重儿子数据，在此基础上暴扫所有轻子树，得到父亲答案
此算法必须建立在 父亲节点的信息是字节点信息的叠加（或可以以其他方式继承） 的基础上
优化方式是尽量减少枚举，增加信息的多次利用
复杂度分析：
如果求解父亲节点询问时都扫整个子树，在随机数据下比较优秀，因为每次问题规模都会减少一半左右
复杂度为节点数×平均深度 (瞎猜的但是应该差不太多，考虑每个点被暴扫的次数）
于是碰到链状数据就萎了
而我们伟大的启发式，就不会遇到这个问题
还是考虑每个点被暴扫的次数，只有他祖辈作为轻儿子出现时，他自己才会被暴扫
而他到根节点的轻边数量不会超过log，所以可以保证nlogn
就用这个
vector存操作，用以上套路+线段树（权值也可，普通也可，一个离散化的事）就可以n（logn）2地愉快解决辣
（线段树忘开4倍对拍了一小时）
T3 大佬
首先要知道每天的期望花费都是相同的，然后这题就结束了
考试时没想到，非常吃屎。
deepinc：在一种可能的情况下，我们横向来看前一天和后一天之间的确是有相互限制的关系的
然而我们如果把所有的方案都列出来，写满一个黑板
就会发现某一天出现的题目难度的排列 的概率都是相等的
虽然横向相互钳制，但是从随机出题的纵向来看，他们相互钳制的关系并不影响期望的等价性
被外校女生爆踩orz