【題目敘述】https://vjudge.net/problem/HDU-1255
【解題想法】線段樹
#include <bits/stdc++.h>
using namespace std;
int t, n, lazy[10005<<2];
double st1[10005<<2], st2[10005<<2];
vector <tuple<double, double, double, int>> v;
vector <double> id;
int get_id(double x){
return lower_bound(id.begin(), id.end(), x)-id.begin();
}
void push_up(int x, int l, int r){
if (lazy[x] >= 2) st2[x] = id[r]-id[l-1];
else if (lazy[x] == 1) st2[x] = st1[x<<1] + st1[x<<1|1];
else if (r != l) st2[x] = st2[x<<1] +st2[x<<1|1];
else st2[x] = 0;
if (lazy[x]) st1[x] = id[r]-id[l-1];
else if (r != l) st1[x] = st1[x<<1] +st1[x<<1|1];
else st1[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 >> t;
while (t--){
cin >> n;
double l, r, d, u;
id.clear();
v.clear();
for (int i = 0; i < n; i++){
cin >> l >> d >> r >> u;
id.push_back(d);
id.push_back(u);
v.push_back(make_tuple(l, d, u, 1));
v.push_back(make_tuple(r, d, u, -1));
}
sort(id.begin(), id.end());
id.erase(unique(id.begin(), id.end()), id.end());
sort(v.begin(), v.end());
double pre = 0, ans = 0;
for (auto i:v){
double pos = get<0>(i), d = get<1>(i), u = get<2>(i);
int del = get<3>(i);
if (pos != pre){
ans += (pos-pre)*st2[1];
pre = pos;
}
update(1, 1, id.size()-1, get_id(d)+1, get_id(u), del);
}
printf("%.2f\n", ans);
}
}