結果
問題 | No.875 Range Mindex Query |
ユーザー |
![]() |
提出日時 | 2019-09-06 22:00:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 336 ms / 2,000 ms |
コード長 | 2,509 bytes |
コンパイル時間 | 1,942 ms |
コンパイル使用メモリ | 132,928 KB |
実行使用メモリ | 9,600 KB |
最終ジャッジ日時 | 2024-06-24 17:52:29 |
合計ジャッジ時間 | 4,999 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 |
ソースコード
#pragma GCC optimize("O3") #include <iostream> #include <iomanip> #include <cstdio> #include <string> #include <cstring> #include <deque> #include <list> #include <queue> #include <stack> #include <vector> #include <utility> #include <algorithm> #include <map> #include <set> #include <complex> #include <cmath> #include <limits> #include <cfloat> #include <climits> #include <ctime> #include <cassert> #include <numeric> #include <fstream> #include <functional> #include <bitset> using namespace std; using ll = long long; using P = pair<int, int>; using T = tuple<int, int, int>; template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;} template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;} constexpr int MOD = 1e9 + 7; constexpr int inf = 1e9; constexpr long long INF = 1e18; constexpr double pi = acos(-1); constexpr double EPS = 1e-10; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; map<int, int> val2index; struct SegmentTree{ private: int n; vector<int> node; public: SegmentTree(vector<int> v){ int sz = v.size(); n = 1; while(n < sz) n *= 2; node.resize(2*n-1, inf); for(int i=0; i<sz; i++) node[i+n-1] = v[i]; for(int i=n-2; i>=0; i--) node[i] = min(node[2*i+1], node[2*i+2]); } // Range Minumum Query int getnode(int x){ x += (n - 1); return node[x]; } void update(int x, int val){ x += (n - 1); node[x] = val; while(0 < x){ x = (x - 1) / 2; node[x] = min(node[2*x+1], node[2*x+2]); } } int getmin(int a, int b, int k=0, int l=0, int r=-1){ if(r < 0) r = n; if(r <= a || b <= l) return inf; if(a <= l && r <= b) return node[k]; int vl = getmin(a, b, 2*k+1, l, (l+r)/2); int vr = getmin(a, b, 2*k+2, (l+r)/2, r); return min(vl, vr); } }; int main(){ int n, q; cin>>n>>q; vector<int> a(n); for(int i=0; i<n; i++){ cin>>a[i]; val2index[a[i]] = i; } SegmentTree seg(a); for(int i=0; i<q; i++){ int c, l, r; cin>>c>>l>>r; l--, r--; if(c == 1){ int a_l = seg.getnode(l); int a_r = seg.getnode(r); seg.update(l, a_r); seg.update(r, a_l); val2index[a_r] = l; val2index[a_l] = r; } else{ cout << val2index[seg.getmin(l, r + 1)] + 1 << endl; } } }