#555155 (C++17) No.1234 典型RMQ

• 問題: No.1234 典型RMQ
• ユーザー: hamamu
• 提出日時: 2020-09-18 22:24:57
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 124 ms / 2,000 ms
• コード長: 6,495 bytes
• コンパイル時間: 2,206 ms
• コンパイル使用メモリ: 208,636 KB
• 最終ジャッジ日時: 2025-01-14 17:25:18
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 27

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
·#include "bits/stdc++.h"
using namespace std;
using     ll=long long;
using    vll=vector<   ll>;
using   vvll=vector<  vll>;
using  vvvll=vector< vvll>;
using vvvvll=vector<vvvll>;
constexpr ll INF = 1LL << 60;
struct Fast{ Fast(){ cin.tie(0); ios::sync_with_stdio(false); cout<<fixed<<setprecision(numeric_limits<double>::max_digits10); } } fast;
#define REPS(i, S, E) for (ll i = (S); i <= (E); i++)
#define REP(i, N) REPS(i, 0, (N)-1)
#define DEPS(i, S, E) for (ll i = (E); i >= (S); i--)
#define DEP(i, N) DEPS(i, 0, (N)-1)
#define rep(i, S, E)  for (ll i = (S); i <= (E); i++)
#define dep(i, E, S)  for (ll i = (E); i >= (S); i--)
#define each(e, v) for (auto&& e : v)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; }return false; }
template<class T> inline T MaxE(vector<T>&v,ll S,ll E){ T m=v[S]; rep(i,S,E)chmax(m,v[i]); return m; }
template<class T> inline T MinE(vector<T>&v,ll S,ll E){ T m=v[S]; rep(i,S,E)chmin(m,v[i]); return m; }
template<class T> inline T MaxE(vector<T> &v) { return MaxE(v,0,(ll)v.size()-1); }
template<class T> inline T MinE(vector<T> &v) { return MinE(v,0,(ll)v.size()-1); }
template<class T> inline T Sum(vector<T> &v,ll S,ll E){ T s=T(); rep(i,S,E)s+=v[i]; return s; }
template<class T> inline T Sum(vector<T> &v) { return Sum(v,0,v.size()-1); }
template<class T> inline ll sz(T &v){ return (ll)v.size(); }
inline ll CEIL(ll a,ll b){ return (a<0) ? -(-a/b) : (a+b-1)/b; }
inline ll FLOOR(ll a,ll b){ return -CEIL(-a,b); }
#if 0
#include <atcoder/all>
using namespace atcoder;
#endif
template <class T, class E> struct LazySegmentTree{
    using F = function<T(T, T)>;
    using G = function<T(T, E)>;
    using H = function<E(E, E)>;
    F f; //!< データ同士の合成関数
    G g; //!< 作用関数
    H h; //!< 作用素同士の合成関数
    T ti; //!< データの単位元 実際の単位元をセットしないとだめ
    E ei; //!< 作用素の単位元 実際の単位元ではなくても、使わない値ならOK
    ll n=1; //!< データ数の2べき上界
    vector<T> dat;
    vector<E> laz;
    LazySegmentTree() {}
    LazySegmentTree(vector<T> &v, F f, G g, H h, T ti, E ei) { Init(v, f, g, h, ti, ei); }
    void Init(vector<T> &v, F f, G g, H h, T ti, E ei){
        this->f=f; this->g=g; this->h=h; this->ti=ti; this->ei=ei;
        while (n<(ll)v.size()) n<<=1;
        dat.resize(2*n-1, ti);
        laz.resize(2*n-1, ei);
        for (ll i=0; i<(ll)v.size(); i++) dat[n-1+i] = v[i];
        for (ll i=n-2; i>=0; i--) dat[i] = f(dat[2*i+1], dat[2*i+2]);
    }
    void Update(ll a, ll b, E x){ update(a, b+1, x, 0, 0, n); } //[a,b]にxを作用
    void update(ll a, ll b, E x, ll k, ll l, ll r){ //注目ノードk=[l,r)
        if (r<=a || b<=l) eval(k); //[l,r)が[a,b)と重ならない時
        else if (a<=l && r<=b){ //[l,r)が[a,b)の内側の時
            laz[k] = h(laz[k], x);
            eval(k); //親ノードが後でdat[k]を見るため、ここで評価しておく必要あり
        }
        else { //[l,r)が[a,b)から一部はみ出す時
            eval(k); //子ノードを処理する前に評価しておく必要あり
            update(a, b, x, k*2+1, l, (l+r)/2);
            update(a, b, x, k*2+2, (l+r)/2, r);
            dat[k] = f(dat[k*2+1], dat[k*2+2]);
        }
    }
    T Range(ll a, ll b) { return range(a, b+1, 0, 0, n); }//[a,b]の値を取得
    T range(ll a, ll b, ll k, ll l, ll r){ //注目ノードk=[l,r)
        if (r<=a || b<=l) return ti; //[l,r)が[a,b)と重ならない時
        eval(k); //自分や子の値を見る前に評価が必要
        if (a<=l && r<=b) return dat[k];//[l,r)が[a,b)の内側の時
        return f(range(a, b, k*2+1, l, (l+r)/2), range(a, b, k*2+2, (l+r)/2, r));
        //[l,r)が[a,b)から一部はみ出す時
    }
    ll FindL(ll a, ll b, T x) { return findL(a, b+1, x, 0, 0, n); }
    ll findL(ll a, ll b, T x, ll k, ll l, ll r){ //[l,r)内最左 なければb
        if (r<=a || b<=l) return b; //範囲外
        eval(k);
        if (f(dat[k], x) != dat[k]) return b; //条件を満たさない
        if (n-1 <= k) return k-(n-1); //葉なら見つかった→位置return
        ll        i = findL(a, b, x, 2*k+1, l, (l+r)/2); //左部分木探す
        if (i==b) i = findL(a, b, x, 2*k+2, (l+r)/2, r); //左になければ右
        return i;
    }
    ll FindR(ll a, ll b, T x) { return findR(a, b+1, x, 0, 0, n); }
    ll findR(ll a, ll b, T x, ll k, ll l, ll r){ //[l,r)内最右 なければa-1
        if (r<=a || b<=l) return a-1; //範囲外
        eval(k);
        if (f(dat[k], x) != dat[k]) return a-1; //条件を満たさない
        if (n-1 <= k) return k-(n-1); //葉なら見つかった→位置return
        ll          i = findR(a, b, x, 2*k+2, (l+r)/2, r); //右部分木探す
        if (i==a-1) i = findR(a, b, x, 2*k+1, l, (l+r)/2); //右になければ左
        return i;
    }
    void eval(ll k){
        if (laz[k] == ei) return;
        if (k<=n-2){ //子に作用素を配る
            laz[k*2+1] = h(laz[k*2+1], laz[k]);
            laz[k*2+2] = h(laz[k*2+2], laz[k]);
        }
        //自分に作用させる
        dat[k] = g(dat[k], laz[k]);
        laz[k] = ei;
    }
    void Dump(ll w=5){
        auto disp=[&](ll x){
            if (x==-INF) cerr << setw(w) << "-INF";
            else if (x== INF) cerr << setw(w) << "INF";
            else              cerr << setw(w) << x;
        };
        REP(i, n) for (ll k=i+n-1, m=1, p=1; k>=0; p=m, m*=k%2, k=(k==0)?-1:(k-1)/2){
            if (m){
                cerr << ((k<n-1)?" ┬ ":""); disp(dat[k]); cerr<<" /"; disp(laz[k]);
            }
            else{
                cerr << ((p&~m) ?" ┘ ":"");
            }
            if (k==0) cerr << '\n';
        } cerr << '\n';
    }
};
void solve()
{
    ll n;  cin >> n;
    vector<ll> a(n);  rep(i,0,n-1){ ll a_; cin>>a_; a[i]=a_; }
    LazySegmentTree<ll, ll> sgt(
        a,
        [](ll x, ll y){ return min(x, y); },//データ同士の合成関数
        [](ll x, ll y){ return x + y; },//データxに作用素yを作用させる関数
        [](ll x, ll y){ return x + y; },//作用素の合成関数
        INF, //データの単位元 実際の単位元をセットしないとだめ
        0); //作用素の単位元 実際の単位元ではなくても、使わない値ならOK
    ll q;  cin >> q;
    rep(qq,0,q-1){
        ll k,l,r,c;  cin >> k >> l >> r >> c;
        l--;r--;
        if (k==1){
            sgt.Update(l, r, c);
        }
        else{//k=2
            ll ans=sgt.Range(l, r);
            cout << ans << '\n';
        }
    }
}
int main(){
#if 1
    solve();
#else
    ll t;  cin >> t;
    rep(i, 0, t-1){
        solve();
    }
#endif
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX