結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー zelnyok
提出日時 2019-12-08 10:21:40
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 289 ms / 2,000 ms
コード長 1,941 bytes
記録
コンパイル時間 1,142 ms
コンパイル使用メモリ 89,108 KB
実行使用メモリ 8,576 KB
最終ジャッジ日時 2024-12-29 18:45:03
合計ジャッジ時間 5,302 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

const int INF = 1e9;

struct S
{
	int x,y;
	S() {}
	S(int x,int y) : x(x),y(y) {}
	static S I() {
		return S(INF,-1);
	}
	void merge(S& a, S& b) {
		if(a.x<b.x) {
			x=a.x; y=a.y;
		} else {
			x=b.x; y=b.y;
		}
	}
};

struct SegmentTree
{
	const int n;
	std::vector<S> data;
	SegmentTree(int n, std::vector<S>& a) : n(n), data(2*n) {
		for(int i=0;i<n;i++) {
			data[n+i] = a[i];
		}
		for(int i=n-1;i>0;i--) {
			data[i].merge(data[i<<1], data[i<<1|1]);
		}
	}
	void set(int i, S v) {
		data[n+i] = v;
		i+=n;
		while(i>0) {
			i>>=1;
			data[i].merge(data[i<<1], data[i<<1|1]);
		}
	}
	S get(int l, int r) {
		// 0-Indexed, [l, r)
		l+=n; r+=n;
		S sum = S::I();
		while(l<r) {
			if(l&1) sum.merge(sum,data[l++]);
			if(r&1) sum.merge(sum,data[--r]);
			l>>=1; r>>=1;
		}
		return sum;
	}
};


signed main() {
	int n,q;
	std::cin >> n >> q;
	std::vector<int> a(n);
	rep(i,n) std::cin >> a[i];
	std::vector<S> b(n);
	rep(i,n) b[i] = S(a[i],i+1);
	SegmentTree s(n,b);
	rep(qqq,q) {
		int x;
		std::cin >> x;
		int l,r;
		std::cin >> l >> r;
		if(x==1) {
			S lx = s.get(l-1,l);
			S rx = s.get(r-1,r);
			lx.y = r; rx.y = l;
			s.set(r-1,lx); s.set(l-1,rx);
		} else {
			print(s.get(l-1,r).y);
		}
	}
	return 0;
}
0