CSU 1786 莫队+KDTree-白红宇

CSU 1786 莫队+KDTree

阅读量：6209 次

发布时间：2019-06-21

本文共 4162 字，大约阅读时间需要 13 分钟。

题意给出n个二维点(2e5) 和 q个询问(1e4) 每个询问给lr 问点l到r间有多少对点的曼哈顿距离<=d 点的坐标<=108

想出了莫队算法复杂度n^1.5 看起来很科学但是每次del和add点是直接进行暴力扫当前LR区间的点来算 ans将要增加/减少多少实际这样的复杂度是V^2.5 会t掉

由于是在二维上找一定范围的点的数目就可以想到KDTree V^1.5log(n)在15s下还是很科学的

做了一些曼哈顿距离的getdis函数调完又t了。。

我使用了一下青岛的K的写法开出三个维度 x y id 每次询问的是和x1y1曼哈顿距离<=d 并且 L <= id <= R 的点因为曼哈顿不是一个矩形是一个正方形旋转了的图形搜起来会比较麻烦

但是我感觉这个就是正解。。在网上也百度不到题解于是出去问了一下别人对这个题的看法然而也是莫队+KDT做的就很迷茫

要来代码一看有一个和我不同的是这样的把输入进去的xy 都变成x+y 和 x-y 在查询的时候不围绕改变后的xy做一个曼哈顿的查询而是直接查询矩形

xl = x - d xr = x + d yl = y - d yr = y + d 这样

查了查对这个优化的意义这个优化的意思是把曼哈顿距离转化为切比雪夫距离

http://m.blog.csdn.net/article/details?id=47259831 这个里面讲的

旋转之前两个点的曼哈顿距离是d 那么旋转后两个点的切比雪夫距离也是d 所以由一个点就可以求出来一个矩阵出来 KDT跑矩阵很快

还有一个点就是KDT的删除点

KDT的插入点是很简单的logn操作但是删除点的话由于这个点可能管辖一定的点删除了它就需要从它的孩子中找出一个点来管辖这个区域相当于每次删除都重构

其实不需要这样我们可以先把这棵树建出来一开始这个树只有形状但是点都没有放进去每次放进去一个点就相当于点亮一个点

可以做一个类似于离线的操作我们现在已经知道哪些点会被插入进这个树了只要它进去我们就记录下来

然后用这些点的形状建树虽然一开始没有点被插进去

我们在结构体里面定义val代表当前的管辖点存在与否/有多少个 sum代表这个区域有多少个 fa代表这个点的父亲节点是谁

所以每次删除或者插入一个点只需要改掉这个点的val 然后把这个点及其先辈的sum改了就可以了由于我们事先知道了所有的点所以建出来的树深度还是logn的

这种KDT写法也是很优雅的。。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;#define pb push_backint n , d , q ;int m , root , cmp_d ;int xl , xr , yl , yr ;int L , R ;struct node { int d[3] , Max[3] , Min[3] ; int sum ; int fa ; int val ; int l , r ; int id ;}tr[200050];bool cmp(node a , node b) { return a.d[cmp_d] < b.d[cmp_d] ;}int ix[200050] , iy[200050] ;int pos[200050] ;struct no { int l , r ; int id ;}xw[10050];bool cmp2(no a , no b) { if(pos[a.l] == pos[b.l]) return a.r < b.r ; return a.l < b.l ;}int an ;int ans[10050] ;void up(int p , int k) { for(int i=0;i<2;i++) { if(tr[p].Max[i] < tr[k].Max[i]) tr[p].Max[i] = tr[k].Max[i] ; if(tr[p].Min[i] > tr[k].Min[i]) tr[p].Min[i] = tr[k].Min[i] ; } tr[p].sum += tr[k].sum ;}int w[200050] ;int build(int l , int r , int D , int fa) { int mid = (l + r) >> 1 ; cmp_d = D ; nth_element(tr+l+1,tr+mid+1,tr+r+1,cmp) ; w[tr[mid].id] = mid ; tr[mid].fa = fa ; tr[mid].val = 0 ; tr[mid].sum = 0 ; for(int i = 0 ; i < 2 ; i ++ ) tr[mid].Max[i] = tr[mid].Min[i] = tr[mid].d[i] ; if(l != mid) tr[mid].l = build(l , mid-1 , D^1 , mid) ; else tr[mid].l = 0 ; if(r != mid) tr[mid].r = build(mid+1 , r , D^1 , mid) ; else tr[mid].r = 0 ; if(tr[mid].l) up(mid , tr[mid].l) ; if(tr[mid].r) up(mid , tr[mid].r) ; return mid ;}void upda(int rt , int val) { tr[rt].val += val ; while(rt) { tr[rt].sum += val ; rt = tr[rt].fa ; }}int query(int p) { if(tr[p].sum == 0) return 0 ; if(tr[p].Max[0] < xl || tr[p].Min[0] > xr || tr[p].Max[1] < yl || tr[p].Min[1] > yr) return 0 ; if(tr[p].Max[0] <= xr && tr[p].Min[0] >= xl && tr[p].Max[1] <= yr && tr[p].Min[1] >= yl) return tr[p].sum ; int ret = 0 ; if(tr[p].d[0] <= xr && tr[p].d[0] >= xl && tr[p].d[1] <= yr && tr[p].d[1] >= yl) ret += tr[p].val ; if(tr[p].l) ret += query(tr[p].l) ; if(tr[p].r) ret += query(tr[p].r) ; return ret ;}void cxh(int x , int y) { xl = x - d ; xr = x + d ; yl = y - d ; yr = y + d ;}int main () { int cas = 1 ; while(scanf("%d%d%d" , &n , &d , &q) != EOF) { int sz = sqrt(n) ; for(int i = 1 ; i <= n ; i ++ ) { scanf("%d%d" , &ix[i] , &iy[i]) ; pos[i] = i / sz ; tr[i].l = tr[i].r = 0 ; tr[i].d[0] = ix[i] + iy[i] ; tr[i].d[1] = ix[i] - iy[i] ; int z = ix[i] ; ix[i] = ix[i] + iy[i] ; iy[i] = z - iy[i] ; tr[i].id = i ; } root = build(1 , n , 0 , 0) ; an = 0 ; for(int i = 1 ; i <= q ; i ++ ) { scanf("%d%d" , &xw[i].l , &xw[i].r) ; xw[i].id = i ; } L = 0 ; R = 0 ; sort(xw+1,xw+1+q,cmp2) ; for(int i = 1 ; i <= q ; i ++ ) { while(L < xw[i].l) { cxh(ix[L] , iy[L]) ; upda(w[L] , -1) ; L ++ ; an -= query(root) ; } while(L > xw[i].l) { L -- ; cxh(ix[L] , iy[L]) ; an += query(root) ; upda(w[L] , 1) ; } while(R < xw[i].r) { R ++ ; cxh(ix[R] , iy[R]) ; an += query(root) ; upda(w[R] , 1) ; } while(R > xw[i].r) { cxh(ix[R] , iy[R]) ; upda(w[R] , -1) ; R -- ; an -= query(root) ; } ans[xw[i].id] = an ; } printf("Case %d:\n" , cas ++ ) ; for(int i = 1 ; i <= q ; i ++ ) printf("%d\n" , ans[i]) ; }}

转载于:https://www.cnblogs.com/rayrayrainrain/p/6814817.html

你可能感兴趣的文章

MySQL 基本语法(1.表字段操作，2表记录管理 3.运算符管理4.SQL查询 5.约束6.索引...