結果

問題 No.875 Range Mindex Query
ユーザー KKT89KKT89
提出日時 2019-09-06 22:40:50
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 191 ms
5,376 KB
testcase_12 AC 157 ms
5,376 KB
testcase_13 AC 131 ms
5,376 KB
testcase_14 AC 131 ms
5,376 KB
testcase_15 AC 179 ms
5,504 KB
testcase_16 AC 253 ms
5,376 KB
testcase_17 AC 279 ms
5,376 KB
testcase_18 AC 264 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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