結果

問題 No.875 Range Mindex Query
ユーザー itsuteiitsutei
提出日時 2021-09-09 13:26:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 253 ms / 2,000 ms
コード長 2,041 bytes
コンパイル時間 2,454 ms
コンパイル使用メモリ 204,160 KB
実行使用メモリ 5,108 KB
最終ジャッジ日時 2023-08-28 17:52:57
合計ジャッジ時間 4,621 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 3 ms
4,376 KB
testcase_02 AC 3 ms
4,376 KB
testcase_03 AC 2 ms
4,380 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 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 175 ms
4,748 KB
testcase_12 AC 147 ms
4,376 KB
testcase_13 AC 122 ms
5,012 KB
testcase_14 AC 122 ms
5,108 KB
testcase_15 AC 165 ms
5,084 KB
testcase_16 AC 233 ms
5,076 KB
testcase_17 AC 253 ms
4,948 KB
testcase_18 AC 243 ms
5,016 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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