fork download 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <string>
  5. #include <vector>
  6. #include <queue>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #include <iomanip>
  11. #include <numeric>
  12. #include <unordered_map>
  13. #include <unordered_set>
  14. #include <climits>
  15.  
  16. #define fora(e,v) for(auto &e: v)
  17. #define srt(v) sort(v.begin(), v.end())
  18. #define srtR(v) sort(v.begin(), v.end(), greater<int>())
  19. #define fill(arr,value) memset(arr, value, sizeof(arr))
  20. #define ll long long
  21. #define all(v) v.begin(), v.end()
  22. #define sz(v) ((int)v.size())
  23.  
  24. using namespace std;
  25.  
  26. const int MAX = 2 * 1e5 + 5;
  27. const int OO = INT_MAX;
  28. const int MOD = 1e9 + 7;
  29.  
  30. vector<int> fact(MAX);
  31.  
  32. ll gcd(ll a, ll b) {
  33.     if (!b) {
  34.         return a;
  35.     }
  36.     return gcd(b, a % b);
  37. }
  38.  
  39. ll lcm(ll a, ll b) {
  40.     return a / gcd(a, b) * b;
  41. }
  42.  
  43. ll power(ll base, ll pow) {
  44.     if (pow == 0) {
  45.         return 1;
  46.     }
  47.  
  48.     ll half = power(base, pow / 2);
  49.     half = (half * half) % MOD;
  50.  
  51.     if (pow % 2 == 1) {
  52.         half = (half * base) % MOD;
  53.     }
  54.  
  55.     return half;
  56. }
  57.  
  58. ll add(ll a, ll b) {
  59.     return ((a % MOD) + (b % MOD)) % MOD;
  60. }
  61.  
  62. ll sub(ll a, ll b) {
  63.     return (((a % MOD) - (b % MOD)) % MOD + MOD) % MOD;
  64. }
  65.  
  66. ll mul(ll a, ll b) {
  67.     return ((a % MOD) * (b % MOD)) % MOD;
  68. }
  69.  
  70. ll inv(ll base) {
  71.     return power(base, MOD - 2);
  72. }
  73.  
  74. ll divide(ll a, ll b) {
  75.     return mul(a, inv(b));
  76. }
  77.  
  78. ll nCr(ll n, ll r) {
  79.     if (r > n) return 0;
  80.     return mul(fact[n], inv(mul(fact[r], fact[n - r])));
  81. }
  82.  
  83. ll nPr(int n, int r) {
  84.     return divide(fact[n], fact[n - r]);
  85. }
  86.  
  87. void doFact() {
  88.     fact[0] = 1;
  89.     for (int i = 1; i < MAX; i++) {
  90.         fact[i] = mul(i, fact[i - 1]);
  91.     }
  92. }
  93.  
  94. bool isPrime(ll n) {
  95.     if (n == 1) return false;
  96.     if (n % 2 == 0) return n == 2;
  97.     for (int i = 3; i * i <= n; i += 2) {
  98.         if (n % i == 0) return false;
  99.     }
  100.     return true;
  101. }
  102.  
  103. int n, q;
  104.  
  105. struct sgTree {
  106.     int size;
  107.     vector<ll> values;
  108.     vector<ll> mins;
  109.  
  110.     ll noOperation = LLONG_MAX;
  111.  
  112.     void init(int n) {
  113.         size = 1;
  114.         while (size < n) size *= 2;
  115.         values.resize(2 * size,0);
  116.         mins.resize(2 * size,0);
  117.     }
  118.  
  119.     void set(int idx, ll val, int root, int lx, int rx) {
  120.         if (rx - lx == 1) {
  121.             values[root] = val;
  122.             return;
  123.         }
  124.         int mid = lx + (rx - lx) / 2;
  125.         if (idx < mid) {
  126.             set(idx, val, 2 * root + 1, lx, mid);
  127.         } else {
  128.             set(idx, val, 2 * root + 2, mid, rx);
  129.         }
  130.         values[root] = values[2 * root + 1] + values[2 * root + 2];
  131.     }
  132.  
  133.     void set(int idx, ll val) {
  134.         set(idx, val, 0, 0, size);
  135.     }
  136.  
  137.     void modify(ll l, ll r, ll val,int root, int lx, int rx) {
  138.         if (lx >= r || rx <= l) return;
  139.         if (lx >= l && rx <= r) {
  140.             values[root] += val;
  141.             mins[root] += val;
  142.             return;
  143.         }
  144.         int mid = lx + (rx - lx) / 2;
  145.         modify(l, r,val, 2 * root + 1, lx, mid);
  146.         modify(l, r,val, 2 * root + 2, mid, rx);
  147.         mins[root] = min(mins[2 * root + 1],mins[2 * root + 2]) + values[root];
  148.     }
  149.  
  150.     void modify(ll l, ll r, ll val) {
  151.         modify(l,r,val,0,0,size);
  152.     }
  153.  
  154.     ll getMin(int l, int r, int root, int lx, int rx) {
  155.         if (lx >= r || rx <= l) return LLONG_MAX;
  156.         if (lx >= l && rx <= r) return mins[root];
  157.         int mid = lx + (rx - lx) / 2;
  158.         ll mn1 = getMin(l, r, 2 * root + 1, lx, mid);
  159.         ll mn2 = getMin(l, r, 2 * root + 2, mid, rx);
  160.         return min(mn1,mn2) + values[root];
  161.     }
  162.  
  163.     ll getMin(int l,int r) {
  164.         return getMin(l, r, 0, 0, size);
  165.     }
  166.  
  167.     ll calc(int l, int r, int root, int lx, int rx) {
  168.         if (lx >= r || rx <= l) return 0;
  169.         if (lx >= l && rx <= r) return values[root];
  170.         int mid = lx + (rx - lx) / 2;
  171.         ll sum1 = calc(l, r, 2 * root + 1, lx, mid);
  172.         ll sum2 = calc(l, r, 2 * root + 2, mid, rx);
  173.         return sum1 + sum2;
  174.     }
  175.  
  176.     ll calc(int l,int r) {
  177.         return calc(l, r, 0, 0, size);
  178.     }
  179.  
  180. };
  181.  
  182. void solve() {
  183.  
  184.     cin >> n >> q;
  185.  
  186.     sgTree seg;
  187.     seg.init(n);
  188.  
  189.     while(q--) {
  190.  
  191.         int op;cin>>op;
  192.  
  193.         if(op == 1) {
  194.  
  195.             ll l,r,val;cin>>l>>r>>val;
  196.             seg.modify(l,r,val);
  197.  
  198.         }
  199.         else {
  200.             ll l,r;cin >> l>> r;
  201.             cout<<seg.getMin(l,r)<<"\n";
  202.         }
  203.  
  204.     }
  205.  
  206. }
  207.  
  208. int main() {
  209.     ll t = 1;
  210.     //cin >> t;
  211.     while (t--) {
  212.         solve();
  213.     }
  214.     return 0;
  215. }
  216.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/FihT9C
language:
C++14 (gcc 8.3)
created:
280 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!