[TIOJ] 1224. 矩形覆蓋面積計算

題目連結:http://tioj.infor.org/problems/1224

---

一個非常經典的掃描線應用，利用掃描線把原本二維的問題降成一維的，再搭配線段樹，就可以做到$O(n log n)$的複雜度，不過本題的線段樹要存的東東有點特別，我想了一段時間才寫出比較精簡的版本，不然我原本是寫讓他存區間和，可是這樣就會再詢問有幾個非空節點上有困難，所以不妨再存一個值紀錄當前非空節點有幾個，而顯然當你懶標記值大於0時整段都被覆蓋，所以就是整段的長度，而沒有整段被覆蓋的時候，那當然就是去看小孩的值囉，不過仔細想想就會發現區間和根本沒用，所以就砍掉他吧XDD

#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define PB push_back
typedef long long lld;
typedef pair<int, int> PII;
#define FF first
#define SS second

const int N = 1000000 + 5;

struct bian{
	PII pos;
	int cnt;
	bool operator<(const bian& a)const{
		return pos<a.pos;
	}
};
vector<pair<int,bian>> E;

class SegTree{
	private:
		struct Node{
			int len=0;
			int cnt=0;
		} arr[4*N];
		void pull(int id, int l, int r){
			if(arr[id].cnt) arr[id].len = r - l;
			else arr[id].len = (r - l)?\
				(arr[id*2+1].len+arr[id*2+2].len) :\
				0;
		}
	public:
		void modify(int l, int r,int ql, int qr, int c, int id){
			if(r <= ql) return;
			if(qr <= l) return;
			if(ql <= l and r <= qr){
				arr[id].cnt+=c;
			}else{
				int m = (l+r)>>1;
				modify(l, m, ql, qr, c, id*2+1);
				modify(m, r, ql, qr, c, id*2+2);
			}
			pull(id, l, r);
		}
		void modify(int l, int r, int c){
			modify(0, N, l, r, c, 0);
		}
		lld query(){
			return arr[0].len;
		}
} seg;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;cin>>n;
	for(int i=0;i<n;i++){
		int l, r, d, t;cin>>l>>r>>d>>t;
		E.PB({l, {{d, t}, 1}});
		E.PB({r, {{d, t}, -1}});
	}
	sort(ALL(E));
	int preX=0;
	lld ans=0;
	for(auto i:E){
		ans += seg.query() * (i.FF - preX);
		seg.modify(i.SS.pos.FF, i.SS.pos.SS, i.SS.cnt);
		preX = i.FF;
	}
	cout<<ans<<'\n';
	return 0;
}