分析

开始学 了，先来做一个模板题。个人感觉 其实就是一个高维的二叉搜索树。其实可以像替罪羊树一样重构来保证平衡，为了偷懒就没写了。

代码

#include<bits/stdc++.h>
using namespace std;
// #define int long long
const int N = 1e7 + 100; 
int read() {
    int x = 0;char ch = getchar();
    while(!isdigit(ch)) {ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return x ;
}
struct Node{int p[2],ch[2],mx[2],mi[2],si,sum,val;}t[N];
int size,rt;
void pushup(int x) {
    int lc = t[x].ch[0],rc = t[x].ch[1];    
    for(int i = 0;i <= 1;i++) {
        t[x].mi[i] = t[x].mx[i] = t[x].p[i];
        if(lc) {
            t[x].mx[i] = max(t[x].mx[i],t[lc].mx[i]);
            t[x].mi[i] = min(t[x].mi[i],t[lc].mi[i]);
        }
        if(rc) {
            t[x].mx[i] = max(t[x].mx[i],t[rc].mx[i]);
            t[x].mi[i] = min(t[x].mi[i],t[rc].mi[i]);
        }
    }
    t[x].sum = t[lc].sum + t[rc].sum + t[x].val;
    t[x].si = t[lc].si + t[rc].si + 1;
    // cout <<"node:: "<< x << " val:: "<< t[x].sum<<" debug: "<< t[x].mi[0] <<" "<< t[x].mx[0] <<" "<< t[x].mi[1] <<" "<< t[x].mx[1] << endl;
}
void insert(int &u,int x,int y,int val,int type) {
    if(!u) {
        u = ++size;t[u].ch[0] = t[u].ch[1] = 0;
        t[u].si = 1;t[u].sum = t[u].val = val;
        t[u].mx[0] = t[u].mi[0] = t[u].p[0] = x;
        t[u].mx[1] = t[u].mi[1] = t[u].p[1] = y;
        return ;
    }
    if(type == 0) {
        if(x <= t[u].p[0]) insert(t[u].ch[0],x,y,val,1 - type);
        else insert(t[u].ch[1],x,y,val,1 - type);
    }
    else {
        if(y <= t[u].p[1]) insert(t[u].ch[0],x,y,val,1 - type);
        else insert(t[u].ch[1],x,y,val,1 - type);
    }
    pushup(u);
}

bool in(int u,int lx,int rx,int ly,int ry) {
    return(lx <= t[u].mi[0] && t[u].mx[0] <= rx && ly <= t[u].mi[1] && t[u].mx[1] <= ry);
}
bool out(int u,int lx,int rx,int ly,int ry) {
    return (t[u].mi[0] > rx || t[u].mx[0] < lx || t[u].mi[1] > ry || t[u].mx[1] < ly);
}
int query(int u,int lx,int rx,int ly,int ry) {
    if(!u) return 0;
    if(in(u,lx,rx,ly,ry)) return t[u].sum;
    if(out(u,lx,rx,ly,ry)) return 0;
    int res = 0,lc = t[u].ch[0],rc = t[u].ch[1];    
    if(lx <= t[u].p[0] && t[u].p[0] <= rx && ly <= t[u].p[1] && t[u].p[1] <= ry) 
        res += t[u].val;
    return (res + query(lc,lx,rx,ly,ry) + query(rc,lx,rx,ly,ry));
}
void print(int x) {
    cout <<"node:: "<< x << " val:: "<< t[x].sum<<" debug: "<< t[x].mi[0] <<" "<< t[x].mx[0] <<" "<< t[x].mi[1] <<" "<< t[x].mx[1] << endl;
    if(t[x].ch[0]) print(t[x].ch[0]);
    if(t[x].ch[1]) print(t[x].ch[1]);
}
int main() {
    while(1) {
        int opt = read();
        if(opt == 0) continue;
        if(opt == 1) {
            int x = read(),y = read(),a = read();
            insert(rt,x,y,a,0);
        }
        if(opt == 2) {
            int lx = read(),ly = read(),rx = read(),ry = read();
            printf("%d\n",query(rt,lx,rx,ly,ry));
        }
        if(opt == 3) break;
        // print(rt);
    } 
}