CODE FESTIVAL 2015 決勝 D. 足ゲームII

条件反射でStarrySkyTreeを使ってた。

問題

code-festival-2015-final-open.contest.atcoder.jp

解法

StarrySkyTree使えば簡単。

StarrySkyTreeというのは、

• 区間[l,r)に一様にvを足す
• 区間[l,r)の最小値を求める

という2つのクエリを備えたSegment Treeの事。実装方法はここに書いてある。kagamiz.hatenablog.com

個人的には遅延Segment Treeで実装した方が頭使わなくていいので好き。

#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
using namespace std;
typedef long long ll;
 
const ll inf = 1e9;
 
struct StarrySkyTree {
	vector<ll> seg, lazy;
	int size;
	StarrySkyTree() {}
	StarrySkyTree(int n) {
		init(n);
	}
	void init(int n) {
		size = 1;
		while (size < n) size *= 2;
		seg.resize(size * 2);
		lazy.resize(size * 2);
	}
	void push(int k, int l, int r) {
		seg[k] += lazy[k];
		if (r - l > 1) {
			lazy[k * 2 + 1] += lazy[k];
			lazy[k * 2 + 2] += lazy[k];
		}
		lazy[k] = 0;
	}
	void update(int a, int b, ll v, int k, int l, int r) {
		push(k, l, r);
		if (r <= a || b <= l) return;
		if (a <= l && r <= b) {
			lazy[k] += v;
			push(k, l, r);
		} else {
			update(a, b, v, k * 2 + 1, l, (l + r) / 2);
			update(a, b, v, k * 2 + 2, (l + r) / 2, r);
			seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2]);
		}
	}
	void update(int a, int b, ll v) {
		update(a, b, v, 0, 0, size);
	}
	ll query(int a, int b, int k, int l, int r) {
		push(k, l, r);
		if (r <= a || b <= l) return -inf;
		if (a <= l && r <= b) return seg[k];
		ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return max(vl, vr);
	}
	ll query(int a, int b) {
		return query(a, b, 0, 0, size);
	}
	ll query() {
		return query(0, size);
	}
};
 
 
int main() {
	int N;
	cin >> N;
	vector<int> S(N), T(N);
	rep (i, N) {
		scanf("%d %d", &S[i], &T[i]);
		S[i]--; T[i]--;
	}
	StarrySkyTree tr(101010);
	rep (i, N) {
		tr.update(S[i], T[i], 1);
	}
	int ans = inf;
	rep (i, N) {
		tr.update(S[i], T[i], -1);
		chmin(ans, tr.query());
		tr.update(S[i], T[i], 1);
	}
	cout << ans << endl;
	return 0;
}

感想

前にもStarrySkyTreeやるだけ問題出てるのでライブラリだけでも持っておくと良さそう。
B: ドキドキデート大作戦高橋君 - AtCoder Regular Contest 045 | AtCoder

遅延SegmentTreeはここが詳しい。d.hatena.ne.jp