結果
問題 | No.2292 Interval Union Find |
ユーザー |
|
提出日時 | 2023-05-05 22:32:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 216 ms / 5,000 ms |
コード長 | 3,317 bytes |
コンパイル時間 | 4,265 ms |
コンパイル使用メモリ | 259,172 KB |
最終ジャッジ日時 | 2025-02-12 18:48:59 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 44 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;struct Fast{Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)#define rrep(i, a, b) for (int i = (int)(b)-1; i >= (a); i--)#define ll long longtemplate <typename T>bool chmax(T &a, const T &b){if (a < b){a = b;return true;}return false;}template <typename T>bool chmin(T &a, const T &b){if (a > b){a = b;return true;}return false;}// https://satanic0258.github.io/snippets/data-structure/SegmentMap.html// Description: 区間をsetで管理するデータ構造(なお実装はmap).各クエリO(log区間数).// #### attention! : [l, r] ( include r, not [l, r) )class SegmentMap : public std::map<signed, signed>{private:bool flagToMergeAdjacentSegment;public:// if merge [l, c] and [c+1, r], set flagToMergeAdjacentSegment to trueSegmentMap(bool flagToMergeAdjacentSegment) : flagToMergeAdjacentSegment(flagToMergeAdjacentSegment) {}// __exist -> iterator pair(l, r) (contain p)// noexist -> map.end()auto get(signed p) const{auto it = upper_bound(p);if (it == begin() || (--it)->second < p)return end();return it;}// insert segment [l, r]void insert(signed l, signed r){auto itl = upper_bound(l), itr = upper_bound(r + flagToMergeAdjacentSegment);if (itl != begin()){if ((--itl)->second < l - flagToMergeAdjacentSegment)++itl;}if (itl != itr){l = std::min(l, itl->first);r = std::max(r, std::prev(itr)->second);erase(itl, itr);}(*this)[l] = r;}// remove segment [l, r]void remove(signed l, signed r){auto itl = upper_bound(l), itr = upper_bound(r);if (itl != begin()){if ((--itl)->second < l)++itl;}if (itl == itr)return;int tl = std::min(l, itl->first), tr = std::max(r, std::prev(itr)->second);erase(itl, itr);if (tl < l)(*this)[tl] = l - 1;if (r < tr)(*this)[r + 1] = tr;}// Is p and q in same segment?bool same(signed p, signed q) const{const auto &&it = get(p);return it != end() && it->first <= q && q <= it->second;}bool contains(signed x) const{const auto &&it = get(x);return it != end() && it->first <= x && x <= it->second;}};int main(){int n, q;cin >> n >> q;SegmentMap s(false);while (q--){int type;cin >> type;if (type == 1){int l, r;cin >> l >> r;l--;r--;s.insert(l, r);}if (type == 2){int l, r;cin >> l >> r;l--;r--;s.remove(l + 1, r - 1);}if (type == 3){int u, v;cin >> u >> v;u--;v--;int ans = -1;if (u == v){ans = 1;}else{ans = s.same(u, v) ? 1 : 0;}cout << ans << "\n";}if (type == 4){int v;cin >> v;v--;if (s.contains(v)){auto it = s.get(v);cout << (it->second - it->first + 1) << "\n";}else{cout << 1 << "\n";}}}}