MnZn 刚学 kdt 求调板子

Nt_Tsumiki @ 2024-02-20 22:16:07

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;
int n,block;

struct KD_tree {
    #define N 200001

    struct Point;
    struct Tree;

    const double A=0.75;
    int tcnt,flatcnt,rt,rubcnt,rub[N];
    struct Point {
        int c[2],val;

        int operator[](int x) { return c[x]; }
        void operator=(Tree tr) { c[0]=tr[0],c[1]=tr[1],val=tr.val; }
    }p[N];
    struct Tree {
        int l,r,val,sum,c[2],maxn[2],minn[2],siz;

        int operator[](int x) { return c[x]; }
        void operator=(Point poi) { val=poi.val,c[0]=poi[0],c[1]=poi[1],l=r=sum=maxn[0]=maxn[1]=minn[0]=minn[1]=siz=0; }
    }t[N];

    void upd(int x) {
        t[x].sum=(t[x].l?t[t[x].l].sum:0)+(t[x].r?t[t[x].r].sum:0)+t[x].val;
        t[x].siz=(t[x].l?t[t[x].l].siz:0)+(t[x].r?t[t[x].r].siz:0)+1;
        t[x].maxn[0]=t[x].minn[0]=t[x][0],t[x].maxn[1]=t[x].minn[1]=t[x][1];
        for (int i:{0,1}) {
            if (t[x].l) t[x].maxn[i]=max(t[x].maxn[i],t[t[x].l].maxn[i]),
                        t[x].minn[i]=min(t[x].minn[i],t[t[x].l].minn[i]);
            if (t[x].r) t[x].maxn[i]=max(t[x].maxn[i],t[t[x].r].maxn[i]),
                        t[x].minn[i]=min(t[x].minn[i],t[t[x].r].minn[i]);
        }
    }

    void build(int &x,int l,int r,int d) {
        int mid=(l+r)>>1; x=rub[rubcnt--];
        nth_element(p+l,p+mid,p+r+1,[d](Point p1,Point p2){ return p1[d]<p2[d]; });
        t[x]=p[mid];
        if (l<mid) build(t[x].l,l,mid-1,d^1);
        if (r>mid) build(t[x].r,mid+1,r,d^1);
        upd(x);
    }

    bool check_poi_cap_squ(int x,Point poi) {
        if ((t[x].minn[0]<=poi.c[0] and poi.c[0]<=t[x].maxn[0])
            and (t[x].minn[1]<=poi.c[1] and poi.c[1]<=t[x].maxn[1])) return 1;
        return 0;
    }

    bool check_squ_in_poi(int x,Point poi) {
        if (poi.c[0]>=t[x].maxn[0] and poi.c[1]>=t[x].maxn[1]) return 1;
        return 0;
    }

    int ask(int x,Point poi) {
        if (!x) return 0;
        if (check_squ_in_poi(x,poi)) return t[x].sum;
        int res=0;
        if (check_poi_cap_squ(t[x].l,poi)) res+=ask(t[x].l,poi);
        if (check_poi_cap_squ(t[x].r,poi)) res+=ask(t[x].r,poi);
        return res;
    }

    void flat(int x) {
        p[++flatcnt]=t[x],rub[++rubcnt]=x;
        if (t[x].l) flat(t[x].l);
        if (t[x].r) flat(t[x].r);
    }

    void ins(int &x,Point poi,int d) {
        if (!x) {
            t[x=rub[rubcnt--]]=poi;
            upd(x);
            return;
        }
        if (poi[d]<t[x][d]) ins(t[x].l,poi,d^1);
        else ins(t[x].r,poi,d^1);
        upd(x);
        if (A*t[x].siz<(double)t[t[x].l].siz or A*t[x].siz<(double)t[t[x].r].siz) {
            flatcnt=0;
            flat(t[x].siz); build(x,1,flatcnt,0);
        }
    }

    void ins(int x,int y,int k) { ins(rt,Point{{x,y},k},0); }
    int ask(int x,int y) { return ask(rt,Point{{x,y},0}); }
    void init() { for (int i=1;i<N;i++) rub[++rubcnt]=i; }

    #undef N
}t;

int main() {
    scanf("%d",&n); block=sqrt(n);
    t.init();
    int op,x1,y1,x2,y2,k,las=0;
    while (1) {
        scanf("%d",&op);
        if (op==1) {
            scanf("%d%d%d",&x1,&y1,&k);
            x1^=las,y1^=las,k^=las;
            t.ins(x1,y1,k);
        } else if (op==2) {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1^=las,y1^=las,x2^=las,y2^=las;
            printf("%d\n",las=t.ask(x2,y2)-t.ask(x1-1,y2)-t.ask(x2,y1-1)+t.ask(x1-1,y1-1));
        } else break;
    }
    return 0;
}

by Nt_Tsumiki @ 2024-02-20 22:16:27

@5k_sync_closer

by 鳶一折纸 @ 2024-02-20 22:22:35

@5k_sync_closer

by yanyanghu @ 2024-02-20 22:44:51

我与洛谷有不共戴天之仇

by Nt_Tsumiki @ 2024-02-21 06:20:37

目前调出来一个错，是判断当前矩形是否与询问矩形有交的 check 锅了

最新版 code：

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;
int n,block;

struct KD_tree {
    #define N 200001

    struct Point;
    struct Tree;

    const double A=0.75;
    int tcnt,flatcnt,rt,rubcnt,rub[N];
    struct Point {
        int c[2],val;

        int operator[](int x) { return c[x]; }
        void operator=(Tree tr) { c[0]=tr[0],c[1]=tr[1],val=tr.val; }
    }p[N];
    struct Tree {
        int l,r,val,sum,c[2],maxn[2],minn[2],siz;

        int operator[](int x) { return c[x]; }
        void operator=(Point poi) { val=poi.val,c[0]=poi[0],c[1]=poi[1],l=r=sum=maxn[0]=maxn[1]=minn[0]=minn[1]=siz=0; }
    }t[N];

    void upd(int x) {
        t[x].sum=(t[x].l?t[t[x].l].sum:0)+(t[x].r?t[t[x].r].sum:0)+t[x].val;
        t[x].siz=(t[x].l?t[t[x].l].siz:0)+(t[x].r?t[t[x].r].siz:0)+1;
        t[x].maxn[0]=t[x].minn[0]=t[x][0],t[x].maxn[1]=t[x].minn[1]=t[x][1];
        for (int i:{0,1}) {
            if (t[x].l) t[x].maxn[i]=max(t[x].maxn[i],t[t[x].l].maxn[i]),
                        t[x].minn[i]=min(t[x].minn[i],t[t[x].l].minn[i]);
            if (t[x].r) t[x].maxn[i]=max(t[x].maxn[i],t[t[x].r].maxn[i]),
                        t[x].minn[i]=min(t[x].minn[i],t[t[x].r].minn[i]);
        }
    }

    void build(int &x,int l,int r,int d) {
        int mid=(l+r)>>1; x=rub[rubcnt--];
        nth_element(p+l,p+mid,p+r+1,[d](Point p1,Point p2){ return p1[d]<p2[d]; });
        t[x]=p[mid];
        if (l<mid) build(t[x].l,l,mid-1,d^1);
        if (r>mid) build(t[x].r,mid+1,r,d^1);
        upd(x);
    }

    bool check_poi_cap_squ(int x,Point poi) {
        if (poi[0]>=t[x].minn[0] and poi[1]>=t[x].minn[1]) return 1;
        return 0;
    }

    bool check_squ_in_poi(int x,Point poi) {
        if (poi[0]>=t[x].maxn[0] and poi[1]>=t[x].maxn[1]) return 1;
        return 0;
    }

    int ask(int x,Point poi) {
        if (!x) return 0;
        if (check_squ_in_poi(x,poi)) return t[x].sum;
        int res=0;
        if (check_poi_cap_squ(t[x].l,poi)) res+=ask(t[x].l,poi);
        if (check_poi_cap_squ(t[x].r,poi)) res+=ask(t[x].r,poi);
        return res;
    }

    void flat(int x) {
        p[++flatcnt]=t[x],rub[++rubcnt]=x;
        if (t[x].l) flat(t[x].l);
        if (t[x].r) flat(t[x].r);
    }

    void ins(int &x,Point poi,int d) {
        if (!x) {
            t[x=rub[rubcnt--]]=poi;
            upd(x);
            return;
        }
        if (poi[d]<=t[x][d]) ins(t[x].l,poi,d^1);
        else ins(t[x].r,poi,d^1);
        upd(x);
        if (A*t[x].siz<(double)t[t[x].l].siz or A*t[x].siz<(double)t[t[x].r].siz) {
            flatcnt=0;
            flat(t[x].siz); build(x,1,flatcnt,0);
        }
    }

    void ins(int x,int y,int k) { ins(rt,Point{{x,y},k},0); }
    int ask(int x,int y) { return ask(rt,Point{{x,y},0}); }
    void init() { for (int i=1;i<N;i++) rub[++rubcnt]=i; }

    #undef N
}t;

int main() {
    scanf("%d",&n); block=sqrt(n);
    t.init();
    int op,x1,y1,x2,y2,k,las=0;
    while (1) {
        scanf("%d",&op);
        if (op==1) {
            scanf("%d%d%d",&x1,&y1,&k);
            x1^=las,y1^=las,k^=las;
            t.ins(x1,y1,k);
        } else if (op==2) {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1^=las,y1^=las,x2^=las,y2^=las;
            printf("%d\n",las=t.ask(x2,y2)-t.ask(x1-1,y2)-t.ask(x2,y1-1)+t.ask(x1-1,y1-1));
        } else break;
    }
    return 0;
}

by 5k_sync_closer @ 2024-02-21 08:55:25

@Nt_Tsumiki

1. ask 中要考虑自己的贡献

    int ask(int x, Point poi)
    {
        if (!x)
            return 0;
        if (check_squ_in_poi(x, poi))
            return t[x].sum;
        int res = 0;
        if (t[x].c[0] <= poi.c[0] && t[x].c[1] <= poi.c[1])
            res += t[x].val; //加上这句
        if (check_poi_cap_squ(t[x].l, poi))
            res += ask(t[x].l, poi);
        if (check_poi_cap_squ(t[x].r, poi))
            res += ask(t[x].r, poi);
        return res;
    }

2. 唐氏错误，88 行 flat(t[x].siz); 应为 flat(x);

by Nt_Tsumiki @ 2024-02-21 08:56:32

@5k_sync_closer 这下糖完了