Advertisement
peltorator

Difference Array: Structs

Mar 8th, 2021
2,009
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct SegmentAdder {
  6.     vector<int> diffArray;
  7.     int initArrayLen;
  8.  
  9.     vector<int> findDiffsArray(const vector<int>& arr) {
  10.         int n = arr.size();
  11.         vector<int> diffs(n - 1);
  12.         for (int i = 0; i < n - 1; i++) {
  13.             diffs[i] = arr[i + 1] - arr[i];
  14.         }
  15.         return diffs;
  16.     }
  17.  
  18.     SegmentAdder(vector<int> b) {
  19.         initArrayLen = b.size();
  20.         b.insert(b.begin(), 0); // add leading zero
  21.         diffArray = findDiffsArray(b);
  22.     }
  23.  
  24.  
  25.     vector<int> findPrefixSums(const vector<int>& a) {
  26.         int n = a.size();
  27.         vector<int> prefixSums(n + 1, 0);
  28.         for (int i = 0; i < n; i++) {
  29.             prefixSums[i + 1] = prefixSums[i] + a[i];
  30.         }
  31.         return prefixSums;
  32.     }
  33.  
  34.     void addOnSegment(int left, int right, int d) { // [left, right) += d
  35.         diffArray[left] += d;
  36.         if (right < initArrayLen) {
  37.             diffArray[right] -= d;
  38.         }
  39.     }
  40.  
  41.     vector<int> getArray() {
  42.         vector<int> finalB = findPrefixSums(diffArray);
  43.         finalB.erase(finalB.begin()); // delete leading zero
  44.         return finalB;
  45.     }
  46. };
  47.  
  48. int main() {
  49.     int n;
  50.     cin >> n;
  51.     vector<int> b(n);
  52.     for (int &val : b) {
  53.         cin >> val;
  54.     }
  55.     SegmentAdder myAdder(b);
  56.  
  57.     int queriesNumber;
  58.     cin >> queriesNumber;
  59.     for (int i = 0; i < queriesNumber; i++) {
  60.         int l, r;
  61.         int d;
  62.         cin >> l >> r >> d;
  63.         l--;
  64.         myAdder.addOnSegment(l, r, d);
  65.     }
  66.     vector<int> finalB = myAdder.getArray();
  67.     for (int val : finalB) {
  68.         cout << val << ' ';
  69.     }
  70.     cout << endl;
  71.     return 0;
  72. }
  73.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement