結果

問題 No.875 Range Mindex Query
ユーザー suzuken_wsuzuken_w
提出日時 2020-02-07 15:33:00
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 236 ms / 2,000 ms
コード長 2,668 bytes
コンパイル時間 2,374 ms
コンパイル使用メモリ 194,440 KB
実行使用メモリ 8,912 KB
最終ジャッジ日時 2023-10-25 23:03:50
合計ジャッジ時間 4,804 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 3 ms
4,348 KB
testcase_02 AC 3 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 3 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 3 ms
4,348 KB
testcase_08 AC 3 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 3 ms
4,348 KB
testcase_11 AC 195 ms
8,748 KB
testcase_12 AC 161 ms
6,076 KB
testcase_13 AC 128 ms
8,648 KB
testcase_14 AC 129 ms
8,652 KB
testcase_15 AC 177 ms
8,648 KB
testcase_16 AC 216 ms
8,648 KB
testcase_17 AC 236 ms
8,912 KB
testcase_18 AC 226 ms
8,912 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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=0;i<n;i++)dat[i+n-1]=v[i]; 
  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分法で探す
        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 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,INT_MAX});
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