BZOJ 4154 kd-tree dfs序 + 二维空间的区间(矩阵)更新单点查找-白红宇

BZOJ 4154 kd-tree dfs序 + 二维空间的区间(矩阵)更新单点查找

阅读量：5982 次

发布时间：2019-06-20

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

一开始没思路感觉像是一个树形dp 然而不会

然后看了一眼题解就明白了

一个点的子树用dfs序表示肯定是一个连续的区间并且由于有子树的距离限制可以转化为一个深度的区间

于是每个点都会有一个在二维平面上的标号(x,y) == (编号,深度)

并且每次进行更新一个节点的子树的时候就可以得到一个x的区间和一个y的区间 (实际上这些x是独一无二的 y更像是一个限制的条件)

这样就可以转化成一个二维的平面每次选择一个矩阵进行颜色的统一更新询问单点的颜色做一个延时标记

询问单点的时候可以每次找啊找直到找到这个点也可以判断一下mark mark一定是最新的历史如果这个点在这个区间里面并且这个区间有修改历史那么ans就是mark

不过加了这个优化速度并没有提升多少

在这里kd-tree很像线段树区别就是维度不同

找了一个小bug就直接a掉了开心!

#include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            using namespace std;#define L long longconst L INF = 999999999 ;const L maxn = 100050 ;const L mod = 1000000007;/**用dfs序设定每个点的子树的标号区间存下每个点的deep则每个点在二维平面的x为它的标号 y为它的深度 (如果仅要表示这个点主码x就可以了)利用kdtree来进行区间修改单点查询如果区间满足 Max[0] Min[0] 属于 x1 x2 && Max[1] Min[1] 属于 y11 y2 就直接修改这个区间的颜色 设置一个延时标记x1 x2 == l[a] r[a] y11 y2 == deep[a] deep[a] + l单点查询直接进行一个logn的查询*/L n , c , q ;L deep[maxn] ;vector
            
             vec[maxn] ;L l[maxn] , r[maxn] ;L cnt ;void dfs(L u , L dep) { deep[u] = dep ; l[u] = ++ cnt ; for(L i = 0; i < vec[u].size(); i ++ ){ L v = vec[u][i] ; dfs(v,dep + 1) ; } r[u] = cnt ;}L root , cmp_d ;struct node { L l , r ; L d[2] , Max[2] , Min[2] ; L c ; L mark ;}a[maxn];bool cmp(node a,node b){return ((a.d[cmp_d] < b.d[cmp_d])||(a.d[cmp_d] == b.d[cmp_d] && a.d[!cmp_d] < b.d[!cmp_d])) ;} ;void up(L p , L k ){ if(a[k].Max[0] > a[p].Max[0]) a[p].Max[0] = a[k].Max[0] ; if(a[k].Max[1] > a[p].Max[1]) a[p].Max[1] = a[k].Max[1] ; if(a[k].Min[0] < a[p].Min[0]) a[p].Min[0] = a[k].Min[0] ; if(a[k].Min[1] < a[p].Min[1]) a[p].Min[1] = a[k].Min[1] ;}void down(L p) { if(a[p].mark == 0)return ; L newc = a[p].mark ; a[p].mark = 0 ; if(a[p].r) { L rr = a[p].r ; a[rr].c = newc ; a[rr].mark = newc ; } if(a[p].l) { L ll = a[p].l ; a[ll].c = newc ; a[ll].mark = newc ; } return ;}L build(L l, L r , L D) { L mid = (l+r)/2 ; cmp_d = D; nth_element(a+1+l,a+1+mid,a+1+r,cmp) ; a[mid].Max[0] = a[mid].Min[0] = a[mid].d[0] ; a[mid].Max[1] = a[mid].Min[1] = a[mid].d[1] ; a[mid].c = 1 ; a[mid].mark = 0 ; if(l != mid)a[mid].l = build(l,mid-1,D^1); else a[mid].l = 0; if(r != mid)a[mid].r = build(mid+1,r,D^1); else a[mid].r = 0; if(a[mid].l)up(mid,a[mid].l) ; if(a[mid].r)up(mid,a[mid].r) ; return mid ;}void upda(L p , L x1 , L y11 , L x2 , L y2 , L newc ) { if(a[p].Max[0] < x1 || a[p].Min[0] > x2 || a[p].Max[1] < y11 || a[p].Min[1] > y2) { return ; } if(a[p].Min[0] >= x1 && a[p].Max[0] <= x2 && a[p].Max[1] <= y2 && a[p].Min[1] >= y11) { a[p].c = newc ; a[p].mark = newc ; return ; } down(p) ; if(a[p].d[0] >= x1 && a[p].d[0] <= x2 && a[p].d[1] >= y11 && a[p].d[1] <= y2) { a[p].c = newc ; } if(a[p].l) { upda(a[p].l , x1, y11 , x2 , y2 , newc) ; } if(a[p].r) { upda(a[p].r , x1, y11 , x2 , y2 , newc) ; }}L ans ;void ask(L p , L x, L y) { if(a[p].d[0] == x && a[p].d[1] == y) { ans = a[p].c ; return ; } if(a[p].mark != 0) { ans = a[p].mark ; return ; } down(p) ; if(a[p].l) { L ll = a[p].l ; if(x >= a[ll].Min[0] && x <= a[ll].Max[0] && y >= a[ll].Min[1] && y <= a[ll].Max[1]) { ask(ll , x , y) ; } } if(a[p].r) { L ll = a[p].r ; if(x >= a[ll].Min[0] && x <= a[ll].Max[0] && y >= a[ll].Min[1] && y <= a[ll].Max[1]) { ask(ll , x , y) ; } }}int main(){ L t ; scanf("%lld",&t); while(t-- ){ scanf("%lld%lld%lld",&n,&c,&q) ; for(L i = 1; i <= n ; i ++ )vec[i].clear() ; for(L i = 2; i <= n ; i ++ ){ L fa ; scanf("%lld",&fa) ; vec[fa].push_back(i) ; } cnt = 0 ; dfs(1,1) ; for(L i = 1; i <= n; i ++ ){ a[i].l = a[i].r = 0; a[i].d[0] = l[i] ; a[i].d[1] = deep[i] ; } root = build(1,n,0) ; L sum = 0; for(L i = 1; i <= q; i ++ ){ L aa , ll , cc ; scanf("%lld%lld%lld",&aa,&ll,&cc); L x1 = l[aa] ; L x2 = r[aa] ; L y11 = deep[aa] ; L y2 = deep[aa] + ll ; if(cc != 0) { upda(root , x1 , y11 , x2 , y2 , cc) ; } else { ans = -1 ; L x = l[aa] ; L y = deep[aa] ; ask(root, x , y) ; sum += ans * i ; sum %= mod ; } } printf("%lld\n",sum) ; }}

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

你可能感兴趣的文章