結果
問題 |
No.1234 典型RMQ
|
ユーザー |
![]() |
提出日時 | 2020-09-19 00:56:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 299 ms / 2,000 ms |
コード長 | 2,684 bytes |
コンパイル時間 | 2,754 ms |
コンパイル使用メモリ | 200,892 KB |
最終ジャッジ日時 | 2025-01-14 18:17:02 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include<bits/stdc++.h> using namespace std; long long LM = 1LL << 60; class sqrt_decomp { class node { int l, r; vector<long long> raw; long long ad; long long res; inline void eval_all() { res = LM; for (auto& i : raw) { i += ad; res = min(res, i); } ad = 0; } public: node(const vector<long long>& v, int l, int r) : l(l), r(r), ad(0), res(LM) { raw = vector<long long>(r - l); for (int i = l; i < r; ++i) { raw[i - l] = v[i]; res = min(res, v[i]); } } inline long long calc(int _l, int _r) { if (r <= _l || _r <= l) { return LM; } else if (_l <= l && r <= _r) { return res; } else { eval_all(); long long res = LM; for (int i = max(l, _l); i < min(r, _r); ++i) { res = min(res, raw[i - l]); } return res; } } inline void update(int _l, int _r, long long _ad) { if (r <= _l || _r <= l) { return; } else if (_l <= l && r <= _r) { res += _ad; ad += _ad; } else { // eval_all(); for (int i = max(l, _l); i < min(r, _r); ++i) { raw[i - l] += _ad; } eval_all(); } } }; vector<node> v; public: sqrt_decomp(const vector<long long>& a, int bucket_size) { v = vector<node>(); for (int i = 0; i < (int)a.size(); i += bucket_size) { v.emplace_back(a, i, min(i + bucket_size, (int)a.size())); } } void update(int l, int r, long long ad) { for (auto& i : v) { i.update(l, r, ad); } } long long run(int l, int r) { long long res = LM; for (auto& i : v) { res = min(res, i.calc(l, r)); } return res; } }; int main() { cin.tie(0); ios::sync_with_stdio(0); int n; cin >> n; vector<long long> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } sqrt_decomp sd(a, 300); int q; cin >> q; for (int _ = 0; _ < q; ++_) { int t, l, r, c; cin >> t >> l >> r >> c; --l; if (t == 1) { sd.update(l, r, c); } else { cout << sd.run(l, r) << '\n'; } } return 0; }