本文共 3803 字，大约阅读时间需要 12 分钟。
第一次遇见强制在线的题目 每个操作都和前面的ans有关 所以不能直接离线做
在这个问题中 kdtree更像一个线段树在一维单点修改区间询问的拓展一样
如果区间被询问区间完全包含 就不用继续递归
插入时如果该点已被修改 就不用建新点
由于kdtree是一个二叉搜索树 所以如果数据构造 是可以卡出一条链的 所以需要在插入一定点数之后开始重构这个kdtree 使深度维持在一个可控范围内
因为写错了in_it函数找了一天bug
#include #include #include #include #include #include #include using namespace std;#define L long longconst 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) ; } }}
转载于:https://www.cnblogs.com/rayrayrainrain/p/6353256.html