Code-chef-QRECT.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cassert>
using namespace std;
typedef long long LL;
const int N = 100005;
int Q , n , P , m;
int X1[N], Y1[N] , X2[N] , Y2[N];
pair<int , int> q[N];
int ans[N] , d[N << 1] , Dx , Dy;
int c[4][N << 1];

void init() {
    char s[10];
    scanf("%d",&Q);
    for (int i = 0 ; i < Q ; ++ i) {
        scanf("%s", s);
        if (*s == 'I' || *s == 'Q') {
            scanf("%d%d%d%d",&X1[n] , &Y1[n] , &X2[n] , &Y2[n]);
            n ++;
        }
        if (*s == 'I')
            q[i] = make_pair(0 , n - 1);
        if (*s == 'Q') {
            ++ P;
            ans[P] = n - P - m;
            q[i] = make_pair(-P , n - 1);
        }
        if (*s == 'D') {
            q[i].first = 1 , ++ m;
            scanf("%d" , &q[i].second);
            -- q[i].second;
        }
    }
    for (int i = 0 ; i < n ; ++ i) {
        d[Dx ++] = X1[i];
        d[Dx ++] = X2[i];
    }
    sort(d , d + Dx);
    Dx = unique(d , d + Dx) - d;
    for (int i = 0 ; i < n ; ++ i) {
        X1[i] = lower_bound(d , d + Dx , X1[i]) - d + 1;
        X2[i] = lower_bound(d , d + Dx , X2[i]) - d + 1;
    }
    for (int i = 0 ; i < n ; ++ i) {
        d[Dy ++] = Y1[i];
        d[Dy ++] = Y2[i];
    }
    sort(d , d + Dy);
    Dy = unique(d , d + Dy) - d;
    for (int i = 0 ; i < n ; ++ i) {
        Y1[i] = lower_bound(d , d + Dy , Y1[i]) - d + 1;
        Y2[i] = lower_bound(d , d + Dy , Y2[i]) - d + 1;
    }

    for (int i = 0 ; i < Q ; ++ i) {
        int k = q[i].second;
        if (q[i].first == 0) {
            for (int j = X2[k] ; j <= Dx ; j += j & -j) ++ c[0][j];
            for (int j = Y1[k] ; j > 0   ; j -= j & -j) ++ c[1][j];
            for (int j = Y2[k] ; j <= Dy ; j += j & -j) ++ c[2][j];
            for (int j = X1[k] ; j > 0   ; j -= j & -j) ++ c[3][j];
        } else if (q[i].first == 1) {
            for (int j = X2[k] ; j <= Dx ; j += j & -j) -- c[0][j];
            for (int j = Y1[k] ; j > 0   ; j -= j & -j) -- c[1][j];
            for (int j = Y2[k] ; j <= Dy ; j += j & -j) -- c[2][j];
            for (int j = X1[k] ; j > 0   ; j -= j & -j) -- c[3][j];
        } else {
            int& res = ans[-q[i].first];
            for (int j = X1[k] - 1 ; j > 0   ; j -= j & -j) res -= c[0][j];
            for (int j = Y2[k] + 1 ; j <= Dy ; j += j & -j) res -= c[1][j];
            for (int j = Y1[k] - 1 ; j > 0   ; j -= j & -j) res -= c[2][j];
            for (int j = X2[k] + 1 ; j <= Dx ; j += j & -j) res -= c[3][j];
        }
    }
}

int root[N << 1];
const int M = 4000005;
struct Treap {
    int nodecnt , prior[M];
    int cnt[M] , size[M] , c[M][2];
    int key[M];
    void clear() {
        nodecnt = 1;
        prior[0] = -1 << 30;
        c[0][0] = c[0][1] = 0;
        key[0] = cnt[0] = size[0] = 0;
    }
    Treap () {
        clear();
    }
    inline void pushup(int p) {
        size[p] = size[c[p][0]] + size[c[p][1]] + cnt[p];
    }
    inline void rotate (int& x , int t) {
        int y = c[x][t];
        c[x][t] = c[y][!t] , c[y][!t] = x;
        pushup(x) , pushup(y) , x = y;
    }
    inline void newnode(int& p , int w) {
        p = nodecnt ++;
        key[p] = w , cnt[p] = size[p] = 1;
        prior[p] = rand() << 15 | rand(), c[p][0] = c[p][1] = 0;
    }
    void insert(int& p , int w) {
        if (!p) {
            newnode(p , w);
            return;
        }
        if (key[p] == w)
            ++ cnt[p];
        else {
            int t = key[p] < w;
            insert(c[p][t] , w);
            if (prior[c[p][t]] > prior[p])
                rotate(p , t);
        }
        pushup(p);
    }
    void erase(int& p , int w) {
        if (!p) return;
        if (key[p] == w) {
            if (cnt[p] == 1) {
                if (!c[p][0] && !c[p][1])
                    p = 0;
                else {
                    rotate(p , prior[c[p][0]] < prior[c[p][1]]);
                    erase(p , w);
                }
            } else
                -- cnt[p];
        } else
            erase(c[p][key[p] < w] , w);
        pushup(p);
    }
    int query(int p , int x) {
        if (!p) return 0;
        if (key[p] > x)
            return query(c[p][0] , x);
        return query(c[p][1] , x) + cnt[p] + size[c[p][0]];
    }
};
Treap T;
void solve(int *X , int *Y , int *x , int *y) {
    memset(root , 0 , sizeof(root));
    T.clear();
    for (int i = 0 ; i < Q ; ++ i) {
        int k = q[i].second;
        if (q[i].first == 0) {
            for (int j = X[k] ; j <= Dx ; j += j & -j)
                T.insert(root[j] , Y[k]);
        } else if (q[i].first == 1) {
            for (int j = X[k] ; j <= Dx ; j += j & -j)
                T.erase(root[j] , Y[k]);
        } else {
            int& res = ans[-q[i].first];
            for (int j = x[k] - 1 ; j > 0 ; j -= j & -j)
                res += T.query(root[j] , y[k] - 1);
        }
    }
}

void work() {
    solve(X2 , Y2 , X1 , Y1);
    for (int i = 0 ; i < n ; ++ i) {
        Y1[i] = Dy - Y1[i] + 1;
        Y2[i] = Dy - Y2[i] + 1;
    }
    solve(X2 , Y1 , X1 , Y2);
    for (int i = 0 ; i < n ; ++ i) {
        Y1[i] = Dy - Y1[i] + 1;
        Y2[i] = Dy - Y2[i] + 1;
        X1[i] = Dx - X1[i] + 1;
        X2[i] = Dx - X2[i] + 1;
    }
    solve(X1 , Y2 , X2 , Y1);
    for (int i = 0 ; i < n ; ++ i) {
        Y1[i] = Dy - Y1[i] + 1;
        Y2[i] = Dy - Y2[i] + 1;
    }
    solve(X1 , Y1 , X2 , Y2);
    for (int i = 1 ; i <= P ; ++ i)
        printf("%d\n" , ans[i]);
}

int main() {
    init();
    work();
    return 0;
}