結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー itsutei
提出日時 2021-09-09 13:26:37
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 251 ms / 2,000 ms
コード長 2,041 bytes
記録
コンパイル時間 1,944 ms
コンパイル使用メモリ 198,052 KB
最終ジャッジ日時 2025-01-24 08:58:48
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;

template<typename T> struct Segtree{
  const T unit = 1e9; //変える
  int n;
  vector<T> node;
  
  Segtree(int n,T val) : Segtree(vector(n,val)){}
  Segtree(vector<T> data) : n( 1<<(int)ceil( log2(data.size()) ) ), node(n*2, unit){
    
    int sz = data.size();
    for(int i=0; i<sz; i++){
      node[n+i] = data[i];
    }
    for(int i=n-1; i>0; i--){
      node[i] = comp( node[i*2],node[i*2+1] );
    }
  }
  
  T comp(const T &a, const T &b){
    return min(a,b); //変える
  }
  T find(int l, int r){ //[l,r)!!
    T x = unit, y = unit;
    l += n; r += n;
    while(l<r){
      if(l&1) x = comp(x,node[l++]);
      if(r&1) y = comp(node[--r],y);
      l>>=1; r>>=1;
    }
    return comp(x,y);
  }
  void update(int i, T v){
    i += n;
    node[i] = v;
    while((i/=2) > 0){
      node[i] = comp( node[i*2],node[i*2+1] );
    }
  }
  void add(int i,T val){
    update(i,node[i+n]+val);
  }
  
  int find_l(int a,int b,T x,int k=1,int l=0,int r=-1){
    if(r<0) r = n;
    if (!f(k,x) || r<=a || b<=l) return b;
    else if (k>=n) return k-n;
    else{
      int vl = find_l(a,b,x,2*k,l,(l+r)/2);
      if (vl != b) return vl;
      else return find_l(a,b,x,2*k+1,(l+r)/2,r);
    }
  }
  int find_r(int a,int b,T x,int k=1,int l=0,int r=-1){
    if(r<0) r = n;
    if (!f(k,x) || r<=a || b<=l) return a-1;
    else if (k>=n) return k-n;
    else{
      int vr = find_r(a,b,x,2*k+1,(l+r)/2,r);
      if (vr != a-1) return vr;
      else return find_r(a,b,x,2*k,l,(l+r)/2);
    }
  }
  bool f(int k, T x){
    return node[k] <= x;
  }
};


int main(){
  
  int n,q; cin>>n>>q;
  vector<int>a(n);
  for(auto &i:a)cin>>i;
  
  Segtree sg(a);
  
  while(q--){
    
    int t,l,r; cin>>t>>l>>r;
    --l; --r;
    if(t==1){
      int b = sg.find(l,l+1);
      int c = sg.find(r,r+1);
      sg.update(l,c);
      sg.update(r,b);
    }
    else{
      int v = sg.find(l,r+1);
      int s = sg.find_l(l,r+1,v);
      cout<<s+1<<'\n';
    }
  }
}
0