結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー Arumakan1727
提出日時 2019-09-06 21:31:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 60 ms / 2,000 ms
コード長 4,736 bytes
コンパイル時間 1,514 ms
コンパイル使用メモリ 172,564 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-24 16:54:25
合計ジャッジ時間 2,919 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
// Begin Header {{{
#define let             const auto
#define all(x)          (x).begin(), (x).end()
#define rep(i, n)       for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, s, t)   for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(Type, ...)  Type __VA_ARGS__; input(__VA_ARGS__)
#define lowerBound(...)                 lowerBound_(__VA_ARGS__)
#define upperBound(...)                 upperBound_(__VA_ARGS__)
#define lowerBound_(begin, end, ...)    (lower_bound((begin), (end), __VA_ARGS__) - (begin))
#define upperBound_(begin, end, ...)    (upper_bound((begin), (end), __VA_ARGS__) - (begin))

#ifdef DBG
#define trace(...) trace_g(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...)
#endif

using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template<class T, class U>inline bool chmax(T &a, const U &b){return b>a && (a=b, true);}
template<class T, class U>inline bool chmin(T &a, const U &b){return b<a && (a=b, true);}
inline i64  sigma(i64 n)            { return (n * (n + 1) >> 1); }
inline i64  updiv(i64 a, i64 b)     { return (a + b - 1) / b; }
inline i64  sqr(i64 n)              { return n * n; }
inline string to_string(char c)     { return string(1, c); }
inline bool   isRangeIn(i64 a, i64 low, i64 high) { return (low <= a && a <= high); }
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template<class T>
vector<T> makeVec(size_t sz) { return vector<T>(sz); }

template<class T, class... Args>
auto makeVec(size_t sz, Args... args) {
    return vector<decltype(makeVec<T>(args...))>(sz, makeVec<T>(args...));
}

template<class T>
inline void input(T &x) { cin >> x; }

template<class Head, class... Tail>
inline void input(Head &head, Tail&... tail) { cin >> head; input(tail...); }

inline void print() { cout << "\n"; }

template<class Head, class... Tail>
inline void print(Head &&head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template<class T>
ostream& operator<< (ostream &out, const vector<T> &vec) {
    static constexpr const char *delim[] = { " ", "" };
    for (const auto &e : vec) out << e << delim[&e == &vec.back()];
    return out;
}

template<class T>
ostream& operator<< (ostream &out, const vector<vector<T>> &mat) {
    static constexpr const char *tail[] = { "\n", "" };
    for (const auto &row : mat) out << row << tail[&row == &mat.back()];
    return out;
}

template <class T>
void trace_g(const char *s, T&& x) {
    clog << '{';
    while(*s != '\0') clog << *(s++);
    clog << ":" << setw(3) << x << '}' << endl;
}

template <class Head, class... Tail>
void trace_g(const char *s, Head&& head, Tail&&... tail) {
    clog << '{';
    while(*s != ',') clog << *(s++);
    clog << ":" << setw(3) << head << "}, ";
    for (++s; !isgraph(*s); ++s);
    trace_g(s, std::forward<Tail>(tail)...);
}
// }}} End Header

template<class Monoid> struct SegmentTree { // {{{
    using Func = function<Monoid(Monoid, Monoid)>;
    const int sz;
    const Func merge;
    const Monoid unity;
    vector<Monoid> dat;

    SegmentTree(int n, const Monoid &u, Func f)
        : sz(1 << (__lg(n+5) + 1)), merge(f), unity(u), dat(sz*2, unity) {}

    void set(int k, const Monoid &v) { dat[k + sz] = v; }

    Monoid& operator[] (int k) { return dat[k + sz]; }
    const Monoid& operator[] (int k) const { return dat[k + sz]; }

    void build() { for (int k = sz-1; k > 0; --k) dat[k] = merge(dat[2*k], dat[2*k+1]); }

    void update(int k, const Monoid &v) {
        dat[ k += sz ] = v;
        while(k >>= 1) dat[k] = merge(dat[2*k], dat[2*k+1]);
    }

    Monoid query(int a, int b) const {
        Monoid L = unity,  R = unity;
        for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
            if (a & 1) L = merge(L, dat[a++]);
            if (b & 1) R = merge(dat[--b], R);
        }
        return merge(L, R);
    }
}; // }}}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);

    var(int, N, Q);

    vector<int> idx(N + 1);
    SegmentTree<int> seg(N, INF, [](int a, int b){ return min(a, b);} );

    reps(i, 1, N) {
        var(int, a);
        idx[a] = i;
        seg.set(i, a);
    }

    seg.build();

    while (Q--) {
        var(int, com, l, r);

        if (com == 1) {
            let beforeL = seg[l];
            let beforeR = seg[r];
            seg.update(l, beforeR);
            seg.update(r, beforeL);
            idx[beforeL] = r;
            idx[beforeR] = l;
        } else {
            let minv = seg.query(l, r + 1);
            print(idx[minv]);
        }
    }

    return 0;
}
0