結果

問題 No.2292 Interval Union Find
ユーザー prism17prism17
提出日時 2023-07-20 14:37:35
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 3,724 bytes
コンパイル時間 2,197 ms
コンパイル使用メモリ 185,056 KB
実行使用メモリ 19,988 KB
最終ジャッジ日時 2024-09-20 10:51:32
合計ジャッジ時間 26,770 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1,032 ms
18,452 KB
testcase_05 AC 1,010 ms
18,324 KB
testcase_06 AC 1,063 ms
18,452 KB
testcase_07 AC 1,318 ms
18,192 KB
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 AC 72 ms
9,880 KB
testcase_42 AC 76 ms
9,880 KB
testcase_43 AC 100 ms
9,876 KB
testcase_44 AC 365 ms
9,748 KB
testcase_45 AC 417 ms
9,832 KB
testcase_46 AC 423 ms
9,752 KB
testcase_47 AC 581 ms
9,876 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 = 2e5 + 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