MLE and RE 求条

P4148 简单题

bsdsdb @ 2024-11-23 19:20:34

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
// using namespace __gnu_pbds;
// tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>T;
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ldb;
//#define umap unordered_map
#define umap __gnu_pbds::cc_hash_table
#define mkp make_pair
#define prque priority_queue
#define emp emplace
#define empb emplace_back
#define empf emplace_front
random_device rndv;
mt19937 rd(rndv());
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const double eps = 1e-8;
inline void enter(){putchar('\n');}
inline void space(){putchar(' ');}
inline ll readll(){ll ret=0,k=1;char c;do{c=getchar();if(c=='-'){k=-1;}}while(('0'>c)|('9'<c));do{ret=(ret<<3)+(ret<<1)+c-48;c=getchar();}while(('0'<=c)&(c<='9'));return ret*k;}
inline void read(ll&x){x=readll();}
inline char readchar(){char ret;do{ret=getchar();}while(ret<=32);return ret;}
inline void read(char&x){x=readchar();}
inline string readstr(){string ret;char c;do{c=getchar();}while(c<=32);do{ret+=c;c=getchar();}while((c>32)&(c!=EOF));return ret;}
inline void read(string&x){x=readstr();}
inline void write(ll x){if(!x){putchar('0');return;}if(x<0){putchar('-');x*=-1;}char op[20]={};ll cur=0;while(x){op[++cur]=x%10+48;x/=10;}while(cur){putchar(op[cur--]);}}
inline ostream& operator<<(ostream& out, __int128 x){if(!x){out<<"0";return out;}if(x<0){out<<"-";x*=-1;}char op[40]={};ll cur=0;while(x){op[++cur]=x%10+48;x/=10;}while(cur){out<<op[cur--];}return out;}
// -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#define axis array<ll, 2>
#define log22(x) (63-__builtin_clzll(x))
struct KDTNode {
    ll l, r, val, sum, id;
    axis pos, mnp, mxp;
    KDTNode() {
        l = r = id = val = sum = 0;
        mnp = {inf, inf}, mxp = {~inf, ~inf};
    }
    KDTNode(axis p, ll v, ll i) {
        l = r = 0;
        id = i;
        val = sum = v;
        pos = mnp = mxp = p;
    }
};
struct KDT {
    ll size = 0, rt = 0;
    vector<KDTNode> node{1};
    void clear() {
        size = rt = 0;
        node.clear();
        node.shrink_to_fit();
        node = vector<KDTNode>(1);
    }
    bool empty() {
        return !size;
    }
    void pushup(ll x) {
        node[x].sum = node[node[x].l].sum + node[x].val + node[node[x].r].sum;
        for (ll k = 0; k < 2; ++k) {
            node[x].mnp[k] = min({node[node[x].l].mnp[k], node[x].pos[k], node[node[x].r].mnp[k]});
            node[x].mxp[k] = max({node[node[x].l].mxp[k], node[x].pos[k], node[node[x].r].mxp[k]});
        }
    }
    #define vit vector<KDTNode>::iterator
    void build(ll& x, vit bg, vit ed) {
        if (bg == ed) {
            return;
        }
        if (!x) {
            x = ++size;
            node.empb(KDTNode());
        }
        ll curdim = rd() % 2;
        vit mid = bg + (ed - bg) / 2;
        nth_element(bg, mid, ed, [&](KDTNode xx, KDTNode y)->bool {
            return mkp(xx.pos[curdim], xx.id) < mkp(y.pos[curdim], y.id);
        });
        node[x] = *mid;
        build(node[x].l, bg, mid);
        build(node[x].r, mid + 1, ed);
        pushup(x);
    }
    void getall(ll x, vector<KDTNode>& ret) {
        if (!x) {
            return;
        }
        ret.empb(node[x]);
        getall(node[x].l, ret);
        getall(node[x].r, ret);
    }
    bool bujiao(axis l1, axis r1, axis l2, axis r2) {
        for (ll k = 0; k < 2; ++k) {
            if (r1[k] < l2[k] || r2[k] < l1[k]) {
                return 1;
            }
        }
        return 0;
    }
    bool baohan(axis l1, axis r1, axis l2, axis r2) {
        for (ll k = 0; k < 2; ++k) {
            if (!(l1[k] <= l2[k] && r2[k] <= r1[k])) {
                return 0;
            }
        }
        return 1;
    }
    ll qry(ll x, axis l, axis r) {
        if (!x) {
            return 0;
        }
        if (bujiao(l, r, node[x].mnp, node[x].mxp)) {
            return 0;
        }
        if (baohan(l, r, node[x].mnp, node[x].mxp)) {
            return node[x].sum;
        }
        return (baohan(l, r, node[x].pos, node[x].pos) ? node[x].val : 0) +
            qry(node[x].l, l, r) + qry(node[x].r, l, r);
    }
};
struct KDT_bg {
    KDT bg[25] = {};
    void insert(KDTNode x) {
        vector<KDTNode> cur = {x};
        KDT nw;
        nw.build(nw.rt, cur.begin(), cur.end());
        ll curind = 0;
        while (!bg[log22(nw.size)].empty()) {
            curind = log22(nw.size);
            vector<KDTNode> al;
            nw.getall(nw.rt, al);
            nw.clear();
            bg[curind].getall(bg[curind].rt, al);
            bg[curind].clear();
            nw.build(nw.rt, al.begin(), al.end());
            curind = log22(nw.size);
        }
        bg[curind] = nw;
    }
    ll qry(axis l, axis r) {
        ll ret = 0;
        for (ll i = 0; i <= 20; ++i) {
            if (!bg[i].empty()) {
                ret += bg[i].qry(bg[i].rt, l, r);
            }
        }
        return ret;
    }
} kdt;

ll n, last = 0;

int main() {
    read(n);
    ll i = 0;
    while (1) {
        ++i;
        ll o, x, y, k, xx, yy;
        read(o);
        if (o == 1) {
            read(x), read(y);
            x ^= last, y ^= last;
            read(k);
            k ^= last;
            kdt.insert(KDTNode({x, y}, k, i));
        } else if (o == 2) {
            read(x), read(y);
            x ^= last, y ^= last;
            read(xx), read(yy);
            xx ^= last, yy ^= last;
            axis l = {x, y}, r = {xx, yy};
            last = kdt.qry(l, r);
            write(last), enter();
        } else {
            return 0;
        }
    }
    return 0;
}

;             ;;;;;;;;;;;         ;
;                      ;         ; ;
;                    ;          ;   ;
;                   ;          ;     ;
;                 ;           ;;;;;;;;;
;               ;            ;         ;
;              ;            ;           ;
;;;;;;;;;;;   ;;;;;;;;;;   ;             ;

   ;                        ;
  ;                          ;
 ;                            ;
;                              ;
;                              ;
;                              ;
 ;                            ;
  ;         ;;          ;;   ;
   ;        ;;          ;;  ;

  ;  ;  ;;; ;;;  ;   ;   ;  ;;  ;;  ;;; 
; ; ; ;  ;  ; ; ; ; ; ; ; ; ;;  ; ; ; ;  ;   ;
;;; ; ;  ;  ; ;   ; ; ;   ; ;;  ; ; ; ;  ;   ;
;;; ; ;  ;  ;;   ;  ; ;  ;  ;;  ;;  ;;  ;;; ;;;
;;; ; ;  ;  ;   ;   ; ; ;   ;;; ;;  ;    ;   ;
; ; ; ;  ;  ;   ; ; ; ; ; ;  ;  ; ; ;    ;   ;
;    ;  ;;; ;   ;;;  ;  ;;;  ;  ; ; ;

在本地搞了个n1000q3000的数据,然后用了6GB内存后崩溃了,,


|