結果
問題 | No.1234 典型RMQ |
ユーザー |
|
提出日時 | 2020-09-19 03:01:31 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 188 ms / 2,000 ms |
コード長 | 6,146 bytes |
コンパイル時間 | 15,583 ms |
コンパイル使用メモリ | 299,456 KB |
最終ジャッジ日時 | 2025-01-14 18:33:45 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("03")#pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>using namespace std;using ld = long double;using ll = long long;using ull = unsigned long long;#define endl "\n"#define FOR(i, a, b) for (int i = (a); i <= (b); i++)#define rep(i, n) for (int i = 0; i < (n); i++)#define PII pair<int, int>#define PLL pair<ll, ll>#define ALL(x) (x).begin(), (x).end()int dx[] = {1, 0, -1, 0};int dy[] = {0, 1, 0, -1};constexpr int INF = 1 << 30;constexpr ll LINF = 1LL << 40;constexpr ll mod = 1e9 + 7;void flush() { cout << flush; }template <class T>vector<T> vec(int len, T elem) {return vector<T>(len, elem);} // auto dp = vec(52, vec(103, vec(103, INF)));template <class T>inline bool chmax(T &a, const T &b) {if (a < b) {a = b;return 1;}return 0;}template <class T>inline bool chmin(T &a, const T &b) {if (b < a) {a = b;return 1;}return 0;}template <class T>inline int popcount(T a) {return __builtin_popcountll(a);}template <class T>inline T emod(T a, T p) {return (a % p + p) % p;}template <typename T>istream &operator>>(istream &is, vector<T> &vec) {for (auto &v : vec) is >> v;return is;}template <typename T>ostream &operator<<(ostream &os, const vector<T> &vec) {os << '\n';for (auto v : vec) os << v << ' ';os << '\n';return os;}template <typename T>ostream &operator<<(ostream &os, const deque<T> &vec) {os << "deq[";for (auto v : vec) os << v << ',';os << ']';return os;}template <typename T>ostream &operator<<(ostream &os, const set<T> &vec) {os << '{';for (auto v : vec) os << v << ',';os << '}';return os;}template <typename T>ostream &operator<<(ostream &os, const unordered_set<T> &vec) {os << '{';for (auto v : vec) os << v << ',';os << '}';return os;}template <typename T>ostream &operator<<(ostream &os, const multiset<T> &vec) {os << '{';for (auto v : vec) os << v << ',';os << '}';return os;}template <typename T>ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) {os << '{';for (auto v : vec) os << v << ',';os << '}';return os;}template <typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2> &pa) {os << '(' << pa.first << ',' << pa.second << ')';return os;}template <typename TK, typename TV>ostream &operator<<(ostream &os, const map<TK, TV> &mp) {os << '{';for (auto v : mp) os << v.first << "=>" << v.second << ',';os << '}';return os;}template <typename TK, typename TV>ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) {os << '{';for (auto v : mp) os << v.first << "=>" << v.second << ',';os << '}';return os;}struct MyIO {MyIO() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}} IO_OI;#ifdef LOCALvoid debug_out() { cerr << endl; }template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) {cerr << " " << H;debug_out(T...);}#define debug(...) \cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl#else#define debug(...) (void(0))#define dump(x) (void(0))#endif//-------------------template <class T, class E>struct SegmentTree {using F = function<T(T, T)>;using G = function<T(T, E)>;using H = function<E(E, E)>;using P = function<E(E, int)>;int n;F f;G g; // pで変換したものをdataに移す時H h; // lazyを遷移させる時P p; // lazyを必要な形に変換T d1;E d0;vector<T> dat;vector<E> laz;SegmentTree(int n_, F f, G g, H h, T d1, E d0, vector<T> v = vector<T>(),P p = [](E a, int b) { return a; }): f(f), g(g), h(h), d1(d1), d0(d0), p(p) {init(n_);if (n_ == (int)v.size()) build(n_, v);}void init(int n_) {n = 1;while (n < n_) n *= 2;dat.clear();dat.resize(2 * n - 1, d1);laz.clear();laz.resize(2 * n - 1, d0);}void build(int n_, vector<T> v) {for (int i = 0; i < n_; i++) dat[i + n - 1] = v[i];for (int i = n - 2; i >= 0; i--)dat[i] = f(dat[i * 2 + 1], dat[i * 2 + 2]);}inline void eval(int len, int k) {if (laz[k] == d0) return;if (k * 2 + 1 < n * 2 - 1) {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], p(laz[k], len));laz[k] = d0;}T update(int a, int b, E x, int k, int l, int r) {eval(r - l, k);if (r <= a || b <= l) return dat[k];if (a <= l && r <= b) {laz[k] = h(laz[k], x);return g(dat[k], p(laz[k], r - l));}return dat[k] = f(update(a, b, x, k * 2 + 1, l, (l + r) / 2),update(a, b, x, k * 2 + 2, (l + r) / 2, r));}T update(int a, int b, E x) { return update(a, b, x, 0, 0, n); }T _query(int a, int b, int k, int l, int r) {eval(r - l, k);if (r <= a || b <= l) return d1;if (a <= l && r <= b) return dat[k];T vl = _query(a, b, k * 2 + 1, l, (l + r) / 2);T vr = _query(a, b, k * 2 + 2, (l + r) / 2, r);return f(vl, vr);}T query(int a, int b) { return _query(a, b, 0, 0, n); }};// END CUT HEREsigned main() {int n, q;cin >> n;vector<ll> a(n);cin >> a >> q;debug(a);SegmentTree<ll, ll> ch(n, [&](ll l, ll r) { return min(l, r); },[](ll l, ll r) { return l + r; }, [](ll l, ll r) { return l + r; },LINF, 0LL, a);while (q--) {int k, l, r;cin >> k >> l >> r;ll c;cin >> c;if (k == 1) {ch.update(l - 1, r, c);} else {cout << ch.query(l - 1, r) << endl;}}}