2016-2017 National Taiwan University World Final Team Selection Contest: E. Lines Game

セグメント木にそんな使い方があったのかと驚かされた問題

問題概要
Problem - E - Codeforces

まず，解法を思いつかないとどうしようもないので、いろいろ考える。
線分が交わらない線分はどういう条件かを考える．

上の図を眺めると、交わらない線分は以下の条件のどちらかを満たす必要がある。

• かつ
• かつ

つまり、全ての線分を取り除くような線分の選び方は、 について単調増加するように並べると、 についても単調増加することがわかる．
そう考えると、増加列によくあるDPのように更新できると思いきや、こんな条件で更新しないといけません。
if かつ かつ 次の条件 かつ を満たすkが存在しない。
を追加しておいて、dp[n+1] を求めるのが楽です。
ここで、 とします。
解法であるならば、yの降順にみていきつつ、今までチェックしたxより現在のxが大きい時だけ更新すればそれで良いです。
(他にも解法はありますが、この解法の方が後々の高速化で説明しやすいのであえて選んでいます。)

const int inf = 2e9 + 10;
const int limit = 100010;
int n,dp[limit],cost[limit];

cin >> n;

rep(i,n) cin >> perm[i + 1], inv[perm[i+1]] = i + 1;
rep(i,n) cin >> cost[i + 1];

perm[0] = 0, inv[0] = 0, cost[0] = 0;
perm[n + 1] = n + 1, inv[n + 1] = n + 1, cost[n + 1] = 0;
for(int i = 1; i<= n+1; ++i) dp[i] = inf;

for(int x = 1; i <= n+1; ++i){
	const int x = i + 1;
	const int y = perm[x];
	int thr = -1;
	for(int cy = y - 1; cy >= 0; --cy){
		const int cx = inv[cy];
		if(x <= cx) continue;
		if(cx <= thr) continue;
		chmin(dp[x],dp[cx]);
		chmax(thr,cx);	
	}
	dp[x] += cost[i];
}

cout << dp[n + 1] << endl;

ここまでで解法なのですが，セグメント木を利用して に高速化することが可能!
x軸は更新時刻、y軸はセグ木の区間として表すことにする。
セグ木では対応する区間に含まれるxの最大値と、区間[m,r)に含まれる点のxの最大値 < x' かつy'が区間[l,m)に属する点の値の最小値を管理する。
右の子ノードを処理してから、その情報を利用して、左の子ノードをさらに処理していく．
基本的には上の二乗解法のコードの高速化なはずなので、上と下のコードをにらめっこすれば分かるかな...

#include <bits/stdc++.h>
#include <sys/types.h>
#include <unistd.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

const int inf = 2100000000;
const int limit = 1 << 17;
int perm[limit];
int val[limit];

using pii = pair<int,int>;

template <int depth> struct Segment_tree {
	const static int h = depth;
	const static int n = 1 << h;

	using T = int;
	T xmax[2 * n];
	T lch_data[2 * n];

	const T out = inf;


	void init() {
		fill_n(lch_data, 2 * n, out);
		fill_n(xmax ,2 * n, -1);
	}

	void update(int y,int x,int v){
		int i = y + n - 1;
		xmax[i] = x;
		lch_data[i] = v;

		while(i){
			const int p = (i - 1) / 2; 
			const int lch = 2 * p + 1;
			const int rch = 2 * p + 2;
			xmax[p] = max(xmax[lch], xmax[rch]);
			lch_data[p] = calc(lch, xmax[rch]);
			i = p;
		}
	}

	int calc(int i, int thr){
		if(i >= n - 1){
			if(thr < xmax[i]) return lch_data[i];
			return inf;
		}

		const int lch = 2 * i + 1;
		const int rch = 2 * i + 2;

		if(thr < xmax[rch])
			return min(lch_data[i],calc(rch,thr));
		else
			return calc(lch,thr);
	}


	pii query(int thr, int k, int l, int r) { 
		if(thr <= l) return pii(inf,-1);
		const int m = (l + r) / 2;
		const int lch = 2 * k + 1;
		const int rch = 2 * k + 2;

		if(thr < m){
			return query(thr, lch, l ,m);
		}else{
			pii cur = query(thr, rch, m, r);
			chmin(cur.first, calc(lch ,cur.second));
			chmax(cur.second,xmax[lch]);
			return cur;
		}
	}

	int query(int y){ return query(y,0,0,n).first;}
};

Segment_tree<17> seg;

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	rep(i,n) cin >> perm[i];
	rep(i,n) cin >> val[i];

	seg.init();
	seg.update(0,0,0);

	rep(i,n){
		const int x = i + 1;
		const int y = perm[i];
		const int cur = seg.query(y) + val[i];
		seg.update(y,x,cur);
	}

	cout << seg.query(n+1) << endl;
	return 0;
}

ちなみにこのテクニックは初めて見たんですけど、時たま出題されているのだろうか...