BZOJ 4066 kd-tree 矩形询问求和

第一次遇见强制在线的题目每个操作都和前面的ans有关所以不能直接离线做

在这个问题中 kdtree更像一个线段树在一维单点修改区间询问的拓展一样

如果区间被询问区间完全包含就不用继续递归

插入时如果该点已被修改就不用建新点

由于kdtree是一个二叉搜索树所以如果数据构造是可以卡出一条链的所以需要在插入一定点数之后开始重构这个kdtree 使深度维持在一个可控范围内

因为写错了in_it函数找了一天bug

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

#include<math.h>

#include<queue>

#include<string>

using namespace std;

#define L long long

const int INF = 999999999 ;

const int maxn = 200050 ;

int n , root , cmp_d , m;

struct node {

    int d[2] , Max[2] , Min[2] ;

    int l , r ;

    int sum ;

    int z ;

}a[maxn];

int x, y , X;

int x1, x2, y11 ,y2 ;

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(int p , int k) {

    a[p].Max[0] = max(a[p].Max[0] , a[k].Max[0]) ;

    a[p].Max[1] = max(a[p].Max[1] , a[k].Max[1]) ;

    a[p].Min[0] = min(a[p].Min[0] , a[k].Min[0]) ;

    a[p].Min[1] = min(a[p].Min[1] , a[k].Min[1]) ;

    a[p].sum += a[k].sum ;

}

int build(int l , int r , int D){

    int 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].sum = a[mid].z ;

    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 inse(int x , int y , int X) {

    int p = root ;

    int D = 0 ;

    while(true) {

        if(x > a[p].Max[0]) a[p].Max[0] = x ;

        if(x < a[p].Min[0]) a[p].Min[0] = x ;

        if(y > a[p].Max[1]) a[p].Max[1] = y ;

        if(y < a[p].Min[1]) a[p].Min[1] = y ;

        a[p].sum += X ;

        if(x == a[p].d[0] && y == a[p].d[1]) {

            a[p].z += X ;

            return ;

        }

        else {

            if(D == 0) {

                if(x <= a[p].d[0]) {

                    if(a[p].l) p = a[p].l ;

                    else {

                        n ++ ;

                        a[n].l = a[n].r = 0 ;

                        a[n].Max[0] = a[n].Min[0] = a[n].d[0] = x ;

                        a[n].Min[1] = a[n].Max[1] = a[n].d[1] = y ;

                        a[n].sum = a[n].z = X ;

                        a[p].l = n ;

                        return ;

                    }

                }

                else {

                    if(a[p].r) p = a[p].r ;

                    else {

                        n ++ ;

                        a[n].l = a[n].r = 0 ;

                        a[n].Max[0] = a[n].Min[0] = a[n].d[0] = x ;

                        a[n].Min[1] = a[n].Max[1] = a[n].d[1] = y ;

                        a[n].sum = a[n].z = X ;

                        a[p].r = n ;

                        return ;

                    }

                }

            }

            else {

                if(y <= a[p].d[1]) {

                    if(a[p].l) p = a[p].l ;

                    else {

                        n ++ ;

                        a[n].l = a[n].r = 0 ;

                        a[n].Max[0] = a[n].Min[0] = a[n].d[0] = x ;

                        a[n].Min[1] = a[n].Max[1] = a[n].d[1] = y ;

                        a[n].sum = a[n].z = X ;

                        a[p].l = n ;

                        return ;

                    }

                }

                else {

                    if(a[p].r) p = a[p].r ;

                    else {

                        n ++ ;

                        a[n].l = a[n].r = 0 ;

                        a[n].Max[0] = a[n].Min[0] = a[n].d[0] = x ;

                        a[n].Min[1] = a[n].Max[1] = a[n].d[1] = y ;

                        a[n].sum = a[n].z = X ;

                        a[p].r = n ;

                        return ;

                    }

                }

            }

        }

        D ^= 1 ;

    }

}

bool in_it(int p , int x1,int y11,int x2 , int y2 ){

    if(x1 <= a[p].Min[0] && x2 >= a[p].Max[0] && y11 <= a[p].Min[1] && y2 >= a[p].Max[1]) {

        return true ;

    }

    return false ;

}

bool rea_out(int p , int x1 , int y11 , int x2 , int y2 ){

    if(x2 < a[p].Min[0] || x1 > a[p].Max[0] || y2 < a[p].Min[1] || y11 > a[p].Max[1]) return true;

    return false ;

}

int ans ;

void ask(int p) {

    if(rea_out(p , x1 , y11 , x2 , y2)) return ;

    if(in_it(p , x1 , y11 , x2 , y2)) {

        ans += a[p].sum ;

        return ;

    }

    if(a[p].d[0] >= x1 && a[p].d[0] <= x2 && a[p].d[1] >= y11 && a[p].d[1] <= y2) {

        ans += a[p].z ;

    }

    if(a[p].l){

        ask(a[p].l);

    }

    if(a[p].r){

        ask(a[p].r);

    }

}

int main(){

    scanf("%d",&m);

    int op;

    int last=0;

    n = 0;

    while(~scanf("%d",&op)){

        if(op == 3)break;

        if(op == 1) {

            scanf("%d%d%d",&x,&y,&X) ;

            x ^= last;

            y ^= last;

            X ^= last;

            if(n == 0) {

                n ++ ;

                a[n].d[0] = x ; a[n].d[1] = y ;

                a[n].z = X ;

                a[n].sum = X ;

                root = build(1,n,0) ;

            }

            else {

                inse(x,y,X) ;

            }

            if(n % 5000 == 0) {

                root = build(1,n,0) ;

            }

        }

        else {

            scanf("%d%d%d%d",&x1,&y11,&x2,&y2) ;

            x1 ^= last;

            y11 ^= last;

            x2 ^= last;

            y2 ^= last;

            ans = 0;

            if(n>0)

                ask(root);

            else ans = 0 ;

            last = ans ;

            printf("%d\n",ans) ;

        }

    }

}

巴特西

BZOJ 4066 kd-tree 矩形询问求和

最新文章

热门文章