Luogu

分析

还是 KD-Tree 板子。

插入时利用替罪羊树重构那一套保证平衡。

查询时判断查询矩形和当前矩形是否有交,如果完全包含直接返回当前矩形和,部分包含就递归下去,否则返回 $0$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;
const double alpha=0.85;

#define ls t[o].lc
#define rs t[o].rc
int D,sta[N],top=0,tot=0,rt;
struct point { int x[2],w; } p[N];
bool operator <(point a,point b) { return a.x[D]<b.x[D]; }
struct node { int mn[2],mx[2],lc,rc,sum,sz; point p; } t[N];
inline int newnode() { return top?sta[top--]:++tot; }
inline void pushup(int o) {
    for (re int i=0;i<2;++i) {
        t[o].mn[i]=t[o].mx[i]=t[o].p.x[i];
        if (ls) {
            t[o].mn[i]=min(t[o].mn[i],t[ls].mn[i]);
            t[o].mx[i]=max(t[o].mx[i],t[ls].mx[i]);
        }
        if (rs) {
            t[o].mn[i]=min(t[o].mn[i],t[rs].mn[i]);
            t[o].mx[i]=max(t[o].mx[i],t[rs].mx[i]);
        }
    }
    t[o].sum=t[ls].sum+t[rs].sum+t[o].p.w;
    t[o].sz=t[ls].sz+t[rs].sz+1;
}
inline int build(int l,int r,int d) {
    if (l>r) return 0;
    int o=newnode(),mid=(l+r)>>1;
    D=d,nth_element(p+l,p+mid,p+r+1),t[o].p=p[mid];
    ls=build(l,mid-1,d^1),rs=build(mid+1,r,d^1);
    pushup(o); return o;
}
inline void rebuild(int o,int pos) {
    if (ls) rebuild(ls,pos);
    p[pos+t[ls].sz+1]=t[o].p,sta[++top]=o;
    if (rs) rebuild(rs,pos+t[ls].sz+1);
}
inline void check(int& o,int d) {
    if (alpha*t[o].sz<max(t[ls].sz,t[rs].sz))
        rebuild(o,0),o=build(1,t[o].sz,d);
}
inline void insert(int& o,point p,int d) {
    if (!o) { o=newnode(); ls=rs=0,t[o].p=p,pushup(o); return; }
    p.x[d]<=t[o].p.x[d]?insert(ls,p,d^1):insert(rs,p,d^1);
    pushup(o); check(o,d);
}
inline int in(node a,int lx,int ly,int rx,int ry) {
    if (lx<=a.mn[0]&&a.mx[0]<=rx&&ly<=a.mn[1]&&a.mx[1]<=ry) return 1;
    if (rx<a.mn[0]||lx>a.mx[0]||ry<a.mn[1]||ly>a.mx[1]) return 0;
    return 2;
}
inline int query(int o,int lx,int ly,int rx,int ry) {
    int res=0;
    if (lx<=t[o].p.x[0]&&t[o].p.x[0]<=rx&&
        ly<=t[o].p.x[1]&&t[o].p.x[1]<=ry) res+=t[o].p.w;
    if (ls) {
        int k=in(t[ls],lx,ly,rx,ry);
        if (k==1) res+=t[ls].sum;
        else if (k==2) res+=query(ls,lx,ly,rx,ry);
    }
    if (rs) {
        int k=in(t[rs],lx,ly,rx,ry);
        if (k==1) res+=t[rs].sum;
        else if (k==2) res+=query(rs,lx,ly,rx,ry);
    }
    return res;
}
#undef ls
#undef rs

int main() { read(); int lastans=0;
    while ("longge ak ioi") {
        int op=read();
        if (op==3) break;
        if (op==1) {
            int x=read()^lastans,y=read()^lastans,w=read()^lastans;
            insert(rt,(point){x,y,w},0);
        } else {
            int lx=read()^lastans,ly=read()^lastans;
            int rx=read()^lastans,ry=read()^lastans;
            printf("%d\n",lastans=query(rt,lx,ly,rx,ry));
        }
    }
    return 0;
}
最后修改:2020 年 02 月 25 日 11 : 49 AM