結果

問題 No.875 Range Mindex Query
ユーザー goodbatongoodbaton
提出日時 2019-09-06 22:06:37
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 103 ms / 2,000 ms
コード長 2,590 bytes
コンパイル時間 1,164 ms
コンパイル使用メモリ 104,080 KB
実行使用メモリ 5,760 KB
最終ジャッジ日時 2024-06-24 17:58:50
合計ジャッジ時間 3,094 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 80 ms
5,760 KB
testcase_12 AC 62 ms
5,376 KB
testcase_13 AC 58 ms
5,760 KB
testcase_14 AC 57 ms
5,760 KB
testcase_15 AC 76 ms
5,760 KB
testcase_16 AC 96 ms
5,760 KB
testcase_17 AC 103 ms
5,760 KB
testcase_18 AC 101 ms
5,760 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

/* SimpleSegTree(0-index) */

template <typename Type = int>
struct SimpleSegTree{
  int segn2;
  Type initVal;
  vector<Type> data;
  function<Type(Type, Type)> merge;

  SimpleSegTree(int n, Type initVal, function<Type(Type, Type)> merge):
    initVal(initVal), merge(merge)
  {
    for(segn2=1; segn2<n; segn2*=2);
    data.assign(segn2*2, initVal);
  }

  SimpleSegTree(int n): //RangeMinimunQuery
    SimpleSegTree(n, LLINF, [](Type a, Type b){ return min(a, b); }) {}

  SimpleSegTree(int n, Type initVal): //RangeMinimunQuery
    SimpleSegTree(n, initVal, [](Type a, Type b){ return min(a, b); }) {}

  //get value [a,b)
  Type query(int a, int b, int l = 0, int r = -1, int k = 0){
    if(r == -1) r = segn2;
    if(a <= l && r <= b) return data[k];
    if(r <= a || b <= l) return initVal;
    return merge(query(a,b,l,(l+r)/2,k*2+1),query(a,b,(l+r)/2,r,k*2+2));
  }

  //set kth number x
  void set(int k, Type x){
    k += segn2-1;
    data[k] = x;
    while(k > 0){
      k = (k-1)/2;
      data[k] = merge(data[k*2+1], data[k*2+2]);
    }
  }
};



int main(){
  int N, Q, a[SIZE];
  ll e9 = 1000000000;

  scanf("%d%d", &N, &Q);

  SimpleSegTree<ll> seg(N);

  for(int i=0; i<N; i++) {
    scanf("%d", a+i);
    seg.set(i, a[i] * e9 + i);
  }


  for(int i=0; i<Q; i++) {
    int q, l, r;
    scanf("%d%d%d", &q, &l, &r);
    l--; r--;

    if (q == 1) {
      swap(a[l], a[r]);
      seg.set(l, a[l] * e9 + l);
      seg.set(r, a[r] * e9 + r);
    } else {
      debug(seg.query(l, r+1));
      int ans = seg.query(l, r+1) % e9;

      printf("%d\n", ans + 1);
    }
  }



  return 0;
}
0