萌新求助K-D tree
  • 板块P4148 简单题
  • 楼主Ame__
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/2/18 10:51
  • 上次更新2023/11/5 03:07:41
查看原帖
萌新求助K-D tree
245875
Ame__楼主2021/2/18 10:51

RTRT,不知道哪里写挂了,而且错的四个点都错的一样也不知道为啥= =,求帮忙看看

// Author: Ame__
#include<bits/stdc++.h>
#include<stdint.h>
#define _ 0
#define AME__DEBUG
#define bomb exit(0)
#define LOG(FMT...) fprintf(stderr , FMT)
#define TOWA(FMT...) fprintf(stdout , FMT)
using namespace std;
/*Grievous Lady*/
    
typedef int32_t i32;
typedef int64_t i64;
typedef double qwq;
    
const int BUF_SIZE = 1 << 12;
char buf[BUF_SIZE] , *buf_s = buf , *buf_t = buf + 1;
    
#define PTR_NEXT() \
{ \
    buf_s ++; \
    if(buf_s == buf_t) \
    { \
        buf_s = buf; \
        buf_t = buf + fread(buf , 1 , BUF_SIZE , stdin); \
    } \
}
    
#define mians(_s_) \
{ \
    while(!isgraph(*buf_s)) PTR_NEXT();\
    char register *_ptr_ = (_s_); \
    while(isgraph(*buf_s) || *buf_s == '-') \
    { \
        *(_ptr_ ++) = *buf_s; \
        PTR_NEXT(); \
    } \
    (*_ptr_) = '\0'; \
}
    
template <typename _n_> void mian(_n_ & _x_){
    char buf_s; while(buf_s != '-' && !isdigit(buf_s)) buf_s = getchar();
    bool register _nega_ = false; if(buf_s == '-'){ _nega_ = true; buf_s = getchar(); }
    _x_ = 0; while(isdigit(buf_s)){  _x_ = _x_ * 10 + buf_s - '0'; buf_s = getchar(); } if(_nega_) _x_ = -_x_;
}
    
const i32 kato = 5e5 + 10;

template <typename _n_> bool cmax(_n_ &a , const _n_ &b){ return a < b ? a = b , 1 : 0; }
template <typename _n_> bool cmin(_n_ &a , const _n_ &b){ return a > b ? a = b , 1 : 0; }
    
i32 n , opt , x , y , w , X , Y , cnt , tot , lastans;

struct point{
    i32 x , y , w;
    point(i32 x = 0 , i32 y = 0 , i32 w = 0): x(x) , y(y) , w(w){ }
    friend bool operator !=(const point &a , const point &b){
        return a.x != b.x || a.y != b.y;
    }
}a[kato] , b[kato];

inline bool cmp1(const point &a , const point &b){
    return a.x < b.x;
}

inline bool cmp2(const point &a , const point &b){
    return a.y < b.y;
}

namespace towa{
    struct node{
        node *ls , *rs;
        static queue<node*> q;
        point p;
        i32 x1 , x2 , y1 , y2 , val , size;
        node(){ }
        node(const point &qaq): p(qaq){
            ls = rs = 0x0 , x1 = x2 = qaq.x , y1 = y2 = qaq.y , val = qaq.w , size = 1;
        }
        inline void up1(node *x){
            this -> x1 = min(this -> x1 , x -> x1) , this -> x2 = max(this -> x2 , x -> x2);
            this -> y1 = min(this -> y1 , x -> y1) , this -> y2 = max(this -> y2 , x -> y2);
        }
        inline void up2(node *x){
            val += x -> val , size += x -> size;
        }
        void *operator new(size_t){
            static node *S = 0x0 , *T = 0x0; node *tmp;
            return q.empty() ? (S == T && (T = (S = new node[1024]) + 1024 , S == T) ? 0x0 : S ++) : (tmp = q.front() , q.pop() , tmp);
        }
        void operator delete(void *qaq){ q.push(static_cast<node*>(qaq)); }
    }*root;

    queue<node*> node::q;

    inline void build(node *&o , i32 l , i32 r , i32 opt){
        if(l > r) return void(o = 0x0);
        i32 mid = (l + r) >> 1;
        nth_element(b + l , b + mid , b + r + 1 , opt ? cmp2 : cmp1);
        o = new node(b[mid]);
        build(o -> ls , l , mid - 1 , opt ^ 1);
        build(o -> rs , mid + 1 , r , opt ^ 1);
        if(o -> ls) o -> up1(o -> ls) , o -> up2(o -> ls);
        if(o -> rs) o -> up1(o -> rs) , o -> up2(o -> ls);
    }

    inline void del(node *&o){
        if(!o) return;
        if(o -> ls) del(o -> ls);
        b[++ tot] = o -> p;
        if(o -> rs) del(o -> rs);
        delete(o);
    }

    inline void judge(node *&o , i32 opt){
        tot = 0; i32 res = o -> size;
        if(0.725 * o -> size <= static_cast<qwq>(max(o -> ls ? o -> ls -> size : 0 , o -> rs ? o -> rs -> size : 0))) del(o) , build(o , 1 , res , opt);
    }

    inline void insert(node *&o , const point &a , i32 opt){
        if(!o) return void(o = new node(a));
        if(opt == 1){
            if(a.y <= o -> p.y) insert(o -> ls , a , opt ^ 1);
            else insert(o -> rs , a , opt ^ 1);
        }else{
            if(a.x <= o -> p.x) insert(o -> ls , a , opt ^ 1);
            else insert(o -> rs , a , opt ^ 1);
        }
        if(o -> ls) o -> up1(o -> ls) , o -> up2(o -> ls);
        if(o -> rs) o -> up1(o -> rs) , o -> up2(o -> rs);
        judge(o , opt);
    }

    inline int ask(node *o , i32 x1 , i32 x2 , i32 y1 , i32 y2){
        if(!o || x2 < o -> x1 || x1 > o -> x2 || y2 < o -> y1 || y1 > o -> y2) return 0;
        if(x1 <= o -> x1 && o -> x2 <= x2 && y1 <= o -> y1 && o -> y2 <= y2) return o -> val;
        i32 res = 0;
        if(x1 <= o -> p.x && o -> p.x <= x2 && y1 <= o -> p.y && o -> p.y <= y2) res += o -> p.w;
        return ask(o -> ls , x1 , x2 , y1 , y2) + ask(o -> rs , x1 , x2 , y1 , y2) + res;
    }
}

inline int Ame_(){
#ifdef AME__
    freopen(".in" , "r" , stdin); freopen(".out" , "w" , stdout); int nol_cl = clock();
#endif
    mian(n);
    while(~scanf("%d" , &opt)){
        if(opt == 1) cnt ++ , mian(a[cnt].x) , mian(a[cnt].y) , mian(a[cnt].w) , a[cnt].x ^= lastans , a[cnt].y ^= lastans , a[cnt].w ^= lastans , towa::insert(towa::root , a[cnt] , 0);
        if(opt == 2) mian(x) , mian(y) , mian(X) , mian(Y) , x ^= lastans , X ^= lastans , y ^= lastans , Y ^= lastans , TOWA("%d\n" , lastans = towa::ask(towa::root , x , X , y , Y));
        if(opt == 3) break;
    }
#ifdef AME__TIME
    LOG("Time: %dms\n", int((clock() - nol_cl) / (qwq)CLOCKS_PER_SEC * 1000));
#endif
    return ~~(0^_^0); /*さようならプログラム*/
}
    
int Ame__ = Ame_();
    
int main(){;}

/*
4
1 2 3 3
2 1 1 3 3
1 1 1 1
2 1 1 0 7
3
*/
2021/2/18 10:51
加载中...