結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー suzuken_w
提出日時 2020-02-07 15:45:14
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 257 ms / 2,000 ms
コード長 2,681 bytes
記録
コンパイル時間 2,552 ms
コンパイル使用メモリ 194,848 KB
実行使用メモリ 9,028 KB
最終ジャッジ日時 2024-09-25 07:15:57
合計ジャッジ時間 5,180 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;
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; }
template<typename Monoid>
struct seg{
int n;
using F=function<Monoid(Monoid,Monoid)>;
F f;
Monoid t;
V<Monoid> dat;
seg(int n_,F f,Monoid t):f(f),t(t){
    n=1;
    while(n<n_)n*=2;
    dat.assign(2*n-1,t);
    //ノードの個数 = 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]=f(dat[i*2+1],dat[i*2+2]);
 }
 seg(int n_,vector<Monoid> &v,F f,Monoid t):f(f),t(t){
    n=1;
    while(n<n_)n*=2;
    dat.assign(2*n-1,t);
    //ノードの個数 = n+n/2+n/4+...=2n-1
  for(int i=n-1;i<2*n-2;i++){dat[i]=v[i-(n-1)];}
  for(int i=n-2;i>=0;i--)dat[i]=f(dat[i*2+1],dat[i*2+2]);
 }
void update(int i,Monoid x){
    //葉のノード番号
    i+=n-1;
    dat[i]=x;
    //登りながら更新(n1=(n-1)/2,n2=(n1-1)/2...と計算すると親のノードを調べることができ最終的に根に到達する)
    while(i>0){
        i=(i-1)/2;
        //配置の更新
        dat[i]=f(dat[i*2+1],dat[i*2+2]);
    }
}
//区間[a,b)の最小値、l,rにはノードkに対応づく区間を与える
Monoid 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 t;
    //区間を完全に含んでいるか、含んでいたら節点の値
    if(a<=l&&r<=b)return dat[k];
    else{
        //上記を満たさなければ2分法で探す
        Monoid vl=query(a,b,k*2+1,l,(l+r)/2);
        Monoid vr=query(a,b,k*2+2,(l+r)/2,r);
        return f(vl,vr);
    }
}
};
int main(){
ll n,q;
cin>>n>>q;
auto f=[](P a,P  b){return min(a,b);};
V<P> dat(n);
for(int i=0;i<n;i++){
    cin>>dat[i].fi;
    dat[i].se=i+1;
}
seg<P> tree(n,dat,f,{INT_MAX,0});
int c;
while(q--){
    cin>>c;
    if(c==2){
        int s,t;
        cin>>s>>t;
        s--;t--;
        cout<<tree.query(s,t+1).se<<endl;
    }
    else{
        int s,t;
        cin>>s>>t;
        s--;t--;
        P l=tree.query(s,s+1);
        P r=tree.query(t,t+1);
        swap(l.se,r.se);
        tree.update(s,r);
        tree.update(t,l);
    }
}
}
0