結果

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

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <numeric>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
#include <cassert>
#include <random>
#include <time.h>
//#include <boost/multiprecision/cpp_int.hpp>



using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const double EPS = 1e-10;
long long const MOD = 1000000007;

long long mod_pow(long long x, long long n) {
    long long res = 1;
    for (int i = 0;i < 60; i++) {
        if (n >> i & 1) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

template<typename T>
T gcd(T a, T b) {
    return b != 0 ? gcd(b, a % b) : a;
}

template<typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

void fastInput() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

struct SegmentTree {
private:
    int n;
    vector<int> node;
public:
    SegmentTree(vector<int> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        
        node.resize(2*n-1, 0);
 
        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[i*2+1], node[i*2+2]); // 残りの初期化
    }
 
    void change(int l, int r) {
        l += (n-1);
        r += (n-1);
        swap(node[l], node[r]); // 葉の変更
 
        // 親への伝播
        while(l > 0) {
            l = (l - 1) / 2;
            node[l] = min(node[2*l+1], node[2*l+2]);
        }
        while(r > 0) {
            r = (r - 1) / 2;
            node[r] = min(node[2*r+1] , node[2*r+2]);
        }
    }
 
    int getmin(int a, int b, int k = 0, int l = 0, int r = -1) {
        if(r < 0) r = n;
        if(b <= l || r <= a) return 100005; // クエリの区間に含まれていない場合は、答えに影響しない値を返す。
        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 main(void) {
    int N, Q; cin >> N >> Q;
    vector<int> A(N+1);
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    vector<int> pos(N+1);
    for (int i = 1; i <= N; i++) {
        pos[A[i]] = i;
    }

    SegmentTree seg(A);
    for (int i = 0; i < Q; i++) {
        int q, l, r; cin >> q >> l >> r;
        if (q == 1) {
            seg.change(l, r);
            swap(pos[A[l]], pos[A[r]]);
            swap(A[l], A[r]);
        } else {
            r++;
            cout << pos[seg.getmin(l, r)] << endl;
        }
    }
    return 0;
}
0