結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー bond_cmprog
提出日時 2019-09-07 13:53:05
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 248 ms / 2,000 ms
コード長 3,156 bytes
コンパイル時間 1,837 ms
コンパイル使用メモリ 175,728 KB
実行使用メモリ 7,296 KB
最終ジャッジ日時 2024-06-26 09:27:39
合計ジャッジ時間 4,377 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
typedef vector<unsigned int>vec;
typedef vector<vec> mat;
typedef vector<vector<int>> Graph;

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-10;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

struct valueIdx{
    ll value, idx;
};

template<class T>
class SegTree{
    int n;                          //葉の数
    vector<T> data;                 //データを格納するvector
    T def;                          //初期値かつ単位元
    function<T(T, T)> operation;   //区間クエリで使う処理
    function<T(T, T)> update;       //点更新で使う処理

    T _query(int a, int b, int k, int l, int r){
        if(r <= a || b <= l) return def;
        if(a <= l && r <= b) return data[k];
        else{
            T c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2);
            T c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r);
            return operation(c1, c2);
        }
    }

    public:
        //_n:必要サイズ, _def:初期値かつ単位元, _operation:クエリ関数, _update:更新関数
        SegTree(size_t _n, T _def, function<T(T, T)> _operation, function<T(T, T)> _update)
        : def(_def), operation(_operation), update(_update){
            n = 1;
            while(n < _n){
                n *= 2;
            }
            data = vector<T> (2 * n - 1, def);
        }

    void change(int i, T x){
        i += n - 1;
        data[i] = update(data[i], x);
        while(i > 0){
            i = (i - 1) / 2;
            data[i] = operation(data[i * 2 + 1], data[i * 2 + 2]);
        }
    }

    //[a, b)の区間クエリ
    T query(int a, int b){
        return _query(a, b, 0, 0, n);
    }

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;

    SegTree<valueIdx> st(N, valueIdx{INF,0},
                    [](valueIdx a, valueIdx b){return (a.value < b.value ? a : b);},
                    [](valueIdx a, valueIdx b){return b;}
                    );
    REP(i,N){
        int a; cin >> a;
        st.change(i, {a,i+1});
    }
    REP(i,Q){
        int q, l, r;
        cin >> q >> l >> r;
        --l, --r;
        if(q==1){
            auto L = st.query(l, l + 1).value;
            auto R = st.query(r, r + 1).value;
            st.change(l, {R,l+1});
            st.change(r, {L,r+1});
        }
        else cout << st.query(l, r + 1).idx << endl;
    }
}
0