https://www.cnblogs.com/OYzx/p/5506468.html
BZOJ2863:(允许离线)
题目大意:给定一个n*n的矩形,以及若干个操作,操作有如下两种:
1.给矩形的(x,y)加上一个v;
2.询问某个子矩阵的权值和。
数据范围:n<=5*10^5,操作数<=2*10^5;
(允许离线,可以用CDQ分治,把每个询问拆成4个矩形)
BZOJ4066:(在线)
题意如上。
数据范围: 1<=N<=500000,操作数不超过M=200000个,内存限制20M,保证答案在int范围内并且解码之后数据仍合法。
出现的每个x轴都开一个splay,然后对于每个询问,就变成了求这其间出现的每个X轴求Y范围内的splay区间和。(感觉可行)
好像正解是kdtree。有空再学。