結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー ldsyb
提出日時 2019-09-07 16:25:50
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,833 bytes
記録
コンパイル時間 1,643 ms
コンパイル使用メモリ 175,068 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-26 21:28:21
合計ジャッジ時間 4,053 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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>
{
	int n;
	vector<T> tree;

	segment_tree(int n_, T e, function<T(T, T)> 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, function<T(T, T)> 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 + 1, 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 (il <= l && r <= ir)
		{
			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