test/aoj/DSL_2_A.test.cpp

• View this file on GitHub
• Last update: 2022-03-13 15:01:13+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A

Depends on

• Segment tree (DataStructure/SegmentTree/SegmentTree.cpp)

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A"

#include <bits/stdc++.h>
#ifdef __LOCAL
#define DBG(X) cout << #X << " = " << (X) << endl;
#define SAY(X) cout << (X) << endl;
#else
#define DBG(X)
#define SAY(X)
#define NDEBUG
#endif

using namespace std;

typedef int_fast32_t int32;
typedef int_fast64_t int64;

const int32 inf = 1e9+7;
const int32 MOD = 1000000007;
const int64 llinf = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define all(obj) (obj).begin(),(obj).end()
#define rall(obj) (obj).rbegin(),(obj).rend()
#define fi first
#define se second
#define pb(a) push_back(a)
typedef pair<int32,int32> pii;
typedef pair<int64,int64> pll;

template<class T> inline bool chmax(T& a, T b) {
  if (a < b) { a = b; return true; } return false;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) { a = b; return true; } return false;
}

#include "../../DataStructure/SegmentTree/SegmentTree.cpp"

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n,q;
  cin >> n >> q;
  SegmentTree<int> rmq(n,[](int a,int b){return min(a,b);},INT_MAX);
  for(int i = 0; i < q; ++i){
    int com,x,y;
    cin >> com >> x >> y;
    if(com == 0){
      rmq.update(x,y);
    }else{
      cout << rmq.query(x,y+1) << endl;
    }
  }
  return 0;
}

#line 1 "test/aoj/DSL_2_A.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A"

#include <bits/stdc++.h>
#ifdef __LOCAL
#define DBG(X) cout << #X << " = " << (X) << endl;
#define SAY(X) cout << (X) << endl;
#else
#define DBG(X)
#define SAY(X)
#define NDEBUG
#endif

using namespace std;

typedef int_fast32_t int32;
typedef int_fast64_t int64;

const int32 inf = 1e9+7;
const int32 MOD = 1000000007;
const int64 llinf = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define all(obj) (obj).begin(),(obj).end()
#define rall(obj) (obj).rbegin(),(obj).rend()
#define fi first
#define se second
#define pb(a) push_back(a)
typedef pair<int32,int32> pii;
typedef pair<int64,int64> pll;

template<class T> inline bool chmax(T& a, T b) {
  if (a < b) { a = b; return true; } return false;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) { a = b; return true; } return false;
}

#line 2 "DataStructure/SegmentTree/SegmentTree.cpp"
using namespace std;

/**
 * @brief Segment tree
 * @details 1点更新（書き換え）区間取得. Tはコンストラクタ引数の2項演算fによってMonoidを成しているとする.
 * 
 * @tparam T Monoid
 */
template<typename T>
struct SegmentTree{
  typedef function<T(T,T)> F;
  /**
   * @brief Construct a new Segment Tree object
   * @details $O(n)$
   * 
   * @param n_ 要素数
   * @param f 2項演算
   * @param e 単位元
   */
  SegmentTree(int n_,F f,T e):f(f),e(e){
    init(n_);
    build();
  }
  /**
   * @brief Construct a new Segment Tree object
   * @details $O(n)$
   * 
   * @param n_ 要素数
   * @param f 2項演算
   * @param e 単位元
   * @param v 初期値
   */
  SegmentTree(int n_,F f,T e,vector<T>& v):f(f),e(e){
    init(n_);
    build(n_,v);
  }
  /**
   * @brief 1点更新
   * @details $O(\log n)$
   * 
   * @param k index
   * @param x 新しい値
   */
  void update(int k,const T& x){
    dat[k+=n]=x;
    while(k>>=1){
      dat[k] = f(dat[k<<1],dat[k<<1|1]);
    }
  }
  /**
   * @brief 区間の値を取得する
   * @details $O(\log n)$
   * 
   * @param a 左端(inclusive)
   * @param b 右端(exclusive)
   * @return T 2項演算fによる[l,r)の区間和
   */
  T query(int a,int b){
    T l=e,r=e;
    for(a+=n,b+=n;a<b;a>>=1,b>>=1){
      if(a&1)l=f(l,dat[a++]);
      if(b&1)r=f(dat[--b],r);
    }
    return f(l,r);
  }
  T operator[](const int &k) const {
    return dat[n+k];
  }
private:
  int n;
  F f;
  T e;
  vector<T> dat;
  void init(int n_){
    n=1;
    while(n<n_)n<<=1;
    dat.clear();
    dat.resize(n<<1, e);
  }
  void build(int n_,const vector<T>& v){
    for(int i=0;i<n_;++i)dat[n+i]=v[i];
    build();
  }
  void build(){
    for(int i=n-1;i>=1;--i){
      dat[i] = f(dat[i<<1],dat[i<<1|1]);
    }
  }
};
#line 45 "test/aoj/DSL_2_A.test.cpp"

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n,q;
  cin >> n >> q;
  SegmentTree<int> rmq(n,[](int a,int b){return min(a,b);},INT_MAX);
  for(int i = 0; i < q; ++i){
    int com,x,y;
    cin >> com >> x >> y;
    if(com == 0){
      rmq.update(x,y);
    }else{
      cout << rmq.query(x,y+1) << endl;
    }
  }
  return 0;
}

Back to top page