【範例】掃描線(線段樹實作)
【題目敘述】https://tioj.ck.tp.edu.tw/problems/1224
#include <bits/stdc++.h>
using namespace std;
int n, st[1000005<<2], lazy[1000005<<2];
vector <tuple<int, int, int, int>> v;
void push_up(int x, int l, int r){
if (lazy[x]) st[x] = r-l+1;
else if (r != l) st[x] = st[x<<1] +st[x<<1|1];
else st[x] = 0;
}
void update(int x, int l, int r, int ul, int ur, int d){
if (ul <= l && r <= ur){
lazy[x] += d;
push_up(x, l, r);
return;
}
int mid = (l+r)/2;
if (ul <= mid) update(x<<1, l, mid, ul, ur, d);
if (mid < ur) update(x<<1|1, mid+1, r, ul, ur, d);
push_up(x, l, r);
}
int main(){
cin >> n;
int l, r, d, u;
for (int i = 0; i < n; i++){
cin >> l >> r >> d >> u;
v.push_back({l, d+1, u, 1});
v.push_back({r, d+1, u, -1});
}
sort(v.begin(), v.end());
int pre = 0;
long long ans = 0;
for (auto [pos, d, u, del]:v){
if (pos != pre){
ans += 1LL*(pos-pre)*st[1];
pre = pos;
}
update(1, 1, 1000000, d, u, del);
}
cout << ans << "\n";
}