結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー moharan627
提出日時 2022-06-19 13:01:46
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 268 ms / 2,000 ms
コード長 3,960 bytes
コンパイル時間 5,305 ms
コンパイル使用メモリ 314,476 KB
実行使用メモリ 9,656 KB
最終ジャッジ日時 2024-10-11 10:11:12
合計ジャッジ時間 8,749 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#if !__INCLUDE_LEVEL__

#include __FILE__
template <typename T>
struct SegmentTree {
    using F = function<T(T, T)>;
    int n;
    F f;
    T ti;
    vector<T> dat;
    SegmentTree(){};
    SegmentTree(F f, T ti) : f(f), ti(ti) {}
    void init(int n_) {
        n = 1;
        while (n < n_) n <<= 1;
        dat.assign(n << 1, ti);
    }
    void build(const vector<T> &v) {
        int n_ = v.size();
        init(n_);
        for (int i = 0; i < n_; i++) dat[n + i] = v[i];
        for (int i = n - 1; i; i--)
            dat[i] = f(dat[(i << 1) | 0], dat[(i << 1) | 1]);
    }
    void set_val(int k, T x) {
        dat[k += n] = x;
        while (k >>= 1) dat[k] = f(dat[(k << 1) | 0], dat[(k << 1) | 1]);
    }
    T query(int a, int b) {
        T vl = ti, vr = ti;
        for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) vl = f(vl, dat[l++]);
            if (r & 1) vr = f(dat[--r], vr);
        }
        return f(vl, vr);
    }
};
//区間最大、最小のインデックスも返すセグ木
//構築
/*
using P = pair<ll, ll>;
auto f=[](P a,P b){return min(a,b);};
P ei(INF,-1);//(単位元,インデックスの初期値)
SegmentTree<P> seg(f,ei);
vector<P> vp(N);//対象となる配列をインデックスとのペアで渡す必要あり
rep(i,N){
    vp[i] = {A[i],i};
}
seg.build(vp);
*/
//メソッド
//seg.set_val(i,{val,i});i番目にvalをセット。この時、インデックスとのペアで渡す必要あり
//seg.query(i,j);[i,j)の区間のクエリ取得。単一の場合、seg.query(i,i+1)で取得。
int main()
{
    ll N,Q;cin >> N >> Q;
    vl A(N);rep(i,N)cin >> A[i];
    using P = pair<ll, ll>;
    auto f = [](P a, P b) { return min(a, b); };
    P ei(INF, -1);  //(単位元,インデックスの初期値)
    SegmentTree<P> seg(f, ei);
    vector<P> vp(N);  //対象となる配列をインデックスとのペアで渡す必要あり
    rep(i, N) { vp[i] = {A[i], i}; }
    seg.build(vp);
    rep(q,Q){
        int t;cin >> t;
        if(t==1){
            ll l,r;cin >> l >> r;
            l-=1;
            r-=1;
            swap(A[l],A[r]);
            seg.set_val(l,{A[l],l});
            seg.set_val(r,{A[r],r});
        }
        else if(t==2){
            ll l, r;
            cin >> l >> r;
            l -= 1;
            cout << seg.query(l,r).second+1 << endl;
        }
    }
}

#else

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rrep(i, n) for(int i = n-1; i >= 0; i--)
#define range(i, m, n) for(int i = m; i < n; i++)
#define fore(i,a) for(auto &i:a)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define Sum(v) accumulate(all(v),0)
#define minv(v) *min_element(all(v))
#define maxv(v) *max_element(all(v))
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
const ll INF = 1e16;
const ll MOD1 = 1000000007;
const ll MOD2 = 998244353;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll SN(char s){return ll(s-'0');}
ll SN(string s){return stoll(s);}
int alpN(char s){return int(s-'a');}
int AlpN(char s){return int(s-'A');}
using Graph = vector<vector<ll>>;
using GraphCost = vector<vector<pair<ll,ll>>>;
using mint1 = modint1000000007;
using mint2 = modint998244353;
using pll = pair<long long, long long>;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){for(int i=0;i<(int)v.size();i++)o<<(i>0?" ":"")<<v[i];return o;}//vector空白区切り出力
ostream& operator<<(ostream& os, const mint1& N) {return os << N.val();}//mint出力。デフォはmint1
ostream& operator<<(ostream& os, const mint2& N) {return os << N.val();}
template<class T> bool contain(const std::string& s, const T& v) {
    return s.find(v) != std::string::npos;
}

#endif
0