Yosupo Wettbewerb : D : Japanese Origami No.1

やはりWriterも言っている通りDが一番難しい。
http://kcs.miz-miz.biz/contest/1027/view/D

問題

無限に広い２次元平面に置いて、N個の塗りつぶりクエリ(L[i],R[i],H[i])が与えられる。
各クエリiでは、順に(L[i],0)-(R[i],H[i])の矩形を異なる色で塗りつぶす。
(下に別の矩形があった場合、上書きする)

その後、M個の調査クエリ(P[j])が与えられる。
各クエリjでは、直線x=P[j]と重なる矩形の色の数を答えよ。

解法

平方探索解法とSegTree解法がある。
自分はWriter解をほぼ写経。
Yosupo Wettbewerb 解説 - よすぽの日記

まずL[i],R[i],P[i]をソートして、x軸の小さい順に処理をしていく。
L[i]に遭遇すると、新規に矩形を上書きすることになる。
これを２次元座標上で(i,H[i])にプロットすることに相当すると考える。
逆にR[i]では(i,H[i])の点を消すことに相当すると考える。

P[i]のクエリは、これらのプロット済み頂点群に対し、左上から右下に向け階段状にこれらの点をつないだときの頂点数を求める問題となる。

これは以下の３要素を持つSegTreeを処理することで解決できる。

• 区間内の高さの最大値
• 区間の左半分における階段状の頂点数
• 区間の右半分における階段状の頂点数

SegTreeの更新では、区間の右半分の高さの最大値vを用いて、左半分における階段状の頂点のうちvを超える数を二分探索でカウントする、という処理を行うと良い。
1クエリの処理がO(log^2N)という珍しい問題。

template<class V,int NV> class SegTree_Stair {
public:
	vector<V> val,lcnt,cnt;
	SegTree_Stair(){val=vector<V>(NV*2,-1);lcnt=cnt=vector<V>(NV*2,0);};
	int find(int e,V v) {
		if(e>=NV) return val[e]>v;
		if(v>val[e*2+1]) return find(e*2,v);
		return lcnt[e]+find(e*2+1,v);
	}
	
	void update(int e, V v) {
		e += NV;
		val[e]=v;
		lcnt[e]=0;
		cnt[e]=(v>=0);
		while(e>1) {
			e>>=1;
			val[e]=max(val[e*2],val[e*2+1]);
			lcnt[e]=find(e*2, val[e*2+1]);
			cnt[e]=lcnt[e] + cnt[e*2+1];
		}
	}
};

int N,M;
int L[201000],R[201000],H[201000];
int P[201000],res[201000];
int ev[401000];

SegTree_Stair<int,1<<18> seg;


void solve() {
	int i,j,k,l,r,x,y; string s;
	MINUS(ev);
	
	cin>>N;
	FOR(i,N) cin>>L[i]>>R[i]>>H[i], ev[L[i]]=ev[R[i]]=i;
	
	cin>>M;
	FOR(i,M) cin>>P[i], ev[P[i]]=i;
	
	FOR(i,401000) if(ev[i]!=-1) {
		if(L[ev[i]]==i) seg.update(ev[i],H[ev[i]]);
		if(R[ev[i]]==i) seg.update(ev[i],-1);
		if(P[ev[i]]==i) res[ev[i]] = seg.cnt[1];
	}
	FOR(i,M) _P("%d\n",res[i]);
}

まとめ

本番区間をどううまく処理してよいかわからなかったが、これは面白いやり方。