A
小学数学
B
小学数学
D
题意：有一个初始全0的$n^2(n\le 1000)$矩阵，在经过许多次操作之后矩阵变成给定的样子。其中每次操作都是选定一个子矩形并用一个没用过的$1\cdots n^2$中的数进行覆盖。给定最终矩阵，问操作中可能的第一个数字的种类数。
解：可以发现，若矩阵非全0，则任何未出现的数字均可能是第一个。对于每个出现的数字，都可以方便处理出它的最小覆盖范围，且易知每个数字都覆盖最小范围的情况下才能覆盖所有可能性。观察发现，被大于一个数字的最小覆盖覆盖到的位置的最终数字必然不可能是第一个数字。因此显然可以利用二维区间树状数组解决，复杂度$O(n^2\lg n)$。
但覆盖可以直接暴力做。考虑你脑子里能想到的最复杂的覆盖方式最终需要扫大约$500^3$次，或者多个两三倍。所以就做完了…ecnu评测机飞快且时限2s且数据范围实在有点小。
补F
原题地址：https://loj.ac/p/2551 江苏省选2018 列队
省选签到题(说实话确实是)
题意：我懒得在这里说了，反正原题loj上有。就算啥时候loj关了，洛谷也得有吧（这句话不包含觉得洛谷比loj活得长的意思，只是因为这里贴出来的是loj上的，那么洛谷关不关不影响看不看得到这个题面）。洛谷关了，别的地方也会有的，毕竟强省省选题。
解：主席树。
看起来像是个主席树，那么主席树我们一般先怎么思考呢？先想一想如果是在整个区间进行询问的话应该怎么做，即L,R永远是1,n的情况下应该怎么做。我们可以发现，直接把所有点的坐标加起来是不行的，因为在算距离的绝对值过程当中，不同点的坐标对答案贡献的正负情况是不同的。那么我们可以再想一想，找到正负分界点再利用数学公式计算不就可以解决了嘛。设分界点为$x$，则如果取$x$符合$x-k+1=num_x$（$num_x$表示$x$点左边(不包含$x$)有几个学生），则从$x$起，所有后面的位置均是通过右边的同学左移来得到的；而在$x$之前，所有位置均是通过左边同学右移得到的。这样我们可以得到一个最终答案的计算公式。而显然$x$的位置是可以在主席树上方便求得的，求得$x$之后求和在主席树上也是方便做的。因此这道题就做完了。果然之前做的主席树题目还是太naive了。数据结构的中端操作还需要多练习，不能仅限于会低端操作就完事了。其实这道题本质上也就是个普通线段树题套个主席树的壳子罢了嘛。