Ruins He's house

这题被范围卡了挺久，线段树的懒操作是指访问到的指定区间如果在需要求的区间内部，那么就直接返回，这样，就遇到了一个问题，就是如何记录子区间的状态，用一个 $del$ 变量来记录子区间的状态，注意，是子区间，这样我们就可以用精简的代码来完成更新区间查找区间的操作。

好吧。。我的第二题现在还是挂着，算了，就把第二题无视掉吧，贴一下 ACD 的解题思路。

好久没写扫描线了，今天想拿些数据结构题目练手，在题目分类里面看到了这题，就拍上了。

扫描线排序离散化，线段树的区间代表 $y$ 的脚标，然后对 $y$ 进行离散化，二分查找对应的 y。

$val$ 用来记录区间被覆盖的次数，严格 $O(nlgn)$ 的访问，然后直接扫描一遍就可以了。

对精度要求不高，原来数组开小了，$eps$ 设成 1e-8 就 WA 了，不知道是数据开到 $1000$ 不够还是 $eps$ 太小。

这几次比赛由于没有太好的解题策略，以至于我们队把这个水题给放走了，大部分时间都在改计算几何，到最后也没有 AC。

这题不想说什么，很大自然的题目，就是模拟，用各种 STL 来模拟，我考虑到既然模拟了，应该不会超时吧？今天就拍了下，果断 1Y，这么暴力的方法 600 多 ms 过。

嗯，主要是记录每个人最近一次下载代码的时间，每行更新的时间和优先级，每个人的优先级。

懒得 hash 了，直接 map 做。

对于 submit 操作，之前 modify 的行号全部放到一个 list 中，submit 的时候直接清空链表就可以了。。。

今天悲剧的第一题没看懂题，好吧，不会做，B 题最简单，放出来。

这题的思路实际上是并查集，先定义一个数组 $st$ 表示现在的状态，目标状态是 $1，2，3，\cdots，n$，那么，每次查找 $i$ 和 $i+v[i]$ 和$i-v[i]$ 三个数，把他们合并，表示他们可以互相转换，那么用 $O(n)$ 的复杂度扫一遍，可以把全部的元素属于什么集合预处理出来，最后只要判断 $st[i]$ 和 $i$ 是不是一个集合里的就可以了。

今天无聊复习 C++，封装了个并查集的类，刚好用上。。。