物理 信息竞赛中的一些算法：前缀和，二维前缀和与骗分
这是一个关于信息竞赛的帖子（应该可以发在 O-Box 里吧）
$A\to B$ 表示把 $A$ 的值设为 $B$。
$a[i]$ 表示数组 $a$ 的第 $i$ 项。
$i$ 除非特殊说明，不指虚数单位。
某些词语可能使用不规范，请大家指出。
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
前缀和：
假设我们遇到这样一道题目：
输入 $n$ 个数，并给出一些区间 $[l_i,r_i]$，输出每个区间内数的和。
我们显然不能对于每个区间循环求和，这样会 TLE，所以我们需要更快的方法。
我们只需要注意到 $\sum_{n=l}^{r}a_n=\sum_{n=1}^{r}a_n-\sum_{n=1}^{l-1}a_n$，就行了。
因为我们需要求一个区间的和，只需要先求从第一个数到区间末尾的和，减去不属于这个区间的部分，就行了。
为什么这样可以防止 TLE 呢？
假设我们获得了数列 $a_1,a_2,\dots,a_n$，我们可以用 $\mathrm{O}(n)$ 的复杂度求出数列 $s_i=\sum_{n=1}^{i}a_n$，然后如果我们要求 $\sum_{n=l}^{r}$，就可以用 $s_r-s_{l-1}$，然后就没有然后了。
二维前缀和：
这次 $s_{i,j}=\sum_{n=1}^{i}\sum_{m=1}^{i}a_{n,m}$，如果求 $a_{i,j}$，可以这么算：：
$a_{i,j}=s_{i,j}-s_{i-1,j}-s_{i,j-1}+s_{i-1,j-1}$
画个图就可以理解了。
骗分法：
作为做题者，什么题可以骗分？
例：
……
……
……
输出字典序最小的方案，如果没有方案输出“Impossible”。
解法：直接输出“Impossible”。
作为出题者，如何避免骗分？
每个测试点，你需要处理 $N$ 次任务。
- 1
一道练习题：
Kulwehfrihulwefilusherg 有一个巨大的农场，但由于某些原因，农场的地面并不平坦。农场是一块长 $n$ 米的正方形网格状地面。每格长宽都是 $1$ 米。第 $i$ 行第 $j$ 格的高度是 $a_{i,j}$。
他需要找到一块边长 $k$ 米的正方形地面，用来养它的 Aefrjhkberafbjhaefrjhb 品种的奶牛。
但 Kulwehfrihulwefilusherg 的 Aefrjhkberafbjhaefrjhb 品种的奶牛们对环境有要求，要求这块地面中地面高度的中位数尽可能小。
求最小的中位数。
其中 $k$ 为奇数。
$1\le k\lt n\le10^5$
$0\lt a_{i,j}\lt10^6$
提示：需要用二维前缀和和二分查找。
