今天下午找Camp的训练题的时候找到的一场CF的题目，感觉题目的质量还不错，尤其是这一场的E题非常喜欢。

A. Brain’s Photos

没有什么多说的，非常基础的模拟题

B. Bakery

同样也没有什么多说的，这一题如果稍加变化是一道非常好的Div.2 C难度的题目

我做的时候使用了超级源跑最短路的想法，实际上完全不需要，一个贪心就可以了。

C. Pythagorean Triples

给你一个数，求与可以这个数组成勾股数的另外两个数。

感觉是数学里面非常基础的一个点，即a² - b² = (a + b)(a - b)，分奇偶讨论一下就可以发现答案，这一题给了数学不好的人非常好的提示，就是几组样例，思考样例的答案是如何构造出来的就可以发现上面的公式。

D. Persistent Bookcase

这题有点OI风范，感觉质量不算高，有点为了可持久化而可持久化的意思，非常裸的裸可持久化。但是又对可持久化的原理要求一定的了解，另外还有一丝卡内存，数据范围应该再稍微小一些比较好。

E. Garlands

这一题是整套题目里面最喜欢的一道题，大概能推测出来作者是先想出的这道题再补全剩下的题目。

题目的大意是在2000*2000的矩阵内给定若干条互不相交的灯带，每个灯如果亮就对它所在的格子有w的权值贡献，一次可以开或者关一个灯带，穿插着一些询问，询问的格式是问一个矩形区域内当前量着的灯的权值和是多少。

喜欢这道题的原因是这题给了充足的提示，引导你的思维往正解的方向上走，比如题目里面最明显的提示就是询问的个数不超过2000个，这就很容易去引导着想2000的平方左右的算法，事实上我最终的算法大约是O(nq log n)的。同时这一题还有很多非常基础的思想。

最开始看到这题的时候，以为是一道数据结构题，但是后来发现没有合适的数据结构可以处理这样的修改。这时候2000的提示就有了作用，这个两千提示我要单独处理询问，于是开始往离线处理的思路上去想，同时我们对于这样的询问一个显然的思想就是使用容斥原理来算出答案而非直接区间查询。

因此我们发现了另外一个2000乘2000的地方，即有不超过2000条灯带，灯带的长度也同样不超过2000，即可以考虑分不同的颜色来单独处理，忽略灯带的连续性，而只将其视作离散的点集，思考如何在2000乘2000的时间内计算某一种颜色对于所有区域的贡献。

接下来考虑使用排序离散化之后配合Bit完成区间查询的操作，发现可以满足题目的要求，复杂度即前文的平方log，可以接受。最后把答案合并即可，整个过程十分流畅，同时没有非常复杂的数据结构，整个完成时间应该可以在45分钟左右。作为一道没有过于高级的数据结构题目，也是非常适合初学者锻炼思想以进一步提高的题目。