Block Tree

#include <bits/stdc++.h>
#define MAX 100007
#define INF 1e9 + 7

using namespace std;
typedef pair<int, int> pii;

struct node{
    int val, lazy;
    node *p,  *s, *t, *q;

    node(){}
    node(int _val, int _lazy){
        val = _val;
        lazy = _lazy;
        p = NULL;
        s = NULL;
        t = NULL;
        q = NULL;
    }
};

node *bt;

bool check(pii x, pii y, pii w) {
    if (w.first >= x.first && w.first <= y.first
    && w.second >= x.second && w.second <= y.second) return true;
    return false;
}

void add(node *no, pii l, pii r, int val){
    no->lazy += val;
    no->val += val;
    //cout << "Update " << l.first << " " << l.second << " - " << r.first << " " << r.second << " with " << val*abs(r.second-r.first+1)*abs(l.second-l.first+1) << endl;
}

void dolazy(node *no, pii l, pii r){
    //cout << "do lazy\n";
    int mid1 = (l.first + r.first)/2;
    int mid2 = (l.second + r.second)/2;

    if(no->t == NULL) no->t = new node(0, 0);
    add(no->t, l, make_pair(mid1, mid2), no->lazy);
    if(no->p == NULL) no->p = new node(0, 0);
    add(no->p, make_pair(mid1+1, mid2+1), r, no->lazy);
    if(no->q == NULL) no->q = new node(0, 0);
    add(no->q, make_pair(mid1+1, l.second), make_pair(r.first, mid2), no->lazy);
    if(no->s == NULL) no->s = new node(0, 0);
    add(no->s, make_pair(l.first, mid2+1), make_pair(mid1, r.second), no->lazy);
    no->lazy = 0;
}

int cnt;
void update(node *no, pii l, pii r, pii x, pii y, int val){
    //cnt++;
    if( l.first > y.first || r.first < x.first ||
        l.second > y.second || r.second < x.second) {
        //cout << "First Carse\n";
        return;
    }else if(check(x, y, l) && check(x, y, r)){
        ///cout << "Second Carse\n";
        no->lazy += val;
        int calc = val;
        no->val += calc;
        //cout << "Update " << l.first << " " << l.second << " - " << r.first << " " << r.second << " with " << calc << endl;
    }else{
        //cout << "Third Carse\n";
        int mid1 = (l.first + r.first)/2;
        int mid2 = (l.second + r.second)/2;
        dolazy(no, l, r);

        update(no->t, l, make_pair(mid1, mid2), x, y, val);
        update(no->p, make_pair(mid1+1, mid2+1), r, x, y, val);
        update(no->q, make_pair(mid1+1, l.second), make_pair(r.first, mid2), x, y, val);
        update(no->s, make_pair(l.first, mid2+1), make_pair(mid1, r.second), x, y, val);

        no->val = min(no->p->val, min( no->s->val, min( no->t->val, no->q->val)));
    }
}

int query(node *no, pii l, pii r, pii x, pii y){
    if( l.first > y.first || r.first < x.first ||
        l.second > y.second || r.second < x.second) {
        //cout << "First Case\n";
        return INF;
    }else if(check(x, y, l) && check(x, y, r)) {
        //cout << "Second Case\n";
        return no->val;
    }else{
        //cout << "Third Case\n";
        int mid1 = (l.first + r.first)/2;
        int mid2 = (l.second + r.second)/2;
        dolazy(no, l, r);

        return min( min( min( query(no->t, l, make_pair(mid1, mid2), x, y) ,
               query(no->p, make_pair(mid1+1, mid2+1), r, x, y)),
               query(no->q, make_pair(mid1+1, l.second), make_pair(r.first, mid2), x, y)),
               query(no->s, make_pair(l.first, mid2+1), make_pair(mid1, r.second), x, y));
    }
}

pair<pii, pii> sq[MAX];
int main(){
    bt = new node(0,0);
    int q; scanf("%d", &q);
    int id = 1;
    while(q--){
        int tipo; scanf("%d", &tipo);
        if(tipo == 1){
            pii x, y; scanf("%d %d %d %d", &x.first, &x.second, &y.first, &y.second);
            sq[id++] = make_pair(x, y);
            //cnt = 0;
            update(bt, make_pair(0,0), make_pair(1000000007, 1000000007), x, y, 1);
            //cout << cnt << endl;
        }else if(tipo == 2){
            int i; scanf("%d", &i);
            id++;
            update(bt, make_pair(0,0), make_pair(50007, 50007), sq[i].first, sq[i].second, -1);
        }else{
            pii x, y; scanf("%d %d %d %d", &x.first, &x.second, &y.first, &y.second);
            int onlyx = query(bt, make_pair(0,0), make_pair(10007, 50007), x, x);
            int onlyy = query(bt, make_pair(0,0), make_pair(50007, 50007), y, y);
            int bigd  = query(bt, make_pair(0,0), make_pair(50007, 50007), x, y);
            //cout << onlyx << " " << onlyy << " " << bigd << endl;
            printf("%c", (onlyy == onlyx && onlyx == bigd)? 'Y':'N');
            id++;
        }
    }
    return 0;
}