結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー kya_ski
提出日時 2020-05-07 15:34:17
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,664 bytes
記録
コンパイル時間 1,621 ms
コンパイル使用メモリ 173,752 KB
実行使用メモリ 5,460 KB
最終ジャッジ日時 2024-07-03 09:25:43
合計ジャッジ時間 3,988 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct SegmentTree {
    using F = function<T(T, T)>;
private : 
    const T id;
    const F f;
    int n;
    vector<T> node;

public : 
    SegmentTree (const F &f, const T &id) : 
        f(f), id(id) { }

    void init (int sz) {
        assert(0 < sz);
        n = 1;
        while (n < sz) n <<= 1;
        node.resize(2*n, id);
    }

    void build (vector<T> v) {
        init((int)v.size());
        for (int i = 0; i < (int)v.size(); i++) node[i+n] = v[i];
        for (int i = n-1; i > 0; i--) node[i] = f(node[i<<1|0], node[i<<1|1]);
    }

    void update (int i, const T &x) {
        assert((i += n) < node.size());
        node[i] = x;
        while (i > 0) {
            i >>= 1;
            node[i] = f(node[i<<1], node[i<<1|1]);
        }
    }

    const T fold (int l, int r) const {
        assert(l <= r);
        T vl = id, vr = id;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l&1) vl = f(vl, node[l++]);
            if (r&1) vr = f(node[--r], vr);
        }
        return f(vl, vr);
    }

    const T &operator[] (int i) const {
        assert(i += n < node.size());
        return node[i];
    }

};

int main() {
	int n, q;
	cin >> n >> q;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	a.emplace_back(INT_MAX);
	iota(b.begin(), b.end(), 0);
	
	auto f = [&] (int l, int r) { return (a[l] < a[r] ? l : r); };
	SegmentTree<int> seg(f, n);
	seg.build(b);
	
	while (q--) {
		int op, l, r;
		cin >> op >> l >> r;
		l--; r--;
		if (op == 1) swap(a[l], a[r]);
		else cout << seg.fold(l, r + 1) + 1 << '\n';
	}
	
	return 0;
}
0