Submit Info #12412

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp ningenMe AC 900 ms 43.17 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.72 MiB
max_random_00 AC 900 ms 43.17 MiB
max_random_01 AC 897 ms 43.17 MiB
max_random_02 AC 890 ms 43.17 MiB
medium_00 AC 6 ms 0.80 MiB
medium_01 AC 4 ms 0.68 MiB
medium_02 AC 7 ms 0.68 MiB
random_00 AC 622 ms 22.28 MiB
random_01 AC 673 ms 42.54 MiB
random_02 AC 408 ms 11.67 MiB
small_00 AC 2 ms 0.67 MiB
small_01 AC 3 ms 0.67 MiB
small_02 AC 1 ms 0.67 MiB
small_03 AC 2 ms 0.68 MiB
small_04 AC 0 ms 0.71 MiB
small_05 AC 3 ms 0.68 MiB
small_06 AC 2 ms 0.67 MiB
small_07 AC 1 ms 0.67 MiB
small_08 AC 1 ms 0.68 MiB
small_09 AC 2 ms 0.68 MiB

#include <bits/stdc++.h> using namespace std; using ll = long long; #define ALL(obj) (obj).begin(),(obj).end() #define SPEED cin.tie(0);ios::sync_with_stdio(false); template<class T> using PQ = priority_queue<T>; template<class T> using PQR = priority_queue<T,vector<T>,greater<T>>; constexpr long long MOD = (long long)1e9 + 7; constexpr long long MOD2 = 998244353; constexpr long long HIGHINF = (long long)1e18; constexpr long long LOWINF = (long long)1e15; constexpr long double PI = 3.1415926535897932384626433L; template <class T> vector<T> multivector(size_t N,T init){return vector<T>(N,init);} template <class... T> auto multivector(size_t N,T... t){return vector<decltype(multivector(t...))>(N,multivector(t...));} template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}} template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;} template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;} template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;} template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;} template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;} template <template <class tmp> class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;} void print(void) {cout << endl;} template <class Head> void print(Head&& head) {cout << head;print();} template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);} template <class T> void chmax(T& a, const T b){a=max(a,b);} template <class T> void chmin(T& a, const T b){a=min(a,b);} void YN(bool flg) {cout << (flg ? "YES" : "NO") << endl;} void Yn(bool flg) {cout << (flg ? "Yes" : "No") << endl;} void yn(bool flg) {cout << (flg ? "yes" : "no") << endl;} /* * @title SegmentTreeBeats */ class SegmentTreeBeats { long long inf; size_t length; size_t height; vector<long long> node_max_first,node_max_second,count_max_first, node_min_first,node_min_second,count_min_first, node_sum,range,lazy_add,lazy_update; inline void internal_chmax(int k, long long x) { node_sum[k] += (x - node_max_first[k]) * count_max_first[k]; if(node_max_first[k] == node_min_first[k]) node_max_first[k] = node_min_first[k] = x; else if(node_max_first[k] == node_min_second[k]) node_max_first[k] = node_min_second[k] = x; else node_max_first[k] = x; if(lazy_update[k] != inf && x < lazy_update[k]) lazy_update[k] = x; } inline void internal_chmin(int k, long long x) { node_sum[k] += (x - node_min_first[k]) * count_min_first[k]; if(node_max_first[k] == node_min_first[k]) node_max_first[k] = node_min_first[k] = x; else if(node_max_second[k] == node_min_first[k]) node_min_first[k] = node_max_second[k] = x; else node_min_first[k] = x; if(lazy_update[k] != inf && lazy_update[k] < x) lazy_update[k] = x; } inline void internal_add(int k, long long x) { node_max_first[k] += x; if(node_max_second[k] != -inf) node_max_second[k] += x; node_min_first[k] += x; if(node_min_second[k] != inf) node_min_second[k] += x; node_sum[k] += range[k] * x; if(lazy_update[k] != inf) { lazy_update[k] += x; } else { lazy_add[k] += x; } } inline void internal_update(int k, long long x) { node_max_first[k] = x; node_max_second[k] = -inf; node_min_first[k] = x; node_min_second[k] = inf; count_max_first[k] = count_min_first[k] = range[k]; node_sum[k] = x * range[k]; lazy_update[k] = x; lazy_add[k] = 0; } inline void propagate(int k) { if(length-1 <= k) return; if(lazy_update[k] != inf) { internal_update(2*k+0, lazy_update[k]); internal_update(2*k+1, lazy_update[k]); lazy_update[k] = inf; return; } if(lazy_add[k] != 0) { internal_add(2*k+0, lazy_add[k]); internal_add(2*k+1, lazy_add[k]); lazy_add[k] = 0; } if(node_max_first[k] < node_max_first[2*k+0]) { internal_chmax(2*k+0, node_max_first[k]); } if(node_min_first[2*k+0] < node_min_first[k]) { internal_chmin(2*k+0, node_min_first[k]); } if(node_max_first[k] < node_max_first[2*k+1]) { internal_chmax(2*k+1, node_max_first[k]); } if(node_min_first[2*k+1] < node_min_first[k]) { internal_chmin(2*k+1, node_min_first[k]); } } inline void merge(int k) { node_sum[k] = node_sum[2*k+0] + node_sum[2*k+1]; if(node_max_first[2*k+0] < node_max_first[2*k+1]) { node_max_first[k] = node_max_first[2*k+1]; count_max_first[k] = count_max_first[2*k+1]; node_max_second[k] = max(node_max_first[2*k+0], node_max_second[2*k+1]); } else if(node_max_first[2*k+0] > node_max_first[2*k+1]) { node_max_first[k] = node_max_first[2*k+0]; count_max_first[k] = count_max_first[2*k+0]; node_max_second[k] = max(node_max_second[2*k+0], node_max_first[2*k+1]); } else { node_max_first[k] = node_max_first[2*k+0]; count_max_first[k] = count_max_first[2*k+0] + count_max_first[2*k+1]; node_max_second[k] = max(node_max_second[2*k+0], node_max_second[2*k+1]); } if(node_min_first[2*k+0] < node_min_first[2*k+1]) { node_min_first[k] = node_min_first[2*k+0]; count_min_first[k] = count_min_first[2*k+0]; node_min_second[k] = min(node_min_second[2*k+0], node_min_first[2*k+1]); } else if(node_min_first[2*k+0] > node_min_first[2*k+1]) { node_min_first[k] = node_min_first[2*k+1]; count_min_first[k] = count_min_first[2*k+1]; node_min_second[k] = min(node_min_first[2*k+0], node_min_second[2*k+1]); } else { node_min_first[k] = node_min_first[2*k+0]; count_min_first[k] = count_min_first[2*k+0] + count_min_first[2*k+1]; node_min_second[k] = min(node_min_second[2*k+0], node_min_second[2*k+1]); } } void _update_min(long long x, int a, int b, int k, int l, int r) { if(b <= l || r <= a || node_max_first[k] <= x) { return; } if(a <= l && r <= b && node_max_second[k] < x) { internal_chmax(k, x); return; } propagate(k); _update_min(x, a, b, 2*k+0, l, (l+r)/2); _update_min(x, a, b, 2*k+1, (l+r)/2, r); merge(k); } void _update_max(long long x, int a, int b, int k, int l, int r) { if(b <= l || r <= a || x <= node_min_first[k]) { return; } if(a <= l && r <= b && x < node_min_second[k]) { internal_chmin(k, x); return; } propagate(k); _update_max(x, a, b, 2*k+0, l, (l+r)/2); _update_max(x, a, b, 2*k+1, (l+r)/2, r); merge(k); } void _add_val(long long x, int a, int b, int k, int l, int r) { if(b <= l || r <= a) { return; } if(a <= l && r <= b) { internal_add(k, x); return; } propagate(k); _add_val(x, a, b, 2*k+0, l, (l+r)/2); _add_val(x, a, b, 2*k+1, (l+r)/2, r); merge(k); } void _update_val(long long x, int a, int b, int k, int l, int r) { if(b <= l || r <= a) { return; } if(a <= l && r <= b) { internal_update(k, x); return; } propagate(k); _update_val(x, a, b, 2*k+0, l, (l+r)/2); _update_val(x, a, b, 2*k+1, (l+r)/2, r); merge(k); } long long _query_max(int a, int b, int k, int l, int r) { if(b <= l || r <= a) { return -inf; } if(a <= l && r <= b) { return node_max_first[k]; } propagate(k); long long lv = _query_max(a, b, 2*k+0, l, (l+r)/2); long long rv = _query_max(a, b, 2*k+1, (l+r)/2, r); return max(lv, rv); } long long _query_min(int a, int b, int k, int l, int r) { if(b <= l || r <= a) { return inf; } if(a <= l && r <= b) { return node_min_first[k]; } propagate(k); long long lv = _query_min(a, b, 2*k+0, l, (l+r)/2); long long rv = _query_min(a, b, 2*k+1, (l+r)/2, r); return min(lv, rv); } public: SegmentTreeBeats(int num,long long inf = (1LL<<60)) : inf(inf){ for (length = 1,height = 0; length <= num; length *= 2, height++); node_max_first.resize(2*length); node_max_second.resize(2*length); count_max_first.resize(2*length); node_min_first.resize(2*length); node_min_second.resize(2*length); count_min_first.resize(2*length); node_sum.resize(2*length); range.resize(2*length); lazy_add.resize(2*length); lazy_update.resize(2*length); for(int i=0; i<2*length; ++i) lazy_add[i] = 0, lazy_update[i] = inf; range[1] = length; for(int i=1; i<length; ++i) range[2*i+0] = range[2*i+1] = (range[i] >> 1); for(int i=0; i<num; ++i) { node_max_first[length+i] = node_min_first[length+i] = node_sum[length+i] = 0; node_max_second[length+i] = -inf; node_min_second[length+i] = inf; count_max_first[length+i] = count_min_first[length+i] = 1; } for(int i=num; i<length; ++i) { node_max_first[length+i] = node_max_second[length+i] = -inf; node_min_first[length+i] = node_min_second[length+i] = inf; count_max_first[length+i] = count_min_first[length+i] = 0; } for(int i=length-1; i; --i) merge(i); } void range_chmin(int a, int b, long long x) { _update_min(x, a, b, 1, 0, length); } void range_chmax(int a, int b, long long x) { _update_max(x, a, b, 1, 0, length); } void range_add(int a, int b, long long x) { _add_val(x, a, b, 1, 0, length); } void range_update(int a, int b, long long x) { _update_val(x, a, b, 1, 0, length); } long long get_max(int a, int b) { return _query_max(a, b, 1, 0, length); } long long get_min(int a, int b) { return _query_min(a, b, 1, 0, length); } long long get_sum(int a, int b) { return _query_sum(a, b, 1, 0, length); } long long _query_sum(int a, int b, int k, int l, int r) { if(b <= l || r <= a) { return 0; } if(a <= l && r <= b) { return node_sum[k]; } propagate(k); long long lv = _query_sum(a, b, 2*k+0, l, (l+r)/2); long long rv = _query_sum(a, b, 2*k+1, (l+r)/2, r); return lv + rv; } }; int main() { int N,Q; cin >> N >> Q; vector<long long> A(N); SegmentTreeBeats seg(N); for(int i = 0; i < N; ++i) { cin >> A[i]; seg.range_add(i,i+1,A[i]); } while(Q--){ long long q,l,r,b; cin >> q >> l >> r; if(q==3){ cout << seg.get_sum(l,r) << endl; } else{ cin >> b; if(q==0) { seg.range_chmin(l,r,b); } if(q==1) { seg.range_chmax(l,r,b); } if(q==2) { seg.range_add(l,r,b); } } } return 0; }