結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー nejineji
提出日時 2019-10-25 19:49:42
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 302 ms / 2,000 ms
コード長 2,406 bytes
記録
コンパイル時間 1,764 ms
コンパイル使用メモリ 175,428 KB
実行使用メモリ 8,656 KB
最終ジャッジ日時 2024-07-21 19:17:43
合計ジャッジ時間 5,706 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;

#define REP(i,x,y) for(ll i=x; i<=y; i++)
#define BIT(t) ((long long 1) << t)
#define PER(i,y,x) for(ll i=y; i>=x; i--)
#define SIZE(v) ll(v.size())
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define pll pair<ll,ll>
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
typedef long long ll;

struct segtree {
       vector<pll> tree;

       pll op(pll x, pll y) {
               return min(x, y);
       }
       pll const INIT_VALUE = {0, 0};
       ll n_ = 1;

       segtree(ll n) {
               while (n_ <= n) {
                       n_ *= 2;
               }
               tree = vector<pll>(n_ * 2 + 1, INIT_VALUE);
       }

       //k番目をxでupdate
       void update(ll k, ll x) {
               k += n_;
               tree[k] = {x, k-n_};
               while (k >= 1) {
                       k /= 2;
                       tree[k] = op(tree[k * 2], tree[k * 2 + 1]);
               }
       }

       pll val_o(ll a, ll b, ll k, ll l, ll r) {
               if (a <= l && r <= b) {
                       return tree[k];
               }
               else if (r <= a || b <= l) {
                       return {1e18, 0};
               }
               else {
                       pll x1 = val_o(a, b, k * 2, l, (l + r) / 2);
                       pll x2 = val_o(a, b, k * 2 + 1, (l + r) / 2, r);
                       return op(x1, x2);
               }

       }

       //[a,b)のvalueを求める
       pll val(ll a, ll b) {
               return val_o(a, b, 1, 0, n_);
       }

       ll val(ll a){
               return tree[a + n_].first;
       }
};

int main(){
        ll n, q;
        cin >> n >> q;
        segtree tree(n+1);
        REP(i,1,n){
                ll x;
                cin >> x;
                tree.update(i, x);
        }
        vll ans;
        REP(iii,1,q){
                ll c, l, r;
                cin >> c >> l >> r;
                if(c == 1){
                        ll x = tree.val(l);
                        ll y = tree.val(r);
                        tree.update(l, y);
                        tree.update(r, x);
                }
                else{
                        ans.push_back(tree.val(l, r+1).second);
                }
        }
        REP(i,0,ans.size() - 1){
                cout << ans[i];
                cout << endl;
        }
        
}
0