結果

問題 No.2292 Interval Union Find
ユーザー prism17prism17
提出日時 2023-07-20 14:41:17
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,620 ms / 5,000 ms
コード長 3,724 bytes
コンパイル時間 2,104 ms
コンパイル使用メモリ 184,608 KB
実行使用メモリ 90,772 KB
最終ジャッジ日時 2024-09-20 10:55:46
合計ジャッジ時間 46,907 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 3 ms
5,248 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 1,037 ms
18,384 KB
testcase_05 AC 954 ms
18,456 KB
testcase_06 AC 980 ms
18,452 KB
testcase_07 AC 1,226 ms
18,080 KB
testcase_08 AC 1,591 ms
90,004 KB
testcase_09 AC 1,618 ms
90,000 KB
testcase_10 AC 1,620 ms
90,004 KB
testcase_11 AC 1,590 ms
90,132 KB
testcase_12 AC 1,580 ms
90,004 KB
testcase_13 AC 1,494 ms
90,004 KB
testcase_14 AC 1,529 ms
90,132 KB
testcase_15 AC 1,558 ms
90,004 KB
testcase_16 AC 1,557 ms
90,136 KB
testcase_17 AC 1,619 ms
90,004 KB
testcase_18 AC 206 ms
90,772 KB
testcase_19 AC 373 ms
90,720 KB
testcase_20 AC 369 ms
90,772 KB
testcase_21 AC 870 ms
90,516 KB
testcase_22 AC 856 ms
90,388 KB
testcase_23 AC 860 ms
90,512 KB
testcase_24 AC 888 ms
90,388 KB
testcase_25 AC 854 ms
90,388 KB
testcase_26 AC 868 ms
90,512 KB
testcase_27 AC 906 ms
90,384 KB
testcase_28 AC 879 ms
90,516 KB
testcase_29 AC 880 ms
90,516 KB
testcase_30 AC 879 ms
90,512 KB
testcase_31 AC 865 ms
90,516 KB
testcase_32 AC 888 ms
90,392 KB
testcase_33 AC 867 ms
90,388 KB
testcase_34 AC 871 ms
90,392 KB
testcase_35 AC 884 ms
90,392 KB
testcase_36 AC 871 ms
90,468 KB
testcase_37 AC 859 ms
90,384 KB
testcase_38 AC 867 ms
90,388 KB
testcase_39 AC 870 ms
90,516 KB
testcase_40 AC 883 ms
90,384 KB
testcase_41 AC 69 ms
9,748 KB
testcase_42 AC 73 ms
9,748 KB
testcase_43 AC 97 ms
9,620 KB
testcase_44 AC 358 ms
9,748 KB
testcase_45 AC 421 ms
9,748 KB
testcase_46 AC 397 ms
9,700 KB
testcase_47 AC 553 ms
9,616 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Problem: No.2292 Interval Union Find No.2292 区间并集查找
// Contest: yukicoder
// URL: https://yukicoder.me/problems/no/2292
// Memory Limit: 512 MB
// Time Limit: 5000 ms

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define dbg(x) cout << #x << " = " << (x) << "\n";
#define popcount(x) __builtin_popcountll((x))
#define all(v) (v).begin(), (v).end()
#define pb emplace_back
#define x first
#define y second

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 8e5 + 7;

struct sgt {
#define lson (id << 1)
#define rson (id << 1 | 1)
#define mid (st[id].l + st[id].r >> 1)
  int index;
  struct node {
    int l, r, lz;
    ll sum, ls, rs;
  } st[N << 2];
  void pushnow(int id, int val) {
    // 给自己打lazy标记
    st[id].rs = st[id].ls = st[id].sum = val ? (st[id].r - st[id].l + 1) : 0;
    st[id].lz = val;
  }
  void pushup(int id) { st[id].sum = st[lson].sum + st[rson].sum; }
  void pushdown(int id) {
    if (st[id].lz != -1) {
      pushnow(lson, st[id].lz);
      pushnow(rson, st[id].lz);
      st[id].lz = -1;
    }
  }
  void build(int id, int l, int r) {
    st[id].l = l;
    st[id].r = r;
    if (l == r) {
      st[id].lz = -1;
      st[id].sum = 0;
      return;
    }
    build(lson, l, mid);
    build(rson, mid + 1, r);
    pushup(id);
  }
  void update(int id, int l, int r, int val) {
    if (st[id].l > r || st[id].r < l) return;
    if (st[id].l >= l && st[id].r <= r) {
      pushnow(id, val);
      return;
    }
    pushdown(id);
    update(lson, l, r, val);
    update(rson, l, r, val);
    pushup(id);
  }
  ll query(int id, int l, int r) {
    if (st[id].l > r || st[id].r < l) return 0;
    if (st[id].l >= l && st[id].r <= r) {
      return st[id].sum;
    }
    pushdown(id);
    return query(lson, l, r) + query(rson, l, r);
  }
} st;

int n, q;

void solve() {
  cin >> n >> q;
  vector<int> op(q), l(q), r(q);
  vector<int> m;
  for (int i = 0; i < q; i++) {
    cin >> op[i];
    if (op[i] == 4) {
      cin >> l[i];
      m.pb(l[i]);
    } else {
      cin >> l[i] >> r[i];
      m.pb(l[i]);
      m.pb(l[i] - 1);
      m.pb(r[i]);
      m.pb(r[i] - 1);
    }
  }
  m.pb(1);
  m.pb(n - 1);
  sort(all(m));
  m.erase(unique(all(m)), m.end());
  st.build(1, 1, m.size());
  auto get = [&](int x) { return lower_bound(all(m), x) - m.begin() + 1; };
  for (int i = 0; i < q; i++) {
    if (op[i] == 1) {
      --r[i];
      st.update(1, get(l[i]), get(r[i]), 1);
    } else if (op[i] == 2) {
      --r[i];
      st.update(1, get(l[i]), get(r[i]), 0);
    } else if (op[i] == 3) {
      if (l[i] == r[i]) {
        cout << "1\n";
        continue;
      }
      if (l[i] > r[i]) swap(l[i], r[i]);
      --r[i];
      cout << ((st.query(1, get(l[i]), get(r[i])) == get(r[i]) - get(l[i]) + 1)
                   ? 1
                   : 0)
           << "\n";
    } else {
      int ansL = 0, ansR = 0;
      int L = get(1), R = get(l[i] - 1);
      while (L < R) {
        int mm = L + R >> 1;
        if (st.query(1, mm, get(l[i] - 1)) == get(l[i] - 1) - mm + 1)
          R = mm;
        else
          L = mm + 1;
      }
      ansL = L;
      if (st.query(1, ansL, ansL) == 0) ++ansL;
      L = get(l[i]), R = get(n - 1);
      while (L < R) {
        int mm = L + R + 1 >> 1;
        if (st.query(1, get(l[i]), mm) == mm - get(l[i]) + 1)
          L = mm;
        else
          R = mm - 1;
      }
      ansR = L;
      if (st.query(1, ansR, ansR) == 0) --ansR;
      cout << max(1, m[ansR - 1] - m[ansL - 1] + 2) << "\n";
    }
  }
}

int main() {
  fastio;
  int t = 1;
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
0