結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー KKT89
提出日時 2019-09-06 22:40:50
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 279 ms / 2,000 ms
コード長 2,060 bytes
コンパイル時間 1,096 ms
コンパイル使用メモリ 79,432 KB
実行使用メモリ 5,504 KB
最終ジャッジ日時 2024-06-24 20:12:40
合計ジャッジ時間 3,502 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <climits>
using namespace std;
typedef long long int ll;

int const INF=INT_MAX;

struct SegmentTree{
private:
    int n;
    vector<int> node;
public:
    SegmentTree(vector<int> v){
        int sz=v.size();
        n=1;
        while(n<sz)n*=2;
        node.resize(2*n-1,INF); // INF
        // 最下段に値を入れた後に、下の段から順番に値を入れる
        for(int i=0;i<sz;i++){
            node[i+n-1]=v[i];
        }
        for(int i=n-2;i>=0;i--){
            node[i]=min(node[2*i+1],node[2*i+2]);
        }
    }
    void update(int x,int val){
        //最下段のノードにアクセスする
        x+=(n-1);
        node[x]=val;
        while(x>0){
            x=(x-1)/2;
            node[x]=min(node[2*x+1],node[2*x+2]);
        }
    }
    void add(int x,int val){
        x+=(n-1);
        node[x]+=val;
        while(x>0){
            x=(x-1)/2;
            node[x]=node[2*x+1]+node[2*x+2];
        }
    }
    int getmin(int a,int b,int k=0,int l=0,int r=-1){
        if(r<0)r=n;
        if(r<=a||b<=l)return INF;
        if(a<=l&&r<=b) return node[k];
        int vl=getmin(a,b,2*k+1,l,(l+r)/2);
        int vr=getmin(a,b,2*k+2,(l+r)/2,r);
        return min(vl,vr);
    }
    int getsum(int a,int b,int k=0,int l=0,int r=-1){
        if(r<0)r=n;
        if(b<=l||r<=a)return 0;
        if(a<=l&&r<=b)return node[k];
        int vl=getsum(a,b,2*k+1,l,(l+r)/2);
        int vr=getsum(a,b,2*k+2,(l+r)/2,r);
        return vl+vr;
    }
};

int main(){
    int n,q; cin >> n >> q;
    vector<int> v(n),p(n+1);
    for(int i=0;i<n;i++){
        cin >> v[i];
        p[v[i]]=i+1;
    }
    SegmentTree seg(v);
    for(int i=0;i<q;i++){
        int c,x,y; cin >> c >> x >> y;
        if(c==1){
            int cp=v[x-1],cp2=v[y-1];
            v[y-1]=cp,v[x-1]=cp2;
            p[cp2]=x,p[cp]=y;
            seg.update(x-1,cp2); seg.update(y-1,cp);
        }
        else{
            cout << p[seg.getmin(x-1,y)] << endl;
        }
    }
}
0