結果

問題 No.2292 Interval Union Find
ユーザー intfansintfans
提出日時 2023-05-16 01:10:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 434 ms / 5,000 ms
コード長 7,248 bytes
コンパイル時間 3,572 ms
コンパイル使用メモリ 227,840 KB
実行使用メモリ 43,352 KB
最終ジャッジ日時 2024-12-14 06:03:48
合計ジャッジ時間 21,673 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 294 ms
17,772 KB
testcase_05 AC 288 ms
17,772 KB
testcase_06 AC 292 ms
17,864 KB
testcase_07 AC 287 ms
17,508 KB
testcase_08 AC 416 ms
41,972 KB
testcase_09 AC 414 ms
41,972 KB
testcase_10 AC 426 ms
42,152 KB
testcase_11 AC 423 ms
41,844 KB
testcase_12 AC 402 ms
41,740 KB
testcase_13 AC 395 ms
41,852 KB
testcase_14 AC 404 ms
42,096 KB
testcase_15 AC 422 ms
41,336 KB
testcase_16 AC 422 ms
40,948 KB
testcase_17 AC 434 ms
41,568 KB
testcase_18 AC 221 ms
40,336 KB
testcase_19 AC 361 ms
43,240 KB
testcase_20 AC 345 ms
43,088 KB
testcase_21 AC 355 ms
42,344 KB
testcase_22 AC 337 ms
42,356 KB
testcase_23 AC 355 ms
42,356 KB
testcase_24 AC 344 ms
42,796 KB
testcase_25 AC 351 ms
42,800 KB
testcase_26 AC 344 ms
42,360 KB
testcase_27 AC 337 ms
42,572 KB
testcase_28 AC 347 ms
43,352 KB
testcase_29 AC 356 ms
42,240 KB
testcase_30 AC 339 ms
42,904 KB
testcase_31 AC 347 ms
42,372 KB
testcase_32 AC 351 ms
42,988 KB
testcase_33 AC 348 ms
42,432 KB
testcase_34 AC 342 ms
42,512 KB
testcase_35 AC 345 ms
42,344 KB
testcase_36 AC 348 ms
42,624 KB
testcase_37 AC 345 ms
42,288 KB
testcase_38 AC 339 ms
42,680 KB
testcase_39 AC 350 ms
42,300 KB
testcase_40 AC 352 ms
42,352 KB
testcase_41 AC 88 ms
13,944 KB
testcase_42 AC 91 ms
14,716 KB
testcase_43 AC 111 ms
14,412 KB
testcase_44 AC 177 ms
14,952 KB
testcase_45 AC 197 ms
14,416 KB
testcase_46 AC 198 ms
14,616 KB
testcase_47 AC 239 ms
14,288 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// https://yukicoder.me/problems/no/2292

/*
n个顶点无向图，初始没有边，按顺序执行q次操作，
+ 1 l r : 对 l <= u < v <= r 的所有顶点对(u,v)连边
+ 2 l r : 删除所有 1 <= u < r, l < v <= n 的 (u,v)对之间的边
+ 3 u v : 判断u,v是否连通，连通输出1，否则输出0
+ 4 v: 输出顶点v所在连通分量的顶点数目
*/

template <class S,           // 线段树维护的数据信息
          S (*op)(S, S),    // 左右子节点信息合并到当前节点
          S (*e)(),
          class F,          // 懒标记维护的信息
          S (*tag)(F, S),  // 查询时给当去节点打上懒标记
          F (*merge)(F, F),  // 懒标记合并
          F (*id)()>        // 懒标记的默认值, 用于清空父节点的懒标记
struct LazySegTree {
    int n, size, log;
    vector<S> d;
    vector<F> lz;
    void pull(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void push_down(int k, F f) {
        d[k] = tag(f, d[k]);
        if (k < size) lz[k] = merge(f, lz[k]);
    }
    void push(int k) {
        push_down(2 * k, lz[k]), push_down(2 * k + 1, lz[k]);
        lz[k] = id();
    }
    LazySegTree() : LazySegTree(0) {}
    explicit LazySegTree(int N) : LazySegTree(vector<S>(N, e())) {}
    explicit LazySegTree(const vector<S>& v) : n(int(v.size())) {
        log = ceil_lg(n), size = 1 << log;
        d = vector<S>(2 * size, e()), lz = vector<F>(size, id());
        for (int i = 0; i < n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) pull(i);
    }
    int ceil_lg(int x) {   // minimum non-neg x s.t. `n <= 2^x`
        return x <= 1 ? 0 : 32 - __builtin_clz(x - 1);
    }
    void set(int p, S x) {   // 0 <= p < n
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) pull(p >> i);
    }
    S get(int p) {     // Assert 0 <= p < n
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }
    S get(int l, int r) {   // op(a[l], ..., a[r - 1])
        if (l == r) return e();
        l += size, r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        S sl = e(), sr = e();
        while (l < r) {
            if (l & 1) sl = op(sl, d[l++]);
            if (r & 1) sr = op(d[--r], sr);
            l >>= 1, r >>= 1;
        }
        return op(sl, sr);
    }
    S get_all() { return d[1]; }
    void apply(int p, F f) {   // 0 <= p < n
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = tag(f, d[p]);
        for (int i = 1; i <= log; i++) pull(p >> i);
    }
    void apply(int l, int r, F f) {  // a[i] = f(a[i]), [l, r)
        if (l == r) return;
        l += size, r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        int l2 = l, r2 = r;
        while (l < r) {
            if (l & 1) push_down(l++, f);
            if (r & 1) push_down(--r, f);
            l >>= 1, r >>= 1;
        }
        l = l2, r = r2;
        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) pull(l >> i);
            if (((r >> i) << i) != r) pull((r - 1) >> i);
        }
    }
    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) { // 0 <= l <= n, g(e()) is true
        if (l == n) return n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) sm = op(sm, d[l]), l++;
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) { // 0 <= r <= n, g(e()) is true
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm)))  sm = op(d[r], sm), r--;
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
};

using S = pair<int, int>; //(size, active sum)
using F = pair<bool, bool>; //(update, 01)
S op(S x, S y){
	return S{x.first + y.first, x.second + y.second};
}
S e() {
    return S{};
};
S tag(F f, S s) { 
	if (f.first) return {s.first, f.second ? s.first : 0};
	return s;
}
F merge(F x, F y) { return  x.first ? x : y; }
F id() { return F{false, false}; }

using ll = long long;

template <class T>
struct Discrete {
    vector<T> xs;
    Discrete(const vector<T>& v) {
        xs = v;
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
    }
    int get(const T& x) const {
        return lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    }
    inline int operator()(const T& x) const { return get(x); }
    T operator[](int i) { return xs[i]; }
    int size() const { return xs.size(); }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    vector<tuple<int, int, int>> querys;
    int t, x, y;
    vector<int> xs{1, 2, n - 1, n, n + 1};
    for (int i = 0; i < q; ++i) {
    	cin >> t;
    	if (t == 4) {
    		cin >> x;
    		querys.emplace_back(t, x, -1);
    		xs.emplace_back(x - 1);
    		xs.emplace_back(x);
    		xs.emplace_back(x + 1);
    	} else {
    		cin >> x >> y;
    		querys.emplace_back(t, x, y);
    		xs.emplace_back(x - 1);
    		xs.emplace_back(x);
    		xs.emplace_back(x + 1);
    		xs.emplace_back(t - 1);
    		xs.emplace_back(y);
    		xs.emplace_back(y + 1);
    	}
    }

    Discrete<int> v(xs);

    vector<S> init;
    for (int i = 1; i < v.size(); ++i) {
    	init.emplace_back(S{v[i] - v[i - 1], 0});
    } 
    LazySegTree<S, op, e, F, tag, merge, id> seg(init);

    for (auto &[t, x, y] : querys) {
    	if (t == 1) {
    		x = v(x), y = v(y);
    		seg.apply(x, y, {true, true});
    	} else if (t == 2) {
    		x = v(x), y = v(y);
    		seg.apply(x, y, {true, false});
    	} else if (t == 3) {
    		x = v(x), y = v(y);
    		if (x > y) swap(x, y);
    		auto [f, s] = seg.get(x, y);
    		cout << (f == s) << '\n';
    	} else {
    		int p = v(x);
    		int l = seg.min_left(p, [&](S x){return x.first == x.second;});
    		int r = seg.max_right(p, [&](S x){return x.first == x.second;});
    		cout << seg.get(l, r).first + 1 << '\n';
    	}
    }

    return 0;
}
0