結果

問題 No.1234 典型RMQ
ユーザー poohbearpoohbear
提出日時 2020-09-18 22:11:04
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 341 ms / 2,000 ms
コード長 4,607 bytes
コンパイル時間 2,231 ms
コンパイル使用メモリ 208,704 KB
実行使用メモリ 10,188 KB
最終ジャッジ日時 2023-08-08 18:44:03
合計ジャッジ時間 10,461 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 309 ms
8,304 KB
testcase_07 AC 252 ms
4,376 KB
testcase_08 AC 341 ms
9,588 KB
testcase_09 AC 292 ms
6,388 KB
testcase_10 AC 314 ms
8,892 KB
testcase_11 AC 294 ms
7,792 KB
testcase_12 AC 286 ms
5,896 KB
testcase_13 AC 255 ms
4,376 KB
testcase_14 AC 285 ms
6,208 KB
testcase_15 AC 283 ms
5,504 KB
testcase_16 AC 318 ms
8,848 KB
testcase_17 AC 281 ms
6,312 KB
testcase_18 AC 237 ms
4,384 KB
testcase_19 AC 331 ms
9,600 KB
testcase_20 AC 220 ms
10,100 KB
testcase_21 AC 302 ms
7,832 KB
testcase_22 AC 258 ms
10,020 KB
testcase_23 AC 248 ms
9,992 KB
testcase_24 AC 244 ms
10,112 KB
testcase_25 AC 242 ms
10,020 KB
testcase_26 AC 252 ms
10,188 KB
testcase_27 AC 1 ms
4,380 KB
testcase_28 AC 1 ms
4,380 KB
testcase_29 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(a,n) for (ll a = 0; a < (n); ++a)
using namespace std;
using ll = long long;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
typedef vector<vector<ll> > Graph;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1e18;

template<typename T,typename M>
struct SegTree{
    using FX = function<T(T,T)>;//T●T->Tとなる関数の型
    using FA = function<T(T,M)>;
    using FM = function<M(M,M)>;
    using FP = function<M(M,ll)>;
    ll n;
    FX fx;
    FA fa;
    FM fm;
    FP fp;
    const T ex;//単位元
    const M em;
    vector<T> node;
    vector<M> lazy;
    SegTree(ll n_, FX fx_, FA fa_,FM fm_, FP fp_ ,T ex_,M em_)
        : n(),fx(fx_),fa(fa_),fm(fm_),fp(fp_),ex(ex_),em(em_),node(n_*4,ex),lazy(n_*4,em){
        ll x = 1;
        while(n_>x)x*=2;
        n=x;
    }

    void set(ll i,T x){
        node[i+n-1] = x;
    }

    void build(){
        for(ll k=n-2;k>=0;k--)node[k]=fx(node[2*k+1],node[2*k+2]);
    }

    void eval(ll k,ll len){
        if(lazy[k]==em)return;//更新がなければ終了
        if(k<n-1){//葉でなければ子に伝搬
            lazy[k*2+1]=fm(lazy[k*2+1],lazy[k]);
            lazy[k*2+2]=fm(lazy[k*2+2],lazy[k]);
        }
        //自身の更新
        node[k]=fa(node[k],fp(lazy[k],len));
        lazy[k]=em;
    }

    void update(ll a, ll b, M x, ll k, ll l, ll r){
        eval(k,r-l);
        if(a<=l&&r<=b){  //完全に内側
            lazy[k]=fm(lazy[k],x);
            eval(k,r-l);
        }
        else if(a<r && l<b){  //一部区間がかぶる
            update(a,b,x,k*2+1,l,(l+r)/2);
            update(a,b,x,k*2+2,(l+r)/2,r);
            node[k]=fx(node[k*2+1],node[k*2+2]);
        }
    }

    void update(ll a,ll b,M x){
        update(a,b,x,0,0,n);
    }

    T query_sub(ll a,ll b,ll k,ll l,ll r){
        eval(k,r-l);
        if(r<=a || b<=l){
            return ex;
        }
        else if(a<=l && r<=b){
            return node[k];
        }
        else{
            T vl = query_sub(a,b,k*2+1,l,(l+r)/2);
            T vr = query_sub(a,b,k*2+2,(l+r)/2,r);
            return fx(vl,vr);
        }
    }

    T query(ll a,ll b){
        return query_sub(a,b,0,0,n);
    }

    T operator[](ll i){
        return query(i,i+1);
    }

    void print(){//デバッグ用
        for(ll i=0;i<n;i++){
            cout << (*this)[i];
            if(i != n-1)cout << ',';
        }
        cout << endl;
    }

    //二分探索で[a,b)でx以下の値を持つ最右の要素位置を見つける
    //コメントアウトするとx以上にもできる
    //全てx以下なら-1を返す
    //後々抽象化出来たらいいな
    ll find_right(ll a,ll b,ll x,ll k,ll l,ll r){
        eval(k,r-l);
        if(node[k]>x||r<=a||b<=l)return -1;
        //if(node[k]<x||r<=a||b<=l)return -1;
        if(k>=n-1)return (k-(n-1));
        ll rv = find_right(a,b,x,2*k+2,(l+r)/2,r);
        if(rv!=-1)return rv;
        return find_right(a,b,x,2*k+1,l,(l+r)/2);
    }

    ll find_right(ll a,ll b,ll x){
        return find_right(a,b,x,0,0,n);
    }

    //二分探索で[a,b)でx以下の値を持つ最左の要素位置を見つける
    //コメントアウトするとx以上にもできる
    //全てx以下なら-1を返す
    ll find_left(ll a,ll b,ll x,ll k,ll l,ll r){
        eval(k,r-l);
        if(node[k]>x||r<=a||b<=l)return -1;
        //if(node[k]<x||r<=a||b<=l)return -1;
        if(k>=n-1)return (k-(n-1));
        ll lv = find_left(a,b,x,2*k+1,l,(l+r)/2);
        if(lv!=-1)return lv;
        return find_left(a,b,x,2*k+2,(l+r)/2,r);
    }

    ll find_left(ll a,ll b,ll x){
        return find_left(a,b,x,0,0,n);
    }
};

int main(){
    ll n;
    cin >> n;
    vector<ll>a(n);
    rep(i,n)cin>>a[i];
    ll q;
    cin >> q;
    using X = long long;
    using M = long long;
    auto fx = [](X x1, X x2) -> X { return min(x1,x2); };
    auto fa = [](X x, M m) -> X { return x + m; };
    auto fm = [](M m1, M m2) -> M { return m1+m2; };
    auto fp = [](M m, long long t) -> M { return m; };
    long long ex = numeric_limits<ll>::max();
    long long em = 0;
    SegTree<X, M> seg(n, fx, fa, fm, fp, ex, em);
    rep(i,n){
        seg.set(i,a[i]);
    }
    seg.build();
    rep(i,q){
        ll k,l,r,c;
        cin >> k >> l >> r >> c;
        l--;r--;
        if(k==1){
            seg.update(l,r+1,c);
        }
        else{
            cout << seg.query(l,r+1) << endl;
        }
    }
    return 0;
}
0