結果

問題 No.875 Range Mindex Query
ユーザー m_tsubasam_tsubasa
提出日時 2019-09-30 00:02:40
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 288 ms / 2,000 ms
コード長 1,495 bytes
コンパイル時間 2,071 ms
コンパイル使用メモリ 172,768 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-14 07:32:54
合計ジャッジ時間 5,948 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 3 ms
6,940 KB
testcase_02 AC 4 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 3 ms
6,940 KB
testcase_07 AC 4 ms
6,944 KB
testcase_08 AC 3 ms
6,940 KB
testcase_09 AC 3 ms
6,940 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 219 ms
6,940 KB
testcase_12 AC 181 ms
6,940 KB
testcase_13 AC 159 ms
6,940 KB
testcase_14 AC 155 ms
6,944 KB
testcase_15 AC 210 ms
6,940 KB
testcase_16 AC 270 ms
6,940 KB
testcase_17 AC 287 ms
6,940 KB
testcase_18 AC 288 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// 1-indexed
template <class T>
struct SegmentTree {
  // a,b,c: T, e:T(unit)
  // abc = (ab)c = a(bc)
  // ae = ea = a
  typedef function<T(T, T)> F;
  int n;
  F f;
  T unit;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(int newn, F f, T t) : f(f), unit(t) {
    init(newn);
  }
  void init(int newn) {
    n = 1;
    while(n < newn) n <<= 1;
    dat.assign(n << 1, unit);
  }

  // "go up" process
  void update(int k, T newdata) {
    dat[k += n] = newdata;
    while(k >>= 1) {
      dat[k] = f(dat[(k << 1) | 0], dat[(k << 1) | 1]);
    }
  }
  // [a,b)
  T query(int a, int b) {
    T vl = unit, vr = unit;
    for(int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
      if(l & 1) vl = f(vl, dat[l++]);
      if(r & 1) vr = f(dat[--r], vr);
    }
    return f(vl, vr);
  }
};

int n, q;
SegmentTree<pair<int, int>> seg;

int main() {
  auto f = [](pair<int, int> l, pair<int, int> r) {
    return min(l, r);
  };
  cin >> n >> q;
  seg = SegmentTree<pair<int, int>>(n, f, {n + 1, n + 1});
  for(int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    seg.update(i, {a, i});
  }
  for(int i = 0; i < q; ++i) {
    int c, l, r;
    cin >> c >> l >> r;
    if(c == 1) {
      pair<int, int> nl = seg.query(l - 1, l),
                     nr = seg.query(r - 1, r);
      seg.update(l - 1, {nr.first, l - 1});
      seg.update(r - 1, {nl.first, r - 1});
    }
    else
      cout << seg.query(l - 1, r).second + 1 << endl;
  }

  return 0;
}
0