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内存后崩溃了,,