yukicoder : No.1074 増殖

想定解と違う…。
https://yukicoder.me/problems/no/1074

問題

2次元座標において、原点を含むような、軸に平行な長方形がN個与えられる。
これらの領域の和集合を順次取るとき、面積の差分を求めよ。

解法

各象限についてみていく。
mapを使い凸包と面積を管理していくと、O(NlogN)で処理できる。
このテクは下記でも使用している。
Codeforces #419 Div1 D. Karen and Cards - kmjp's blog
JOI2011-2012 Day1 Fish 解説

class AreaRect {
	map<ll,ll> M;
public:
	ll sum;
	AreaRect() {
		M[0]=1LL<<60;
		M[1LL<<60]=0;
		sum=0;
	}
	void add(ll x,ll y) {
		auto k=M.lower_bound(x);
		if(k->second>=y) return;
		while(prev(M.lower_bound(x))->second<=y) {
			auto p=*prev(M.lower_bound(x));
			M.erase(p.first);
			sum-=(p.first-prev(M.lower_bound(p.first))->first)*(p.second-M.lower_bound(p.first)->second);
		}
		sum += (x-prev(M.lower_bound(x))->first)*(y-M.lower_bound(x)->second);
		M[x]=y;
	}
};

AreaRect M[4];

int N;
int X1,X2,Y1,Y2;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll pre=0;
	FOR(i,N) {
		cin>>X1>>Y1>>X2>>Y2;
		M[0].add(-X1,-Y1);
		M[1].add(-X1,Y2);
		M[2].add(X2,-Y1);
		M[3].add(X2,Y2);
		ll sum=M[0].sum+M[1].sum+M[2].sum+M[3].sum;
		cout<<sum-pre<<endl;
		pre=sum;
	}
}

まとめ

ライブラリ化しているので瞬殺でした。