去雅礼会被虐的

Day -1

上午坐高铁到湖南，然后转了地铁，公交。

雅礼的老师人很好，帮我们订了酒店（第一次见到这种操作，受宠若惊）

下午去雅礼转了一圈，办了饭卡，不过因为机房维护，晚上回宾馆了，只拷了他们的比赛题，准备晚上看看。

中途和他们的初中的同学聊天，得到了被强校吊打的恐惧

某初中同学：我去年本来能考300+，结果挂到了240。

啊。。我好菜啊。。

晚上看了一波今天的考试题，都是只会打暴力，状态好的话可以打满90，状态不行的话可能暴力都会打挂掉。

然后看了看题解，T1的60分dp自己想到了一部分，但是没有往dp哪一方面考虑，然后就被正解震撼到了。

题意大概是这样的：

（算了先放一个弱化版：

给定一个二维平面，每个点有一个权值，每次求一个正方形内的权值和。

正方形的边与$x,y$轴平行的情况大家都会

考虑是成$45°$的情况

先想一种比较咸鱼的做法

用$dp(i,j,k)$表示$(i,j)$为中心，对角线长度的二分之一是$k$的菱形权值和

然后就可以搞

下面是正解

我们维护一个梯形的前缀和：

如图对于用黑框圈住的1，我们维护这一段的和

然后我们再反向维护一下这个值

下面是查询部分

现在我们要查询红色十字这部分的权值和

先求出橙色梯形的权值和（预处理过）

然后再减去蓝色梯形（此处退化），得到绿色的梯形

然后注意到我们反向维护了一个值，用上面的操作瞎搞出来粉色的梯形，然后对它们的面积取交，就得到了上半部分

然后用上面的操作得到下半部分

很神的思路

然后这个题是这样的：求菱形的权值和，而且距离菱形越近的点乘的权值越大。

然后就要多维护一些东西。。。

很蛇。。