結果
問題 | No.875 Range Mindex Query |
ユーザー |
![]() |
提出日時 | 2019-09-06 21:43:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 307 ms / 2,000 ms |
コード長 | 2,477 bytes |
コンパイル時間 | 1,747 ms |
コンパイル使用メモリ | 176,224 KB |
実行使用メモリ | 8,948 KB |
最終ジャッジ日時 | 2024-06-24 17:19:04 |
合計ジャッジ時間 | 4,633 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> P; typedef pair<ll, P> P3; typedef pair<P ,P> PP; constexpr ll MOD = ll(1e9) + 7; constexpr int IINF = INT_MAX; constexpr ll LLINF = LLONG_MAX; constexpr int MAX_N = int(1e5) + 5; constexpr double EPS = 1e-8; constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0}; #define REP(i, n) for (int i = 0; i < n; i++) #define REPR(i, n) for (int i = n; i >= 0; i--) #define SORT(v) sort((v).begin(), (v).end()) #define SORTR(v) sort((v).rbegin(), (v).rend()) #define ALL(v) (v).begin(), (v).end() template <typename Monoid> struct SegmentTree{ private: using F = function<Monoid(Monoid, Monoid)>; int N; vector<Monoid> node; F f; Monoid e; // identity element public: SegmentTree(){} SegmentTree(F f, Monoid e):f(f), e(e){} void init(int sz){ N = 1; while(N < sz) N <<= 1; node.assign(2*N-1, e); } void build(vector<Monoid>& v){ int sz = int(v.size()); init(sz); for(int i=0; i<sz; i++){ node[i+N-1] = v[i]; } for(int i=N-2; i>=0; i--){ node[i] = f(node[i*2+1], node[i*2+2]); } } void update(int k, Monoid x){ k += N-1; node[k] = x; while(k > 0){ k = (k-1)/2; node[k] = f(node[2*k+1], node[2*k+2]); } } // [a,b) Monoid query(int a, int b){return query(a, b, 0, 0, N);} Monoid query(int a, int b, int k, int l, int r){ if(b <= l || r <= a) return e; if(a <= l && r <= b) return node[k]; Monoid vl, vr; vl = query(a, b, 2*k+1, l, (l+r)/2); vr = query(a, b, 2*k+2, (l+r)/2, r); return f(vl, vr); } }; int main() { int n, q; cin >> n >> q; vector<P> a(n); for(int i=0;i<n;i++){ cin >> a[i].first; a[i].second = i+1; } auto f = [](P x, P y){return min(x,y);}; SegmentTree<P> seg(f,P(IINF,IINF)); seg.build(a); for(int i=0;i<q;i++){ int c, l ,r; cin >> c >> l >> r; l--; if(c == 1){ r--; P x, y; x = seg.query(l,l+1); y = seg.query(r,r+1); x.second = r+1; y.second = l+1; seg.update(l,y); seg.update(r,x); } else{ cout << seg.query(l,r).second << endl; } } return 0; }