結果

問題 No.875 Range Mindex Query
ユーザー ldsybldsyb
提出日時 2019-09-07 17:03:15
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 283 ms / 2,000 ms
コード長 1,825 bytes
コンパイル時間 3,320 ms
コンパイル使用メモリ 172,248 KB
実行使用メモリ 6,332 KB
最終ジャッジ日時 2023-09-09 05:07:05
合計ジャッジ時間 5,254 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 3 ms
4,380 KB
testcase_02 AC 3 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 3 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 203 ms
6,044 KB
testcase_12 AC 163 ms
4,612 KB
testcase_13 AC 142 ms
6,276 KB
testcase_14 AC 141 ms
6,332 KB
testcase_15 AC 195 ms
6,216 KB
testcase_16 AC 265 ms
6,308 KB
testcase_17 AC 283 ms
6,172 KB
testcase_18 AC 278 ms
6,164 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template <typename T>
struct monoid
{
	using F = function<T(T, T)>;

	T e;
	F f;

	monoid(T e, F f) : e(e), f(f)
	{
	}
};

template <typename T>
struct segment_tree : monoid<T>
{
	using F = function<T(T, T)>;
	int n;
	vector<T> tree;

	segment_tree(int n_, T e, F f) : monoid<T>(e, f)
	{
		for (n = 1; n < n_;)
		{
			n *= 2;
		}
		tree.assign(2 * n, monoid<T>::e);
	}

	segment_tree(int n_, vector<T> &init, T e, F f) : monoid<T>(e, f)
	{
		for (n = 1; n < n_;)
		{
			n *= 2;
		}
		tree.assign(2 * n, monoid<T>::e);
		for (size_t i = 0; i < init.size(); i++)
		{
			update(i, init[i]);
		}
	}

	void update(int index, T x)
	{
		index += n;
		tree[index] = x;
		for (index /= 2; 0 < index; index /= 2)
		{
			tree[index] = monoid<T>::f(tree[2 * index + 0], tree[2 * index + 1]);
		}
	}

	T query(int index, int il, int ir, int l, int r)
	{
		if (ir <= l || r <= il)
		{
			return monoid<T>::e;
		}

		if (l <= il && ir <= r)
		{
			return tree[index];
		}
		else
		{
			T left = query(2 * index + 0, il, (il + ir) / 2, l, r);
			T right = query(2 * index + 1, (il + ir) / 2, ir, l, r);
			return monoid<T>::f(left, right);
		}
	}

	T query(int l, int r)
	{
		return query(1, 0, n, l, r);
	}
};

int main()
{
	int n, q;
	cin >> n >> q;
	vector<int64_t> as(n);
	for (auto &&a : as)
	{
		cin >> a;
		a--;
	}

	vector<int> mp(n);
	for (int i = 0; i < n; i++)
	{
		mp[as[i]] = i;
	}

	segment_tree<int64_t> seg(n, as, (1LL << 60), [](int64_t l, int64_t r) { return min(l, r); });

	for (int _ = 0; _ < q; _++)
	{
		int t, l, r;
		cin >> t >> l >> r;
		l--;
		r--;

		if (t == 1)
		{
			seg.update(l, as[r]);
			seg.update(r, as[l]);
			swap(mp[as[l]], mp[as[r]]);
			swap(as[l], as[r]);
		}
		else if (t == 2)
		{
			cout << mp[seg.query(l, r + 1)] + 1 << endl;
		}
	}

	return 0;
}
0