Codeforces #419 Div1 D. Karen and Cards

方針は浮かんだけどそのデータ構造書いたことなかった。
http://codeforces.com/contest/815/problem/D

問題

3種のパラメータを持つカード群がある。
各パラメータはそれぞれ[1,P],[1,Q],[1,R]の範囲の値を取るので、計P*Q*R種類通りのパラメータが考えられる。

2つのカードで対戦するとき、2種類以上のパラメータが相手のカードを上回るならばそのカードが勝ちとなる。
N枚のカードとそのパラメータ(A[i],B[i],C[i])が与えられる。全カードに勝てるカードのパラメータは何通りあるか。

解法

3種のパラメータが張る3次元の空間座標を考える。
カード(A[i],B[i],C[i])に勝てないパラメータは、下記3つの直方体の和集合である。

• (0,0,0)-(A[i],B[i],R)を頂点とする軸に平行な直方体
• (0,0,0)-(A[i],Q,C[i])　〃
• (0,0,0)-(P,B[i],C[i])　〃

求めたいのは全カードに勝てるパラメータなので、全カードにおける上記直方体群の和集合中のパラメータの組み合わせを求め、P*Q*Rから引けばよい。

直方体の和集合の体積を求めるテクは、過去JOIで出たらしく、「JOI fish 2012」あたりで検索するといくつか情報が出てくる。
特にわかりやすいのはこちら。SegTreeに言及している記事もあるが、map1個で処理できる。
JOI2011-2012 Day1 Fish 解説

いきなり3次元で考えるのではなく、XY座標における長方形の和集合を、Z軸の大きい方から走査していくと考えるとよい。
長方形の和集合の面積は、長方形の角の座標をmapで管理しておけばよい。

class AreaRect { //(0,0)-(X,Y)の矩形の面積の総和
	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;
	}
};

int N,AA,BB,CC;
vector<pair<int,int>> add[505050];
AreaRect AR;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>AA>>BB>>CC;
	FOR(i,N) {
		int a,b,c;
		cin>>a>>b>>c;
		add[AA].push_back({b,c});
		add[a].push_back({BB,c});
		add[a].push_back({b,CC});
	}
	
	ll ret=0;
	for(x=AA;x>=1;x--) {
		FORR(e,add[x]) AR.add(e.first,e.second);
		ret += 1LL*BB*CC-AR.sum;
	}
	
	cout<<ret<<endl;
	
}

まとめ

長方形の和集合の面積、こんな短いコードで書けるのね…。