結果
問題 | No.1234 典型RMQ |
ユーザー |
![]() |
提出日時 | 2020-09-18 22:01:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 149 ms / 2,000 ms |
コード長 | 3,397 bytes |
コンパイル時間 | 1,433 ms |
コンパイル使用メモリ | 98,912 KB |
最終ジャッジ日時 | 2025-01-14 17:11:21 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <iostream>#include <vector>#include <string>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>using namespace std;using ll = long long;struct SegmentTree {struct Lazy {static constexpr Lazy e() {return { 0 };}bool operator==(const Lazy &o) const {return c == o.c;}Lazy &operator*=(const Lazy &o) {return *this = { c + o.c };}ll c;};struct Node {static constexpr Node e() {return { 1LL << 60 };}Node operator*(const Node &o) const {return { min(v, o.v) };}Node &act(int w, const Lazy &o) {return *this = { v + o.c };}ll v;};SegmentTree(int n) : n(n) {for (m = 2; m < n; m *= 2);t = vector<Node>(m + n + n % 2, Node::e());z = vector<Lazy>(m, Lazy::e());}Node &operator[](int i) {return t[m + i];}const Node &root() const {return t[1];}void build() {for (int i = (n - 1 + m) / 2; i > 0; i--) t[i] = t[i * 2] * t[i * 2 + 1];}void update(int i, const Node &o) {i += m;for (int j = m; j >= 2; j /= 2) propagate(i / j, j);for (t[i] = o; i /= 2, i > 0;) t[i] = t[i * 2] * t[i * 2 + 1];}Node query(int l, int r, int i = 1, int il = 0, int ir = -1) {if (ir < 0) ir = m;if (l <= il && ir <= r) return t[i];propagate(i, ir - il);Node o = Node::e();int ic = (il + ir) / 2;if (l < ic) o = o * query(l, r, i * 2 + 0, il, ic);if (ic < r) o = o * query(l, r, i * 2 + 1, ic, ir);return o;}void range_act(int l, int r, Lazy x, int i = 1, int il = 0, int ir = -1) {if (ir < 0) ir = m;if (l <= il && ir <= r) { act(i, ir - il, x); return; }propagate(i, ir - il);int ic = (il + ir) / 2;if (l < ic) range_act(l, r, x, i * 2 + 0, il, ic);if (ic < r) range_act(l, r, x, i * 2 + 1, ic, ir);t[i] = t[i * 2] * t[i * 2 + 1];}void propagate(int i, int w) {if (z[i] == Lazy::e()) return;for (int j = 0; j < 2; j++) act(i * 2 + j, w / 2, z[i]);z[i] = Lazy::e();}void act(int i, int w, Lazy x) {t[i].act(w, x);if (i < m) z[i] *= x;}//void print() {// for (int j = 1; j <= m; j *= 2) {// int k = min(j * 2, m + n);// for (int i = j; i < k; i++) {// if (j < m) {// cout << t[i].v << ':' << z[i] << string(m / j * 2 - 4, ' ') << " \n"[i == k - 1];// } else {// cout << t[i].v << " \n"[i == k - 1];// }// }// }//}vector<Node> t;vector<Lazy> z;int n, m;};int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;SegmentTree st(n);for (int i = 0; i < n; i++) {ll a;cin >> a;st[i] = { a };}st.build();int q;cin >> q;while (q--) {int k, l, r, c;cin >> k >> l >> r >> c;l--;if (k == 1) {st.range_act(l, r, { c });} else {cout << st.query(l, r).v << '\n';}}return 0;}