結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー suzuken_w
提出日時 2019-12-26 12:34:56
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 231 ms / 2,000 ms
コード長 2,274 bytes
記録
コンパイル時間 2,881 ms
コンパイル使用メモリ 192,900 KB
実行使用メモリ 7,296 KB
最終ジャッジ日時 2024-10-03 07:36:12
合計ジャッジ時間 5,230 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=1000000007;
const ll mod=998244353;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
const int MAX_N=(1<<18);
struct seg{
private:
int n;
V<P> dat;

public:
explicit seg(int n_){
    //簡約化のためにnを２の冪乗に置き換える
    n=1;
    while(n<n_)n*=2;
    dat.assign(2*n-1,{inf,0});
    //ノードの個数 = n+n/2+n/4+...=2n-1
  for(int i=0;i<n;i++)dat[i+n-1]={inf,i}; 
  for(int i=n-2;i>=0;i--)dat[i]=min(dat[i*2+1],dat[i*2+2]);
}
void update(int i,int x){
    //葉のノード番号
    i+=n-1;
    dat[i].fi=x;
    //登りながら更新(n1=(n-1)/2,n2=(n1-1)/2...と計算すると親のノードを調べることができ最終的に根に到達する)
    while(i>0){
        i=(i-1)/2;
        //配置の更新
        dat[i]=min(dat[i*2+1],dat[i*2+2]);
    }
}
//区間[a,b)の最小値、l,rにはノードkに対応づく区間を与える
P query(int a,int b,int k=0,int l=0, int r=-1){
    if(r<0)r=n;
    //区間が交差するかどうか、しなければINT_MAX
    if(r<=a||l>=b)return {inf,0};
    //区間を完全に含んでいるか、含んでいたら節点の値
    if(a<=l&&r<=b)return dat[k];
    else{
        //上記を満たさなければ2分法で探す
        P vl=query(a,b,k*2+1,l,(l+r)/2);
        P vr=query(a,b,k*2+2,(l+r)/2,r);
        return min(vl,vr);
    }
}
void swap(int i,int j){
  int l=query(i,i+1).fi,r=query(j,j+1).fi;
    update(i,r);
    update(j,l);
}
};
int main(){
 int n,q;
 cin>>n>>q;
 seg t(n);
 for(int i=1;i<=n;i++){
     int v;cin>>v;
     t.update(i,v);
 }
 while(q--){
     int c,a,b;cin>>c>>a>>b;
     if(c==1){
         t.swap(a,b);
     }
     else{
         cout<<t.query(a,b+1).se<<endl;
     }
 }
 
}
0