萌新刚学kdt求助

RT，全MLE。

#include<bits/stdc++.h>

#ifndef CRT
#define endl '\n' 
#endif

using namespace std ;

typedef long long ll ;
typedef unsigned long long ull ;
typedef long double ld ;

const ll N = 5e5 + 5 ;

struct point
{
    ll x , y , w ;
    point ( const ll & x = 0 , const ll & y = 0 , const ll & w = 0 ) : x ( x ) , y ( y ) , w ( w ) {}
};

struct kdtree
{
    ll idx , root ;
    ll tot , buf [N] ;
    const ld maxsz = 0.72 ;
    struct node
    {
        ll l = 0 , r = 0 ;
        point p ;
        ll sum , size ;
        ll minn [2] , maxn [2] ;
    } nodes [N] ;
    ll add ()
    {
        if ( ! tot )
        {
            return ++ idx ;
        }
        return buf [tot --] ;
    }
    void pushup ( ll u )
    {
        auto &l = nodes [nodes [u].l] , & r = nodes [nodes [u].r] ;
        nodes [u].sum = nodes [u].p.w + l.sum + r.sum ;
        nodes [u].size = l.size + r.size + 1 ;
        nodes [u].minn [0] = min ( { nodes [u].p.x , l.minn [0] , r.minn [0] } ) ;
        nodes [u].maxn [0] = max ( { nodes [u].p.x , l.maxn [0] , r.maxn [0] } ) ;
        nodes [u].minn [1] = min ( { nodes [u].p.x , l.minn [1] , r.minn [1] } ) ;
        nodes [u].maxn [1] = max ( { nodes [u].p.x , l.maxn [1] , r.maxn [1] } ) ;
    }
    point pt [N] ;
    void getseq ( ll u , ll cnt )
    {
        if ( nodes [u].l )
        {
            getseq ( nodes [u].l , cnt ) ;
        }
        buf [++ tot] = u ;
        pt [nodes [nodes [u].l].size + cnt] = nodes [u].p ;
        if ( nodes [u].r )
        {
            getseq ( nodes [u].r , cnt + nodes [nodes [u].l].size + 1 ) ;
        }
    }
    ll rebuild ( ll l , ll r , ll k )
    {
        if ( l > r )
        {
            return 0 ;
        }
        ll mid = l + r >> 1 ;
        ll u = add () ;
        nth_element ( pt + l , pt + mid , pt + r + 1 , [&]( point a , point b ){
            return ( k ? ( a.y < b.y ) : ( a.x < b.x ) ) ;
        }) ;
        nodes [u].p = pt [mid] ;
        nodes [u].l = rebuild ( l , mid - 1 , k ^ 1 ) ;
        nodes [u].r = rebuild ( mid + 1 , r , k ^ 1 ) ;
        pushup ( u ) ;
        return u ;
    }
    void maintain ( ll & u , ll k )
    {
        if ( nodes [u].size * maxsz < nodes [nodes [u].l].size ||
            nodes [u].size * maxsz < nodes [nodes [u].r].size )
        {
            getseq ( u , 0 ) ;
            u = rebuild ( 1 , tot , k ) ;
        }
        return ;
    }
    void insert ( ll & u , point p , ll k )
    {
        if ( ! u )
        {
            u = add () ;
            nodes [u].p = p ;
            pushup ( u ) ;
            return ;
        }
        if ( ( k ? p.y <= nodes [u].p.y : p.x < nodes [u].p.x ) )
        {
            insert ( nodes [u].l , p , k ^ 1 ) ;
        }
        else
        {
            insert ( nodes [u].r , p , k ^ 1 ) ;
        }
        pushup ( u ) ;
        maintain ( u , k ) ;
    }
    bool In ( node t , ll x1 , ll y1 , ll x2 , ll y2 )
    {
        return t.minn [0] >= x1 && t.maxn [0] <= x2 && t.minn [1] >= y1 && t.maxn [1] <= y2 ;   
    }
    bool In ( point p , ll x1 , ll y1 , ll x2 , ll y2 )
    {
        return p.x >= x1 && p.x <= x2 && p.y >= y1 && p.y <= y2 ;
    }
    bool Out ( node t , ll x1, ll y1, ll x2, ll y2 ) 
    {
        return t.maxn[0] < x1 || t.minn [0] > x2 || t.maxn [1] < y1 || t.minn [1] > y2 ;    
    }
    ll query ( ll u , ll x1 , ll y1 , ll x2 , ll y2 )
    {
        if ( In ( nodes [u] , x1 , y1 , x2 , y2 ) )
        {
            return nodes [u].sum ;
        }
        if ( Out ( nodes [u] , x1 , y1 , x2 , y2 ) )
        {
            return 0 ; 
        }
        ll ans = 0 ;
        if ( In ( nodes [u].p , x1 , y1 , x2 , y2 ) )
        {
            ans += nodes [u].p.w ;
        }
        ans += query ( nodes [u].l , x1 , y1 , x2 , y2 ) +
               query ( nodes [u].r , x1 , y1 , x2 , y2 ) ;
        return ans ;
    }
} tree ;

void init ()
{
    tree.nodes [0].minn [0] = tree.nodes [0].minn [1] = N + 5 ;
    tree.nodes [0].maxn [0] = tree.nodes [0].maxn [1] = -1 ;
    return ;
}

ll n , ans = 0 ;

ll last_ans = 0 ;

int main ()
{
    // freopen ( ".in" , "r" , stdin ) ;
    // freopen ( ".out" , "w" , stdout ) ;
    ios::sync_with_stdio ( 0 ) ;
    cin.tie ( 0 ) ;
    cout.tie ( 0 ) ;
    cin >> n ;
    ll opt ;
    while ( cin >> opt , opt != 3 )
    {
        if ( opt == 1 )
        {
            ll x , y , k ;
            cin >> x >> y >> k ;
            x ^= last_ans ;
            y ^= last_ans ;
            k ^= last_ans ;
            tree.insert ( tree.root , point ( x , y , k ) , 0 ) ;
        }
        else
        {
            ll x1 , y1 , x2 , y2 ;
            cin >> x1 >> y1 >> x2 >> y2 ;
            x1 ^= last_ans , y1 ^= last_ans ;
            x2 ^= last_ans , y2 ^= last_ans ;
            last_ans = tree.query ( tree.root , x1 , y1 , x2 , y2 ) ;
            cout << last_ans << endl ;
        }
    }
    return 0 ;
}