「SDOI2009」虔诚的墓主人

传送门

几个月前某学姐给我推荐的毒瘤题之一。然而我直到现在也只切掉两道，我真是太菜了。

首先，为了方便，我们将题目中所给的坐标系顺时针旋转一下，令正下为 $x$ 轴正方向。我们先考虑单独一块墓地的虔诚度的计算。设其往左数有 $L$ 棵常青树，往右数有 $R$ 棵常青树，往上数有 $U$ 棵常青树，往下数有 $D$ 棵常青树，其虔诚度就是

$$C_{L}^{k}C_{R}^{k}C_{U}^{k}C_{D}^{k}$$

考虑到墓地不能和常青树重合，又有 $k\geqslant 1$，虔诚度为正的，也就是会对答案产生有效贡献的墓地，一定是在某几棵常青树之间。我们在读入时就可以统计出第 $x$ 行，第 $y$ 列上有多少棵常青树，分别记为 $sumx[x]$，$sumy[y]$。然后我们令 $x$ 坐标为第一关键字，$y$ 坐标为第二关键字，将所有常青树按坐标从小到大排序，然后按顺序遍历一遍。假设我们遍历到了第 $i$ 棵常青树，记 $cntx[x]$ 为前 $i-1$ 棵常青树中第 $x$ 行上有多少棵常青树，$cnty[y]$ 为前 $i-1$ 棵常青树中第 $y$ 列上有多少棵常青树，当前常青树坐标为 $(x[i],y[i])$。如果 $x[i]=x[i-1]$，则第 $i$ 棵常青树与第 $i-1$ 棵常青树之间就有可能有虔诚度为正的墓地。具体地，它们的虔诚度之和为

$$C_{cntx[x[i]]}^{k}C_{sumx[x[i]]-cntx[x[i]]}^{k}(\sum\limits_{i=y[i-1]+1}^{y[i]-1}C_{cnty[i]}^{k}C_{sumy[i]-cnty[i]}^{k})$$

怎么快速地查询与修改后面那个 $\Sigma$ 所涉及到的值？树状数组啊当然如果您非要写些乱七八糟的数据结构也没人拦着您。

坐标范围很大，因此我们需要离散化。而且很明显地，没有常青树的行与列是不需要考虑的。

#include<cstdio>

struct NOIp{
 unsigned long long RP,score;
};
NOIp NOIp2018;

int main(){
 for(;;){
 NOIp2018.RP++;
 NOIp2018.score++;
 }
 return 0;
}

以及，明天就是 NOIp 初赛了，在那之后三周就是复赛，我还不想退役啊但是我实在是太菜了qaq。