Friends and Subsequences [Codeforces 361 : Div2 D]

問題

http://codeforces.com/contest/689/problem/D

n要素の2つの数列a,bがある。
この時、[l,r]の範囲でのal, al+1, ..., ar-1, arの最大値とbl, bl+1, ..., br-1, brの最小値が一致するような[l,r]の組の個数を答えよ。

1 <= n <= 2*10^5

考察

1. ぱっと見て、セグメントツリーを使いそうな問題かなーというのは思う
2. 区間最大値、区間最小値なので、セグ木かなという感じ

3. まず全探索を考えてみる
パパッとプログラムを書くとこんな感じ

int ans = 0;
rep(i, 0, n) {
	int aa = -INF;
	int bb = INF;
	rep(j, i, n) {
		aa = max(aa, a[j]);
		bb = min(bb, b[j]);
		if (aa == bb) ans++;
		if (bb < aa) break;
	}
}
cout << ans << endl;

ここでは、ある区画の最大最小では片方の点を固定すると、もう片方の点が右に行けば行くほど最大値は単調増加、最小値は単調減少するという特性を利用してプログラムを書いている

4. 3.の全探索プログラムを高速化できないか考えてみる
5. できる！！！

6. 変数jに関するループでは、[i,???]の区間において、最大と最小が等しくなっているポイントだけでans++をしている
7. 要は[i,???]の区間において、最大最小が等しくなる区間を探していることになる

8. これは二分探索+セグ木でやれそう！！！
9. セグメントツリーを使って、区間の最大最小をO(log n)で取得できるようにしておく
10. 二分探索で最大最小がひっくり返る境界線を探すので、各i毎にO(lognlogn)の計算量で計算ができる

11. これで計算量をO(n^2)からO(nlognlogn)まで落とせたので、解ける

実装

http://codeforces.com/contest/689/submission/18943156

typedef long long ll;
//-----------------------------------------------------------------
template<class V, int NV> class SegTreeMin {
public:
	vector<V> val;
	static V const def = (1LL << 60) - 1;
	V comp(V l, V r) { return min(l, r); };
	SegTreeMin() { val = vector<V>(NV*2, def); }

	V getval(int l, int r) {
		l += NV; r += NV + 1;
		V ret = def;
		while (l < r) {
			if (l & 1) ret = comp(ret, val[l++]);
			if (r & 1) ret = comp(ret, val[--r]);
			l /= 2; r /= 2;
		}
		return ret;
	}
	void update(int i, V v) {
		i += NV;
		val[i] = v;
		while (i>1) i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]);
	}
};
//-----------------------------------------------------------------
template<class V, int NV> class SegTreeMax {
public:
	vector<V> val;
	static V const def = -(1LL << 60);
	V comp(V l, V r) { return max(l, r); };
	SegTreeMax() { val = vector<V>(NV*2, def); }

	V getval(int l, int r) {
		l += NV; r += NV + 1;
		V ret = def;
		while (l < r) {
			if (l & 1) ret = comp(ret, val[l++]);
			if (r & 1) ret = comp(ret, val[--r]);
			l /= 2; r /= 2;
		}
		return ret;
	}
	void update(int i, V v) {
		i += NV;
		val[i] = v;
		while (i>1) i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]);
	}
};
//-----------------------------------------------------------------
int n;
ll a[201010], b[201010];
SegTreeMax<ll, 1 << 20> sta;
SegTreeMin<ll, 1 << 20> stb;
//-----------------------------------------------------------------
int main() {
	scanf("%d", &n);
	rep(i, 0, n) scanf("%I64d", &a[i]);
	rep(i, 0, n) scanf("%I64d", &b[i]);

	rep(i, 0, n) sta.update(i, a[i]);
	rep(i, 0, n) stb.update(i, b[i]);

	ll ans = 0;
	rep(i, 0, n) if (a[i] <= b[i]) {

		int l = i, r = n;
		while (l + 1 != r) {
			int mid = (l + r) / 2;
			if (sta.getval(i, mid) <= stb.getval(i, mid))
				l = mid;
			else
				r = mid;
		}

		if (sta.getval(i, l) != stb.getval(i, l)) continue;

		int rr = l;

		if (i == rr) {
			ans++;
			continue;
		}

		l = i, r = rr;
		while (l + 1 != r) {
			int mid = (l + r) / 2;
			if (sta.getval(i, mid) < stb.getval(i, mid))
				l = mid;
			else
				r = mid;
		}

		int ll = r;

		ans += rr - ll + 1;
		if (a[i] == b[i]) ans++;
	}
	cout << ans << endl;
}