Ruins He's house

今晚最后一题冲动了，没看范围就模拟，为某孩子送去了 50 分。。。

好吧，我在这里说说前两题。。。

这题典型的线段树加离散化，比赛的时候没有思路，中午突然想到了怎么实现。

这题主要的思路是将全部的数据读取进来然后离线处理，离散化的时候把不同的点按照先 $x$ 后 $y$ 的方式离散化，也就是说只要两个点不是同一个点，那么他们的离散化后的 hash 值就不一样，将离散化后的值放到 lst 数组中去。

在线段树中维护第 $i$ 个 $lst$ 元素是否存在，如果存在，那么线段树中的第 $i$ 个元素值就是 $lst[i]$ 对应的 $y$ 值，否则就为 $-1$，$seg$ 的值记录 $[l,r]$ 区间的最大值。每次 find 的时候，读取的如果是 $x, y$，那么去找 $[x+1,M]$ 区间，优先找左边的区间，如果左边区间的最大值比 $y$ 来的大，那么解一定在左边区间，如果左边区间的最大值小于或等于 $y$，那么用同样的方法找右区间，如果依然没有比 $y$ 大的，那么返回 $-1$，否则返回第一个比 $y$ 大的区间在 $lst$ 数组中对应的脚标。

主要是离散化的方式有点特别，先按 $xy$ 排序，记录 $lst$ 数组，然后按 $id$ 排序，返回原来输入的顺序，这样保证了读取的顺序和输入顺序一致。

因为今天要打区域赛的缘故，昨晚 CF 没有做，现在放出 ABC 的思路，后两题表示不怎么会，一题图论，一题数论，平时都是队友搞定的。。。

这题一眼看去就是更新区间查找点，典型的树状数组解法，但是如果用三维树状数组的话，会遇到一个难题，那就是怎么分割？

我们看简单的问题开始，对于一维的情况，将区间 $(a,b)$ 进行更新，那么就在 $a$ 处加 $v$，$b+1$ 处减 $v$ 即可。

对于二维的情况，那就麻烦一点，将区域 $(x_1, y_1)$ 到 $(x_2, y_2)$ 进行更新，那么就在 $(x_1, y_1)$ 处加 $v$，在 $(x_2+1,y_1)$ 和 $(x_1,y_2+1)$ 处减 v，在 $(x_2+1, y_2+1)$ 处加 v 即可。

那么三维的呢？经过画图，我得到了结论，那就是 $(x_1, y_1, z_1)$ 加 v，和 $(x_1, y_1, z_1)$ 相邻奇数长度的点减 $v$，这些点有$(x_2+1, y_1, z_1)$、$(x_1, y_2+1, z_1)$、$(x_1, y_1, z_2+1)$ 还有 $(x_2+1, y_2+1, z_2+1)$，剩下的就是加 $v$ 了。

把三个维度不同的树状数组的情况和在一起，源点 $P$ 加 $v$ 和 $P$ 相邻奇数位置的减 $v$，偶数位置的加 $v$，这样就可以快速地记下来全部的切割情况了。

持续一个半月的暑期 ACM 集训暂时告一段落，想想也改把平时遇到的问题进行总结了。。

在这个暑期的集训中，我们的能力可以说是发生了质的变化，想想去年刚接触 ACM 的时候做的趣味赛，以及前半年参加的校赛，从校初赛 5 题惊险出线到现在可以和队友在一起切题，感觉就是一眨眼间的事情。

这最后的大半个月，我和两个队友基本上每天都做一套题，过题数从刚开始的 3、4 道到现在的 5、6 道，可以说我们在成长，整个集训队的孩子们都在成长。而在这个过程中，也暴露出了许多的问题，在此，我做出如下总结：