[BZOJ1176]mokia
cdq分治复习
之前完全忘记了cdq分治是什么东西了,今天yy了一番终于记起来了.
对于这道题来说,首先转成三维偏序的形式,对于一个矩形的询问可以转化成对四个点的询问,对(x,y,t)的询问表示t'<=t&&x'<=x&&y'<=y的那些操作.
现在变成三维偏序之后,就sort一维之后按照以下步骤进行:
1.solve(l,mid)
2.统计所有左边的点对右边的贡献(排序+树状数组)
3.solve(mid+1,r)
需要谨慎的一点是最好拿不重复的一维来排序,不然炒鸡麻烦,陌上花开调了我整整一天.
本来想着就懒一懒写树套树,后来还是觉得太长(至少90+)真烦ovo