結果

問題 No.2292 Interval Union Find
ユーザー intfansintfans
提出日時 2023-05-16 00:53:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 459 ms / 5,000 ms
コード長 7,183 bytes
コンパイル時間 2,849 ms
コンパイル使用メモリ 227,204 KB
実行使用メモリ 38,756 KB
最終ジャッジ日時 2024-05-08 04:52:06
合計ジャッジ時間 23,591 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 296 ms
14,172 KB
testcase_05 AC 285 ms
13,720 KB
testcase_06 AC 304 ms
13,804 KB
testcase_07 AC 286 ms
13,428 KB
testcase_08 AC 428 ms
37,416 KB
testcase_09 AC 442 ms
37,144 KB
testcase_10 AC 445 ms
37,268 KB
testcase_11 AC 444 ms
37,144 KB
testcase_12 AC 441 ms
37,148 KB
testcase_13 AC 427 ms
36,500 KB
testcase_14 AC 446 ms
36,760 KB
testcase_15 AC 455 ms
37,148 KB
testcase_16 AC 449 ms
36,740 KB
testcase_17 AC 459 ms
37,144 KB
testcase_18 AC 217 ms
35,548 KB
testcase_19 AC 368 ms
38,756 KB
testcase_20 AC 378 ms
38,648 KB
testcase_21 AC 376 ms
38,076 KB
testcase_22 AC 363 ms
37,920 KB
testcase_23 AC 358 ms
38,292 KB
testcase_24 AC 356 ms
38,080 KB
testcase_25 AC 354 ms
38,076 KB
testcase_26 AC 361 ms
38,344 KB
testcase_27 AC 357 ms
38,484 KB
testcase_28 AC 357 ms
38,180 KB
testcase_29 AC 365 ms
38,012 KB
testcase_30 AC 359 ms
38,072 KB
testcase_31 AC 352 ms
37,828 KB
testcase_32 AC 357 ms
38,548 KB
testcase_33 AC 353 ms
38,144 KB
testcase_34 AC 356 ms
38,116 KB
testcase_35 AC 355 ms
38,480 KB
testcase_36 AC 358 ms
38,464 KB
testcase_37 AC 359 ms
38,248 KB
testcase_38 AC 356 ms
37,872 KB
testcase_39 AC 359 ms
38,028 KB
testcase_40 AC 358 ms
38,204 KB
testcase_41 AC 82 ms
10,844 KB
testcase_42 AC 86 ms
11,368 KB
testcase_43 AC 108 ms
10,620 KB
testcase_44 AC 180 ms
11,380 KB
testcase_45 AC 189 ms
10,824 KB
testcase_46 AC 193 ms
10,804 KB
testcase_47 AC 236 ms
10,700 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;

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);
    	}
    }

    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());

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

    for (auto &[t, x, y] : querys) {
    	if (t == 1) {
    		x = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    		y = lower_bound(xs.begin(), xs.end(), y) - xs.begin();
    		seg.apply(x, y, {true, true});
    	} else if (t == 2) {
    		x = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    		y = lower_bound(xs.begin(), xs.end(), y) - xs.begin();
    		seg.apply(x, y, {true, false});
    	} else if (t == 3) {
    		x = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    		y = lower_bound(xs.begin(), xs.end(), y) - xs.begin();
    		if (x > y) swap(x, y);
    		auto [f, s] = seg.get(x, y);
    		cout << (f == s) << '\n';
    	} else {
    		int p = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    		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