結果

問題 No.875 Range Mindex Query
ユーザー MASATO338MASATO338
提出日時 2021-04-01 22:07:22
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 284 ms / 2,000 ms
コード長 2,909 bytes
コンパイル時間 2,224 ms
コンパイル使用メモリ 207,448 KB
実行使用メモリ 6,680 KB
最終ジャッジ日時 2023-08-23 06:07:12
合計ジャッジ時間 5,513 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 3 ms
4,380 KB
testcase_02 AC 3 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 3 ms
4,380 KB
testcase_07 AC 3 ms
4,380 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 3 ms
4,380 KB
testcase_11 AC 203 ms
6,160 KB
testcase_12 AC 168 ms
4,876 KB
testcase_13 AC 147 ms
6,492 KB
testcase_14 AC 140 ms
6,528 KB
testcase_15 AC 195 ms
6,516 KB
testcase_16 AC 263 ms
6,588 KB
testcase_17 AC 284 ms
6,416 KB
testcase_18 AC 274 ms
6,680 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INFint = 1e9+1;
const ll INFll = (ll)1e18+1;
const int MOD=1e9+7;

struct SegmentTree {
public:
  int n;
  vector<pair<int,int>> node;

  // 元配列 v をセグメント木で表現する
  SegmentTree(vector<pair<int, int>> v) {
    int sz = v.size();
    n = 1; while(n < sz) n *= 2; // 最下段のノード数は元配列のサイズ以上になる最小の 2 冪 -> これを n とおく
    node.resize(2*n-1, {INFint, 0}); // セグメント木全体で必要なノード数は 2n-1 個である

    for(int i=0; i<sz; i++) node[i+n-1] = v[i]; // 配列そのままが入るのはindex n-1から
    for(int i=n-2; i>=0; i--) node[i] = min(node[2*i+1], node[2*i+2]); // 下の段から順に初期値を計算していく(根はnode[0])
  }
  void update(int x, pair<int,int> val) {
    x += n - 1; // 最下段のノードにアクセスする
    node[x] = val;
    while(x > 0) {
      x = (x - 1) / 2; // 自分の親ノードに行く
      node[x] = min(node[2*x+1], node[2*x+2]);
    }
  }
  pair<int,int> getmin(int a, int b, int k=0, int l=0, int r=-1) { // 再帰を用いて、根から降りていき、[a,b)に完全にかぶっていると、その区間の値を返す
    if(r == -1) r = n; // 最初に呼び出されたときの対象区間は [0, n)。デフォルト引数にしたいが、デフォルト引数として、メンバ変数は使えないのでこういう実装になっている
    if(r <= a || b <= l) return {INFint, 0}; // 要求区間と対象区間が交わらない -> 適当に返す
    if(a <= l && r <= b) return node[k]; // 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う

    pair<int,int> vl = getmin(a, b, 2*k+1, l, (l+r)/2); // 左側の子にアクセス
    pair<int,int> vr = getmin(a, b, 2*k+2, (l+r)/2, r); // 右側の子にアクセス
    return min(vl, vr);
  }
  void print(){ // 最下段[n-1,2n-1)のn個を出力する
    for(int i(0);i<n;i++) cout << node[i+n-1].first << " ";
    cout << endl;
  }
  void print_all(){ // 最下段[n-1:2n-1)のn個を出力する
    for(int i(0);i<2*n-1;i++) cout << node[i].first << " ";
    cout << endl;
    for(int i(0);i<2*n-1;i++) cout << node[i].second << " ";
    cout << endl;
  }
};

int main(){
  int N,Q;
  cin>>N>>Q;
  vector<pair<int, int>> A(N);
  for(int i(0);i<N;i++){
    int a;
    cin>>a;
    A[i] = {a, i};
  }
  SegmentTree sg(A);
  for(int i(0);i<Q;i++){
    int x, l, r;
    cin>>x>>l>>r;
    l--;r--;
    if (x == 1) {
      pair<int,int> lv = sg.node[l + sg.n - 1];
      pair<int,int> rv = sg.node[r + sg.n - 1];
      int tmp = lv.second;
      lv.second = rv.second;
      rv.second = tmp;
      sg.update(l, rv);
      sg.update(r, lv);
    }else{
      cout << sg.getmin(l, r+1).second + 1 << endl;
    }
    // sg.print_all();
  }
  return 0;
}
0