結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー S_K
提出日時 2019-12-02 14:49:02
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 4,380 bytes
記録
コンパイル時間 2,222 ms
コンパイル使用メモリ 175,956 KB
実行使用メモリ 6,144 KB
最終ジャッジ日時 2024-11-24 05:06:19
合計ジャッジ時間 4,516 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// yukicoder875 Range Mindex Query

#include <bits/stdc++.h>

using namespace std;
using ll=int64_t;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using mii = map<int, int>;
using vi=vector<int>;
using vii=vector<vi>;
using vl=vector<ll>;
using vll=vector<vl>;
using tpi=tuple<int, int, int>;

template<typename T>
class seg_tree {
private:
    using comp_type=function<const T &(const T &, const T &)>;

    static size_t __get_max_size(size_t size) {
        int res = 1;
        while (res < size) {
            res *= 2;
        }
        return res;
    }

    const size_t __size;
    const size_t __max_size;
    vector<T> __node;
    const T &__unit;
    const comp_type __comp;

    constexpr const T &__node_query(size_t i, size_t a, size_t b, size_t l, size_t r) const {
        if (r <= a || b <= l) {
            return __unit;
        } else if (l >= a && r <= b) {
            return __node[i];
        } else {
            size_t mid = (r + l) / 2;
            const auto &x1 = __node_query(2 * i + 1, a, b, l, mid);
            const auto &x2 = __node_query(2 * i + 2, a, b, mid, r);
            return __comp(x1, x2);
        }
    }

public:
    seg_tree() = delete;

    explicit constexpr seg_tree(const vector<T> &v, const T &unit, comp_type comp) : __size(v.size()),
                                                                                     __max_size(
                                                                                             __get_max_size(v.size())),
                                                                                     __unit(unit),
                                                                                     __comp(comp) {
        if (v.size() <= 1) {
            cerr << "Invalid argument: v is (0 or 1) size vector" << endl;
            exit(1);
        }

        __node = vector<T>(2 * max_size() - 1, unit);
        int base = max_size() - 1;
        for (auto i = 0; i < v.size(); i++) {
            __node[base + i] = v[i];
        }

        for (auto i = base - 1; i >= 0; i--) {
            __node[i] = comp(__node[2 * i + 1], __node[2 * i + 2]);
        }
    }

    constexpr const T &query(size_t a, size_t b) const {
        if (a >= size()) {
            cerr << "Invalid argument: a=" << a << endl;
            exit(1);
        }
        if (b > size()) {
            cerr << "Invalid argument: b=" << b << endl;
            exit(1);
        }
        if (a >= b) {
            cerr << "Invalid argument: a,b=" << a << " " << b << endl;
            exit(1);
        }
        return __node_query(0, a, b, 0, max_size());
    }

    constexpr void update(size_t i, const T &x) {
        if (i >= size()) {
            cerr << "Invalid argument: i=" << i << endl;
            exit(1);
        }

        int index = max_size() - 1 + i;
        __node[index] = x;
        while (index > 0) {
            index = (index - 1) / 2;
            __node[index] = __comp(__node[2 * index + 1], __node[2 * index + 2]);
        }
    }

    constexpr size_t size() const noexcept {
        return __size;
    }

    constexpr size_t max_size() const noexcept {
        return __max_size;
    }

    constexpr decltype(__node.begin()) begin() noexcept {
        return __node.begin();
    }

    constexpr decltype(__node.begin()) end() noexcept {
        return __node.end();
    }

    constexpr T get(size_t i) {
        return __node[max_size() - 1 + i];
    }
};

int main() {
    using vp=vector<pii>;

    int N, Q;
    cin >> N >> Q;

    vp A(N);
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        A[i] = make_pair(a, i + 1);
    }

    seg_tree<pii> t(A, make_pair(1e5 + 1, -1), [](const pii &a, const pii &b) -> const pii & {
        if (a.first < b.first) {
            return a;
        } else {
            return b;
        }
    });

    for (int i = 0; i < Q; i++) {
        int mode, a1, a2;
        cin >> mode >> a1 >> a2;
        if (mode == 2) {
            const auto &ans = t.query(a1 - 1, a2);
            cout << ans.second << endl;
        } else {
            auto old1 = t.get(a1 - 1);
            auto old2 = t.get(a2 - 1);
            int tmp = old1.first;
            old1.first = old2.first;
            old2.first = tmp;

            t.update(a1 - 1, old1);
            t.update(a2 - 1, old2);
        }
    }

    return 0;
}
0