题目链接
传送门
思路
这个题在\(BZOJ\)上有个二维平面的版本(\(BZOJ2716\)天使玩偶),不过是权限题因此就不附带链接了,我也只是在算法进阶指南上看到过,那个题的写法是\(CDQ\),然后比赛开始半个小时我就开始写\(CDQ\),\(T\)了之后冷静分析发现复杂度我少算了个\(log\),\(CDQ\)写这题的复杂度是\(nlog^3(n)\),然后就没思路了。
赛后看\(qls\)说用三维\(bit\)可以过后试了一下\(T\)了,然后发现\(qls\)的代码当时跑了\(937ms\)应该是卡过去的,感觉是\(vector\)常数大,但是想不出除\(vector\)的其他动态开全局数组大小的方法,最后疯狂交在\(T\)了一页后成功卡过去了,下面贴一下三维\(bit\)的代码和\(CDQ\)写法(对拍了很久貌似没问题,就当过了吧~)的代码。
这两份代码的主体思路就是拆绝对值符号,然后查询时(拿\(x_1\leq x2,y_1\leq y2,z_1\leq z_2\)举例,下标为\(2\)的是查询的点)\(|x_2-x_1|+|y_2-y_1|+|z_2-z_1|=(x_2+y_2+z_2)-(x_1+y_1+z_1)\),然后就是要查询\(x_1+y_1+z_1\)的最大值用树状数组维护即可,其他情况分别移动坐标即可。
update:发现题解里面贴的那份代码的三维\(bit\)写法贼牛逼,贴的代码就改成看了那个队的代码之后写的了。
代码
//三维bit
#include
#include
//CDQ
#include
#include