昔はこういうの苦手だったけど、今ならできる!
問題概要
階建ての建物があって、後述するエレベータの建設をなくしては、下への移動は自由にできるが、上への移動は自由にできない。
個のエレベータ建設計画がある。 番目の計画では、 日目の夜に 階と 階との間の行き来をすべて可能にする。
以下の 個のクエリに答えよ。 番目のクエリは、 日目の昼の時点で、 階から 階へと移動することが可能かどうかを問う。
制約
考えたこと
時系列に沿って考えた方が楽なので、「エレベータ建設」と「クエリ」とをぜんぶまとめて 個のクエリとして処理する。次のようなクエリ構造体を管理することにしよう。
struct Query { int id; long long time, left, right; Query() {} Query(int i, long long t, long long l, long long r) : id(i), time(t), left(l), right(r) {} };
id は、「エレベータ建設」の場合は -1 とし、「クエリ」の場合はクエリ番号とする。こうして管理した 個のクエリを、time の昇順に並べて処理していくことにする。
ここで注意点として、エレベータ建設とクエリ処理とが同日程の場合、エレベータ建設が未実施の状態でクエリを処理することになる。このような処理は煩雑なので、time を全体的に 2 倍して、クエリ処理についてはさらに 1 を足すことにした。
クエリ処理
各クエリは次のように考えて処理することにする。なお、すべて 0-indexed で考えることにする。
- サイズ の配列を用意し、初期状態ではすべて 1 とする
- エレベータ建設では、配列の区間 [l, r) の値をすべて 1 に更新する
- クエリ処理では、
- l >= r ならば無条件に "Yes"
- l < r ならば、配列の区間 [l, r) の値がすべて 1 ならば "Yes"、そうでなければ "No"
このような処理は遅延セグメント木を用いて実現できる。
- 区間 [l, r) の値を 1 に更新する
- 区間 [l, r) の最小値を取得する
という 2 つの処理をカバーしたセグ木を作れば OK。全体として、計算量は となる。
コード
#include <bits/stdc++.h> using namespace std; // Segment Tree template<class Monoid, class Action> struct SegTree { using FuncMonoid = function< Monoid(Monoid, Monoid) >; using FuncAction = function< void(Monoid&, Action) >; using FuncComposition = function< void(Action&, Action) >; FuncMonoid FM; FuncAction FA; FuncComposition FC; Monoid IDENTITY_MONOID; Action IDENTITY_LAZY; int SIZE, HEIGHT; vector<Monoid> dat; vector<Action> lazy; SegTree() {} SegTree(int n, const FuncMonoid fm, const FuncAction fa, const FuncComposition fc, const Monoid &identity_monoid, const Action &identity_lazy) : FM(fm), FA(fa), FC(fc), IDENTITY_MONOID(identity_monoid), IDENTITY_LAZY(identity_lazy) { SIZE = 1, HEIGHT = 0; while (SIZE < n) SIZE <<= 1, ++HEIGHT; dat.assign(SIZE * 2, IDENTITY_MONOID); lazy.assign(SIZE * 2, IDENTITY_LAZY); } void init(int n, const FuncMonoid fm, const FuncAction fa, const FuncComposition fc, const Monoid &identity_monoid, const Action &identity_lazy) { FM = fm, FA = fa, FC = fc; IDENTITY_MONOID = identity_monoid, IDENTITY_LAZY = identity_lazy; SIZE = 1, HEIGHT = 0; while (SIZE < n) SIZE <<= 1, ++HEIGHT; dat.assign(SIZE * 2, IDENTITY_MONOID); lazy.assign(SIZE * 2, IDENTITY_LAZY); } // set, a is 0-indexed void set(int a, const Monoid &v) { dat[a + SIZE] = v; } void build() { for (int k = SIZE - 1; k > 0; --k) dat[k] = FM(dat[k*2], dat[k*2+1]); } // update [a, b) inline void evaluate(int k) { if (lazy[k] == IDENTITY_LAZY) return; if (k < SIZE) FC(lazy[k*2], lazy[k]), FC(lazy[k*2+1], lazy[k]); FA(dat[k], lazy[k]); lazy[k] = IDENTITY_LAZY; } inline void update(int a, int b, const Action &v, int k, int l, int r) { evaluate(k); if (a <= l && r <= b) FC(lazy[k], v), evaluate(k); else if (a < r && l < b) { update(a, b, v, k*2, l, (l+r)>>1); update(a, b, v, k*2+1, (l+r)>>1, r); dat[k] = FM(dat[k*2], dat[k*2+1]); } } inline void update(int a, int b, const Action &v) { update(a, b, v, 1, 0, SIZE); } // get [a, b) inline Monoid get(int a, int b, int k, int l, int r) { evaluate(k); if (a <= l && r <= b) return dat[k]; else if (a < r && l < b) return FM(get(a, b, k*2, l, (l+r)>>1), get(a, b, k*2+1, (l+r)>>1, r)); else return IDENTITY_MONOID; } inline Monoid get(int a, int b) { return get(a, b, 1, 0, SIZE); } inline Monoid operator [] (int a) { return get(a, a + 1); } // debug void print() { for (int i = 0; i < SIZE; ++i) { if (i) cout << ","; cout << get(i, i+1); } cout << endl; } }; struct Query { int id; long long time, left, right; Query() {} Query(int i, long long t, long long l, long long r) : id(i), time(t), left(l), right(r) {} friend ostream& operator << (ostream &os, const Query &q) { return os << "(" << q.id << ", " << q.time << ", " << q.left << ", " << q.right << ")" << endl; } }; int main() { int N, M, Q; cin >> N >> M >> Q; vector<Query> qs(M + Q); for (int i = 0; i < M; ++i) { long long t, l, r; cin >> t >> l >> r; --l, --r; qs[i] = Query(-1, t*2+1, l, r); } for (int i = 0; i < Q; ++i) { long long t, l, r; cin >> t >> l >> r; --l, --r; qs[i+M] = Query(i, t*2, l, r); } sort(qs.begin(), qs.end(), [&](const Query &p, const Query &q) { return p.time < q.time; }); auto fm = [&](long long a, long long b) -> long long { return min(a, b); }; auto fa = [&](long long &a, long long b) -> void { a = b; }; auto fc = [&](long long &a, long long b) -> void { a = b; }; SegTree<long long, long long> seg(N+5, fm, fa, fc, 1LL<<60, -1); for (int i = 0; i < N+5; ++i) seg.set(i, 0); seg.build(); vector<bool> res(Q, false); for (auto q : qs) { if (q.id == -1) { seg.update(q.left, q.right, 1); } else { if (q.left >= q.right) res[q.id] = true; else res[q.id] = seg.get(q.left, q.right); } } for (int q = 0; q < Q; ++q) cout << (res[q] ? "Yes" : "No") << endl; }