bzoj4066.cc

#include #include #include

using namespace std;

#define upMax(a,b) {
if (a < b)
a = b;
} #define upMin(a,b) {
if (a > b)
a = b;
}

struct kdnode { int p[2], a[2][2], v, s; kdnode *ch[2]; inline void update() { a[0][0] = a[1][0] = p[0]; a[0][1] = a[1][1] = p[1]; s = v; if (ch[0]) { upMin(a[0][0], ch[0]-> a[0][0]); upMin(a[0][1], ch[0]-> a[0][1]); upMax(a[1][0], ch[0]-> a[1][0]); upMax(a[1][1], ch[0]-> a[1][1]); s += ch[0]-> s; } if (ch[1]) { upMin(a[0][0], ch[1]-> a[0][0]); upMin(a[0][1], ch[1]-> a[0][1]); upMax(a[1][0], ch[1]-> a[1][0]); upMax(a[1][1], ch[1]-> a[1][1]); s += ch[1]-> s; } } };

const int maxn = 200009;

int n, lans, qa[2], qb[2], qv, cmpx; kdnode nbuf_arr[maxn], *nbuf(nbuf_arr), *krt;

inline bool xCmp(int* a, int* b) { if (a[cmpx] == b[cmpx]) return a[cmpx ^ 1] < b[cmpx ^ 1]; else return a[cmpx] < b[cmpx]; }

kdnode* kdIns(kdnode* p) { cmpx ^= 1; if (!p) { p = nbuf ++; p-> p[0] = qa[0], p-> p[1] = qa[1]; p-> v = p-> s = qv; p-> ch[0] = p-> ch[1] = 0; } else if (qa[0] == p-> p[0] && qa[1] == p-> p[1]) { p-> v += qv; p-> s += qv; } else { int d(xCmp(qa, p-> p) ^ 1); p-> ch[d] = kdIns(p-> ch[d]); } p-> update(); cmpx ^= 1; return p; }

inline bool outRect(kdnode* p) { return qa[0] > p-> a[1][0] || qa[1] > p-> a[1][1] || qb[0] < p-> a[0][0] || qb[1] < p-> a[0][1]; } inline bool inRect(kdnode* p) { return qa[0] <= p-> a[0][0] && qa[1] <= p-> a[0][1] && qb[0] >= p-> a[1][0] && qb[1] >= p-> a[1][1]; }

void kdQry(kdnode* p) { if (!p || outRect(p)) return; else if (inRect(p)) qv += p-> s; else { if (p-> p[0] >= qa[0] && p-> p[0] <= qb[0] && p-> p[1] >= qa[1] && p-> p[1] <= qb[1]) qv += p-> v; kdQry(p-> ch[0]), kdQry(p-> ch[1]); } }

int main() { #ifndef ONLINE_JUDGE freopen(".in", “r”, stdin); #endif

cmpx = 0;
scanf("%d", &n);
krt = 0;
lans = 0;
for (int opt; scanf("%d", &opt), opt < 3; )
    if (opt == 1) {
        scanf("%d%d%d", qa, qa + 1, &qv);
        qa[0] ^= lans, qa[1] ^= lans, qv ^= lans;
        krt = kdIns(krt);
    }
    else {
        scanf("%d%d%d%d", qa, qa + 1, qb, qb + 1);
        qa[0] ^= lans, qa[1] ^= lans;
        qb[0] ^= lans, qb[1] ^= lans;
        qv = 0;
        kdQry(krt);
        printf("%d\n", (lans = qv));
    }

}

Comments