fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. typedef long long ll;
  5.  
  6. class SegmentTree {
  7.     vector<ll> tree, lazy;
  8.     int n;
  9.  
  10.     void push(int node, int start, int end) {
  11.         if (lazy[node] != 0) {
  12.             tree[node] += (end - start + 1) * lazy[node]; // Apply lazy value to the current segment
  13.             if (start != end) {
  14.                 lazy[node * 2 + 1] += lazy[node]; // Propagate to left child
  15.                 lazy[node * 2 + 2] += lazy[node]; // Propagate to right child
  16.             }
  17.             lazy[node] = 0; // Clear the lazy value
  18.         }
  19.     }
  20.  
  21.     void updateRange(int node, int start, int end, int l, int r, ll val) {
  22.         push(node, start, end); // Apply pending updates
  23.         if (start > r || end < l) return; // Out of range
  24.  
  25.         if (start >= l && end <= r) { // Completely within range
  26.             lazy[node] += val; // Mark for lazy propagation
  27.             push(node, start, end); // Apply the update now
  28.             return;
  29.         }
  30.  
  31.         int mid = (start + end) / 2;
  32.         updateRange(node * 2 + 1, start, mid, l, r, val);    // Update left child
  33.         updateRange(node * 2 + 2, mid + 1, end, l, r, val);  // Update right child
  34.         tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2]; // Update current node
  35.     }
  36.  
  37.     ll queryRange(int node, int start, int end, int l, int r) {
  38.         push(node, start, end); // Apply pending updates
  39.         if (start > r || end < l) return 0; // Out of range
  40.  
  41.         if (start >= l && end <= r) return tree[node]; // Completely within range
  42.  
  43.         int mid = (start + end) / 2;
  44.         ll leftSum = queryRange(node * 2 + 1, start, mid, l, r);
  45.         ll rightSum = queryRange(node * 2 + 2, mid + 1, end, l, r);
  46.         return leftSum + rightSum; // Combine results
  47.     }
  48.  
  49. public:
  50.     SegmentTree(int size) {
  51.         n = size;
  52.         tree.assign(4 * n, 0);
  53.         lazy.assign(4 * n, 0);
  54.     }
  55.  
  56.     void updateRange(int l, int r, ll val) {
  57.         updateRange(0, 0, n - 1, l, r, val);
  58.     }
  59.  
  60.     ll queryRange(int l, int r) {
  61.         return queryRange(0, 0, n - 1, l, r);
  62.     }
  63. };
  64.  
  65. void solve() {
  66.     int n, c;
  67.     cin >> n >> c;
  68.     SegmentTree segTree(n);
  69.  
  70.     while (c--) {
  71.         int type;
  72.         cin >> type;
  73.  
  74.         if (type == 0) { // Range update
  75.             int p, q;
  76.             ll v;
  77.             cin >> p >> q >> v;
  78.             segTree.updateRange(p - 1, q - 1, v);
  79.         } else if (type == 1) { // Range sum query
  80.             int p, q;
  81.             cin >> p >> q;
  82.             cout << segTree.queryRange(p - 1, q - 1) << '\n';
  83.         }
  84.     }
  85. }
  86.  
  87. signed main() {
  88.     ios::sync_with_stdio(false);
  89.     cin.tie(nullptr);
  90.  
  91.     int t;
  92.     cin >> t;
  93.     while (t--) {
  94.         solve();
  95.     }
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout 0s 5276KB
comments (?)
stdin
copy 
1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8 
0 5 7 14
1 4 8
stdout
copy 
80
508
https://ideone.com/YaZl1S
problem HORRIBLE, based on SPOJ submission 33979301 (CPP), 2024-12-17 20:10:24
language:
C++ (gcc 8.3)
created:
4 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!