結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー m_tsubasa
提出日時 2019-09-30 00:02:40
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 246 ms / 2,000 ms
コード長 1,495 bytes
記録
コンパイル時間 1,776 ms
コンパイル使用メモリ 175,444 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-03 04:44:30
合計ジャッジ時間 4,756 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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