結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー shop_one
提出日時 2020-04-15 15:37:32
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 215 ms / 2,000 ms
コード長 1,658 bytes
記録
コンパイル時間 914 ms
コンパイル使用メモリ 101,128 KB
実行使用メモリ 7,380 KB
最終ジャッジ日時 2024-10-01 18:46:17
合計ジャッジ時間 3,375 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using TP = tuple<ll,ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(18);
}
template <typename Monoid >
struct SegmentTree{
  using F = function< Monoid(Monoid,Monoid) >;

  int sz;
  vector<Monoid> seg;

  const F f;
  const Monoid M;

  SegmentTree(int n,const F f,const Monoid &M) : f(f),M(M){
    sz = 1;
    while(sz<n) sz<<=1;
    seg.assign(sz*2,M);
  }
  void set(int k,const Monoid &v){
    seg[k+sz] = v;
  }
  void build(){
    for(int k=sz-1;k>0;k--){
      seg[k] = f(seg[2*k],seg[2*k+1]);
    }
  }
  void update(int k,const Monoid &v){
    k += sz;
    seg[k] = v;
    while(k >>= 1){
      seg[k] = f(seg[2*k],seg[2*k+1]);
    }
  }
  Monoid que(int a,int b){
    Monoid L=M,R=M;
    for(a+=sz, b+=sz;a<b;a>>=1,b>>=1){
      if(a&1) L = f(L,seg[a++]);
      if(b&1) R = f(seg[--b],R);
    }
    return f(L,R);
  }
  Monoid operator[](const int &k) const{
    return seg[k+sz];
  }
};
signed main(){
  init_io();
  ll n,q,a,p,l,r;
  cin >> n >> q;
  SegmentTree<P> seg(n,[](P a,P b){
      return min(a,b);
      },P(11110000000,0));
  for(ll i=0;i<n;i++){
    cin >> a;
    seg.update(i,P(a,i));
  }
  for(int i=0;i<q;i++){
    cin >> p >> l >> r;
    l--;
    r--;
    if(p==1){
      ll x = seg[l].first;
      ll y = seg[r].first;
      seg.update(l,P(y,l));
      seg.update(r,P(x,r));
    }else{
      cout << seg.que(l,r+1).second+1<<endl;
    }
  }
}
0