TIOJ 1224 . 矩形覆蓋面積計算

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

typedef long long int int64;

struct bst{ // 0-base
    vector<int> ncnt;
    vector<int> cnt;
    vector<int> col;
    int base;
    bst(int n){
        base = (1<<(int)(ceil(log2(n+2))))-1;
        ncnt = vector<int>(2*base+2, 0);
        cnt = vector<int>(2*base+2, 0);
        col = vector<int>(2*base+2, 0);
        for(int lx = 0;lx < n;lx++) cnt[base+lx+2] = 1;
        for(int lx = base;lx;lx--) cnt[lx] = cnt[lx<<1] + cnt[(lx<<1)^1];
        return;
    }

    void modify(int a, int b, int v){
        int nodes[30]; int nc = 0;
        for(a+=base+1, b+=base+3; a^b^1;a>>=1, b>>=1){
            if(~a&1) nodes[nc++] = a^1;
            if(b&1) nodes[nc++] = b^1;
        }
        for(int lx = 0;lx < nc;lx++){
            int nd = nodes[lx];
            //printf("%d -> %d\n", nd, v);
            ncnt[nd] += v;
            if(ncnt[nd] == 0){
                // 1->0
                int det = cnt[nd]-col[nd];
                for(int prc = nd>>1;prc;prc>>=1){
                    col[prc] -= det;
                    if(ncnt[prc]) break;
                }
            }else if(ncnt[nd] == 1 and v == 1){
                // 0->1
                int det = cnt[nd]-col[nd];
                for(int prc = nd>>1;prc;prc>>=1){
                    col[prc] += det;
                    if(ncnt[prc]) break;
                }
            }
        }
        return;
    }

    int query()const{
        return col[1];
    }
};

struct qry{int l, r, v, x; qry(int _l = 0, int _r = 0, int _v = 0, int _x = 0):l(_l),r(_r),v(_v),x(_x){return;}}qrys[200000];
bool operator<(const qry& a, const qry& b){return a.x < b.x;}

int main(){
    int n; scanf("%d", &n);
    for(int lx = 0;lx < n;lx++){
        int l, r, d, u; scanf("%d %d %d %d", &l, &r, &d, &u);
        qrys[lx<<1] = qry(d,u-1,1,l);
        qrys[(lx<<1)^1] = qry(d,u-1,-1,r);
    }
    sort(qrys, qrys+2*n);
    int64 ans = 0;
    int org = 0;
    bst BST(1000000);
    for(int lx = 0;lx < 2*n;lx++){
        //printf("%d %d %d %d\n", qrys[lx].x, qrys[lx].l, qrys[lx].r, qrys[lx].v);
        ans += ((int64)BST.query())*((int64)(qrys[lx].x-org));
        //printf("%lld\n", ans);
        org = qrys[lx].x;
        BST.modify(qrys[lx].l, qrys[lx].r, qrys[lx].v);
    }
    printf("%lld\n", ans);
    return 0;
}