Area intersected by exactly k rectangles

#include <bits/stdc++.h>
#define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
using namespace std;

const int maxn = 1e5 + 10;
const int maxk = 55;
const int MOD = 1e9 + 7;
struct EVENT{
    int x;
    int y1;
    int y2;
    int type;
};
//Các sự kiện sweepline gồm tọa độ x, độ dài y1, y2, và kiểu sự kiện
//đóng hay mở một đoạn thẳng

bool comp(EVENT& A, EVENT& B){
    if (A.x == B.x) return A.type > B.type;
    return A.x < B.x;
}
//Xử lý các sự kiện x trước
vector<EVENT> events;



vector<int> tempY;
int n, k, treesize;
long long T[maxk+1][maxn << 3];
int delta[maxn << 3];
// T[j][nod]: Tổng chiều dài (trên trục Y) nằm trọn vẹn trong khoảng quản lý của nod, bị phủ ÍT NHẤT j lần bởi những lần cập nhật đoạn thẳng được ghi nhận tại chính nod (delta[nod]) và các nút con cháu của nó
// delta[nod]: Số lần toàn đoạn [l,r] bị phủ đang được quản lý bởi nod
//maxn << 1 cho số lượng sự kiện tối đa có thể xảy ra (1 mở và 1 đóng)
//maxn << 3 cho ước lượng segment tree trên toàn sự kiện
//maxk+1 để tránh tràn mảng vì phải lấy T(k) - T(k+1)



void push_up(int nod, int l, int r){
    int len = tempY[r+1] - tempY[l];
    int d = delta[nod];

    if (d >= k+1){
        up(j,1,k+1) T[j][nod] = len;
        return;
    }
    // Ngay cả khi bỏ qua con, delta đã đủ >= k+1 lần → mọi ngưỡng đều đạt

    if (l == r){
        up(j,1,k+1) T[j][nod] = (d >= j) ? len : 0;
        return;
    }
    // leaf


    up(j,1,k+1){
        if (j <= d) T[j][nod] = len;
        else{
            int need = j - d;
            // đã đóng góp được d lần thì cần đóng góp thêm j-d lần nữa
            T[j][nod] = T[need][nod*2] + T[need][nod*2+1];
        }
    }
}
//Nếu "khoảng" [l, r] bị bao hoàn toàn thì lấy toàn bộ
//Nếu "khoảng" [l, r] chỉ bị bao một phần và không phải nút lá thì cập nhật dựa theo con
//Nếu "khoảng" lá không bị bao thì phải bằng 0
//Chú ý: nếu không có điều kiện (l != r) thì segment tree có thể lấy T[nod*2] với nod*2 là chỉ số tràn ngoài phạm vi đã khai báo
//Chú ý: delta không bao giờ đẩy xuống nút con



void update(int nod, int l, int r, int u, int v, int val){
    if (r < u || l > v) return;
    if (l >= u && r <= v){
        delta[nod] += val;
        push_up(nod, l, r);
        return;
    }
    int mid = (l+r) >> 1;
    update(nod*2, l, mid, u, v, val);
    update(nod*2+1, mid+1, r, u, v, val);
    push_up(nod, l, r);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    up(i,1,n){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        tempY.push_back(y1);
        tempY.push_back(y2);
        events.push_back({x1, y1, y2, 1});
        events.push_back({x2, y1, y2, -1});
    }

    tempY.push_back(-MOD);
    sort(tempY.begin(), tempY.end());
    tempY.resize(unique(tempY.begin(), tempY.end()) - tempY.begin());
    treesize = tempY.size()-1;
//    tempY thêm phần tử -MOD để lấy lowerbound với chỉ số bắt đầu từ 1
//    treesize = tempY.size()-1 vì phải bỏ qua phần tử -MOD;


    sort(events.begin(), events.end(), comp);

    long long res = 0;
    for (int i = 0; i < (int)(events.size()-1); i++){
        int u = lower_bound(tempY.begin(), tempY.end(), events[i].y1) - tempY.begin();
        int v = lower_bound(tempY.begin(), tempY.end(), events[i].y2) - tempY.begin();


        update(1, 1, treesize-1, u, v-1, events[i].type);
        // Đúng k lần = (>= k) - (>= k+1)
        res += 1ll*(T[k][1] - T[k+1][1]) * 1ll*(events[i+1].x - events[i].x);

//        Segment tree quản lý các "khoảng" giữa tọa độ điểm này và tọa độ điểm kia
//        có treesize tọa độ điểm thì có treesize-1 "khoảng"
//        Tại mỗi nút chỉ số v quản lý khoảng [l, r], lấy kết quả nút nếu bị bao toàn bộ là tempY[r+1] - tempY[l]
//        Do đó, mỗi lần lấy kết quả trong tọa độ [u, v] thì lấy kết quả trên "khoảng" [u, v-1] trên segment tree
    }
    cout << res;
}








//#include <bits/stdc++.h>
//#define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
//using namespace std;
//
//int n, k;
//map<pair<int, int>, int> a;
//// Lưu số lần bị phủ của từng ô vuông đơn vị 1x1
//
//signed main(){
//    ios_base::sync_with_stdio(false);
//    cin.tie(0);
//    #define Task "A"
//    if (fopen(Task".inp", "r")){
//        freopen(Task".inp", "r", stdin);
//        freopen(Task".out", "w", stdout);
//    }
//
//    cin >> n >> k;
//    up(i, 1, n){
//        int x1, y1, x2, y2;
//        cin >> x1 >> y1 >> x2 >> y2;
//        // x từ x1 đến x2-1 đại diện cho các ô vuông trên trục X
//        up(x, x1, x2-1){
//            up(y, y1, y2-1){
//                a[make_pair(x, y)]++;
//            }
//        }
//    }
//
//    int cnt = 0;
//    for (auto it : a){
//        if (it.second == k) {
//            cnt++;
//        }
//    }
//    cout << cnt << "\n";
//
//
////    down(j,maxy,-maxy){
////        up(i,-maxx,maxx){
////            cout << a[make_pair(i, j)] << " ";
////        }
////        cout << "\n";
////    }
//}