結果
問題 | No.875 Range Mindex Query |
ユーザー |
![]() |
提出日時 | 2020-03-08 15:30:09 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 354 ms / 2,000 ms |
コード長 | 2,047 bytes |
コンパイル時間 | 1,760 ms |
コンパイル使用メモリ | 174,452 KB |
実行使用メモリ | 12,928 KB |
最終ジャッジ日時 | 2024-11-07 06:37:04 |
合計ジャッジ時間 | 5,359 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 |
ソースコード
#include "bits/stdc++.h" using namespace std; template<typename Mono> class SegmentTree { private: using F = function<Mono(Mono, Mono)>; vector<Mono> Node; long long Size; const F f; const Mono Unit; public: SegmentTree(long long N, const F f, const Mono& M) : f(f), Unit(M) { Size = 1; while (Size < N) Size <<= 1; Node.assign(Size * 2, Unit); } void Set(long long N, long long X) { Node[N + Size] = X; } void Set(vector<Mono> V) { for (int i = 0; i < V.size(); i++) { Set(i, V[i]); } for (int i = Size - 1; i > 0; i--) Node[i] = f(Node[i * 2], Node[i * 2 + 1]); } void Set(Mono V[], long long S) { for (int i = 0; i < S; i++) { Set(i, V[i]); } for (int i = Size - 1; i > 0; i--) Node[i] = f(Node[i * 2], Node[i * 2 + 1]); } void update(long long K, long long X) { K += Size; Node[K] = X; while (K >>= 1) Node[K] = f(Node[K * 2], Node[K * 2 + 1]); } Mono query(long long A, long long B, long long K = 1, long long L = 0, long long R = -1) { if (R == -1) R = Size; if (B <= L || R <= A) return Unit; if (A <= L && R <= B) return Node[K]; return f(query(A, B, K * 2, L, (L + R) / 2), query(A, B, K * 2 + 1, (L + R) / 2, R)); } Mono operator[](const long long K) const { return Node[K + Size]; }; long long size() { return Size; }; void put() { printf("%ld\n", Size); for (int i = 1; i < Size * 2; i++) { printf("%ld", Node[i]); if (i == Size * 2 - 1) printf("\n"); else printf(" "); } } }; int main() { long long N, Q, INF = 1000000000000000000; cin >> N >> Q; vector<long long> A(N); map<long long, long long> mp; for (int i = 0; i < N; i++) { cin >> A[i]; mp[A[i]] = i; } SegmentTree<long long> Seg(N, [](long long A, long long B) {return min(A, B); }, INF); Seg.Set(A); for (int i = 0; i < Q; i++) { long long T, L, R; cin >> T >> L >> R; if (T == 1) { L--, R--; mp[A[R]] = L, mp[A[L]] = R; Seg.update(L, A[R]); Seg.update(R, A[L]); swap(A[L], A[R]); } else { L--; cout << mp[Seg.query(L, R)] + 1 << endl; } } }