結果

問題 No.2292 Interval Union Find
ユーザー じきお。
提出日時 2025-02-23 03:12:39
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 410 ms / 5,000 ms
コード長 4,718 bytes
コンパイル時間 4,631 ms
コンパイル使用メモリ 283,852 KB
実行使用メモリ 22,272 KB
最終ジャッジ日時 2025-02-23 03:13:01
合計ジャッジ時間 21,149 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...)
#endif

template <class S, class T>
struct Intervals {
    static constexpr S INF = numeric_limits<S>::max() / 2;
    static constexpr S L = -INF, R = INF;
    T none_val;
    int total_num;  // none_val でない区間の個数
    S total_len;    // none_val でない区間の長さの合計
    map<S, T> data;

    // コンストラクタ：全体 [L, R) を none_val に初期化
    Intervals(T nv = -1) : none_val(nv), total_num(0), total_len(0) {
        data.emplace(L, none_val);
        data.emplace(R, none_val);
    }

    // 区間 [l, r) の値を v に設定
    void set(S l, S r, T v) {
        assert(L <= l && r < R);
        if (l >= r) return;
        auto it_l = split(l), it_r = split(r);
        // [l, r) に含まれる既存の区間をすべて削除
        for (auto it = it_l; it != it_r;) {
            if (it->second != none_val) {
                S seg_l = it->first, seg_r = next(it)->first;
                total_len -= (seg_r - seg_l);
                total_num--;
            }
            it = data.erase(it);
        }
        // 新たに [l, r) を挿入
        auto it = data.emplace(l, v).first;
        if (v != none_val) {
            total_len += (r - l);
            total_num++;
        }
        // 左側との結合
        if (it != data.begin()) {
            auto it_prev = prev(it);
            if (it_prev->second == v) {
                data.erase(it);
                total_num--;
                l = it_prev->first;
                it = it_prev;
            }
        }
        // 右側との結合
        auto it_next = next(it);
        if (it_next != data.end() && it_next->second == v) {
            data.erase(it_next);
            total_num--;
        }
    }

    // 点 i が含まれる [i, i + 1) の値を返す
    T get_value(S i) {
        assert(L <= i && i < R);
        auto it = prev(data.upper_bound(i));
        return it->second;
    }

    // 点 i が含まれる区間 [l, r) とその値 v を返す
    tuple<S, S, T> get(S i) {
        assert(L <= i && i < R);
        auto it_r = data.upper_bound(i), it_l = prev(it_r);
        return make_tuple(it_l->first, it_r->first, it_l->second);
    }

    // 区間 [l, r) 内の区間を（境界ごとに分割した） run-length 圧縮結果として返す
    vector<tuple<S, S, T>> get(S l, S r) {
        assert(L <= l && r < R);
        vector<tuple<S, S, T>> res;
        if (l >= r) return res;
        auto it_r = data.upper_bound(l), it_l = prev(it_r);
        while (it_l->first < r) {
            res.emplace_back(max(l, it_l->first), min(it_r->first, r), it_l->second);
            it_l = it_r++;
        }
        return res;
    }

   private:
    // 点 pos において区間を分割し，すでに境界があればその位置のイテレータを返す
    // そうでなければ，その区間 [l, r) を [l, pos) と [pos, r) に分割し，後者の先頭を返す
    typename map<S, T>::iterator split(S pos) {
        auto it = data.lower_bound(pos);
        if (it != data.end() && it->first == pos) return it;
        T v = prev(it)->second;
        auto res = data.emplace(pos, v).first;
        if (v != none_val) total_num++;
        return res;
    }
};
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int N, Q;
    cin >> N >> Q;

    Intervals<int, int> I(-1);
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int L, R;
            cin >> L >> R;
            // [L, R) を 1 にする
            I.set(L, R, 1);
        }
        if (type == 2) {
            int L, R;
            cin >> L >> R;
            // [L, R) を -1 にする
            I.set(L, R, -1);
        }
        if (type == 3) {
            int u, v;
            cin >> u >> v;
            if (u > v) swap(u, v);
            // (u, v) がつながっているか
            auto [l, r, val] = I.get(u);
            // debug(u, v, l, r, val);
            cout << ((u == v) || (val != -1 && v <= r) ? 1 : 0) << '\n';
        }
        if (type == 4) {
            int v;
            cin >> v;
            // v が含まれる区間幅
            auto [l1, r1, val1] = I.get(v - 1);
            auto [l2, r2, val2] = I.get(v);
            // debug(v, l, r, val);
            if (val1 == val2) {
                cout << (val1 != -1 ? r2 - l1 + 1 : 1) << '\n';
            } else if (val1 == 1) {
                cout << r1 - l1 + 1 << '\n';
            } else {
                cout << r2 - l2 + 1 << '\n';
            }
        }
    }
}
0