結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー chocopuu
提出日時 2019-09-07 03:00:56
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 271 ms / 2,000 ms
コード長 1,974 bytes
記録
コンパイル時間 1,742 ms
コンパイル使用メモリ 176,820 KB
実行使用メモリ 8,532 KB
最終ジャッジ日時 2024-06-25 02:42:37
合計ジャッジ時間 4,560 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, s, n) for (int i = (s); i < (n); i++)
#define RFOR(i, s, n) for (int i = (n) - 1; i >= (s); i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define ALL(a) a.begin(), a.end()
const long long MOD = 1e9 + 7, INF = 1e18;
template<class T>inline bool CHMAX(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool CHMIN(T&a,T b){if(a>b){a=b;return true;}return false;}

template<class T>
class SegmentTree{
	private:
	int N;
	T initVal;
	std::vector<T>ary;
	std::function<T(T&,T&)>merge;
	void init(int n){
		while(N < n)N <<= 1;
		ary.resize(N << 1,initVal);
	}
	public:
		SegmentTree(int n,T initVal,std::function<T(T&,T&)>f):
			N(1),initVal(initVal),merge(f){init(n);}
	// -- a[i] = val;
	inline void update(int i,T val){
		ary[i += N] = val;
		while(i > 1){
			i >>= 1;
			ary[i] = merge(ary[i << 1],ary[(i << 1) + 1]);
		}
	}
	// -- a[i] += val;
	inline void add(int i,T val){
		update(i,ary[i + N] + val);
	}
	// -- [l,r)
	inline T query(int l,int r){
		if(l >= r)return initVal;
		T vr = initVal,vl = initVal;
		for(l += N,r += N;l != r;l >>= 1,r >>= 1){
			if(l & 1)vl = merge(vl,ary[l++]);
			if(r & 1)vr = merge(vr,ary[--r]);
		}
		return merge(vl,vr);
	}
	/*
	void debug show(){
		for(iint i = N;i < N;i++)std::cerr << ary[i] << ' ';
		std:::cerr << '\n';
	}
	*/
};

signed main(){
	int N,Q;
	cin >> N >> Q;
	vector<int>ans;
	auto seg = SegmentTree<pair<int,int>>(N,make_pair(INF,INF),[](pair<int,int>&l,pair<int,int>&r){return min(l,r);});
	REP(i,N){
		int t;cin >> t;
		seg.update(i,{t,i});
	}
	while(Q--){
		int x;
		cin >> x;
		if(x == 2){
			int l,r;
			cin >> l >> r;
			ans.push_back(seg.query(l-1,r).second+1);
		}else{
			int l,r;
			cin >> l >> r;
			l--;r--;
			int ll = seg.query(l,l+1).first;
			int rr = seg.query(r,r+1).first;
			seg.update(l,{rr,l});
			seg.update(r,{ll,r});
		}
	}
	for(auto e:ans){
		cout << e << endl;
	}
}
0