結果
問題 |
No.875 Range Mindex Query
|
ユーザー |
|
提出日時 | 2019-09-08 00:12:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 66 ms / 2,000 ms |
コード長 | 2,132 bytes |
コンパイル時間 | 1,839 ms |
コンパイル使用メモリ | 194,696 KB |
最終ジャッジ日時 | 2025-01-07 17:22:36 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:60:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 60 | scanf("%d%d", &N, &Q); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:64:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 64 | scanf("%d", &a); | ~~~~~^~~~~~~~~~ main.cpp:70:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 70 | scanf("%d%d%d", &t, &l, &r); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename Tp> class segtree{ Tp *tree; Tp (*operation)(const Tp&, const Tp&); Tp ident; size_t len, depth; public: segtree(size_t n, Tp (*op)(const Tp&, const Tp&), Tp id) : operation(op), ident(id){ for(depth=1;(1ULL<<depth)<n;++depth); len = 1ULL<<depth; ++depth; tree = new Tp[2*len]; for(size_t i=0;i<2*len;++i) tree[i] = id; } ~segtree(){ delete[] tree; } void update(size_t pos, Tp val){ tree[len+pos] = val; for(size_t p=(len+pos)>>1;p>0;p>>=1){ tree[p] = operation(tree[2*p], tree[2*p+1]); } } void add(size_t pos, Tp val){ tree[len+pos] += val; for(size_t p=(len+pos)>>1;p>0;p>>=1){ tree[p] = operation(tree[2*p], tree[2*p+1]); } } Tp queue(size_t left, size_t right){ Tp lval = ident, rval = ident; left += len; right += len; while(true){ if(left >= right) return operation(lval, rval); if(right - left == 1) return operation(lval, operation(tree[left], rval)); if(left & 1) lval = operation(lval, tree[left++]); left >>= 1; if(right & 1) rval = operation(tree[right-1], rval); right >>= 1; } } Tp &operator[](size_t pos){ return tree[len+pos]; } void refresh(){ for(size_t p=len-1;p>0;--p){ tree[p] = operation(tree[2*p], tree[2*p+1]); } } }; int main(){ int N, Q; int a, t, l, r; scanf("%d%d", &N, &Q); segtree<pair<int,int>> st(N, [](auto x, auto y){ return min(x, y); }, {N+1, -1}); for(int i=0;i<N;++i){ scanf("%d", &a); st[i] = {a, i+1}; } st.refresh(); for(int i=0;i<Q;++i){ scanf("%d%d%d", &t, &l, &r); if(t==1){ int tmp = st[l-1].first; st.update(l-1, {st[r-1].first, st[l-1].second}); st.update(r-1, {tmp, st[r-1].second}); } else printf("%d\n", st.queue(l-1, r).second); } return 0; }