結果

問題 No.875 Range Mindex Query
ユーザー onsen_manjuuuonsen_manjuuu
提出日時 2020-08-18 08:29:49
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 280 ms / 2,000 ms
コード長 3,173 bytes
コンパイル時間 1,877 ms
コンパイル使用メモリ 175,700 KB
実行使用メモリ 5,504 KB
最終ジャッジ日時 2024-10-11 22:05:54
合計ジャッジ時間 4,571 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const int INF = 1e9;

template<class T> 
class SegTree{

    private:

        int n;
        int m;
        int depth;
        T def;
        vector<T> data;
        function<T(T,T)> calculate;
        function<T(T,T)> update;

        T rec(int l, int r, int node, int node_l, int node_r) {
            if (node_r <= l || node_l >= r) return def;
            if (node_l >= l && node_r <= r) return data[node];
            int mid = (node_l + node_r) / 2;
            return calculate(
                rec(l, r, node * 2, node_l, mid),
                rec(l, r, node * 2 + 1, mid, node_r));
        }

        void _show() {
            vector<string> res(depth + 1);
            vector<int> width(depth + 1);
            width[depth-1] = 3;
            for(int i = depth-2; i >= 0; i--)width[i] = width[i + 1] * 2 + 2;

            for(int i = 0; i < depth; i++) {
                int start = 1<<i, end = 1<<(i + 1);
                for(int j = start; j < end; j++) {
                    int d = 0, cur = (data[j] == 0 ? 1 : data[j]);
                    while(cur){cur/=10,d++;}
                    int wid = width[i] - d;
                    cerr << '[' << right << string(wid/2,' ') << data[j] << string(wid - wid/2, ' ') << ']';
                }
                cerr << '\n';
            }
        }


    public:


        SegTree(vector<T> a, T _def, function<T(T,T)> _calculate, function<T(T,T)> _update):
        def(_def), calculate(_calculate), update(_update) {
            m = a.size();
            for (n = 1; n < (int) a.size(); n *= 2, depth++);
            data.resize(n * 2, def);
            for (int i = 0; i < (int) a.size(); i++) data[i + n] = a[i];
            for (int i = n - 1; i >= 1; i--)
                data[i] = calculate(data[i * 2], data[i * 2 + 1]);
        }
        

        //区間取得
        T get(int l,int r){
            if(l == r)return def;
            return rec(l,r,1,0,n);
        }
        
        //一点更新
        void assign(int index, T val){
            index += n;
            data[index] = update(data[index], val);
            for(;index /= 2;)
                data[index] = calculate(data[index * 2],data[index * 2 + 1]);
        }


        void print() {
            cerr << "[";
            for(int i = 0; i < m; i++) {
                cerr << data[i + n] << (i != m - 1 ? "," : "]\n");
            }
        }

        void show() {
            _show();
        }

        T operator[] (int i){
            return data[i + n];
        }

};


int main()
{
    int n, q;
    cin >> n >> q;
    vector<int> pos(n);
    vector<int> a(n);
    for(int i = 0; i < n; i++)cin >> a[i],a[i]--,pos[a[i]] = i;
    SegTree<int> tree(a, INF, [](int a, int b){return min(a,b);}, [](int a, int b){return b;});

    for(int i = 0; i < q; i++) {
        int t, l, r; cin >> t >> l >> r;
        l--,r--;
        if(t == 1) {
            int lv = tree[l], rv = tree[r];
            tree.assign(r, lv), tree.assign(l, rv);
            pos[lv] = r, pos[rv] = l;
        } else {
            cout << pos[tree.get(l, r + 1)]+1 << endl;
        }
    }

}
0