Увећавање сегмената - Решење

Директно решење

Директан начин је да се одржава низ \(M\) у којем се памти маса на камиону током сваког километра пута. Након учитавања сваког податка о предмету (почетног километра \(a\), завршног километра \(b\) и масе \(m\)), све вредности у низу \(M\) на позицијама од \(a\) до \(b\) (укључујући и њих) се увећавају за \(m\).

#include <iostream>
#include <vector>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> mase(n, 0);
  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
    int km_od, km_do, masa;
    cin >> km_od >> km_do >> masa;
    for (int km = km_od; km <= km_do; km++)
      mase[km] += masa;
  }

  for (int masa : mase)
    cout << masa << " ";
    
  return 0;
}

Разлике суседних елемената низа

Задатак можемо решити ефикасније ако уместо да у низу \(M\) одржавамо масу у камиону у километру \(i\), одржавамо разлику између масе у километру \(i\) и \(i-1\) (на позицији \(0\) се чува маса у камиону у нултом километру). Дакле, уводимо низ \(R_i\) такав да је \(R_0 = M_0\), а \(R_i = M_i - M_{i-1}\), за \(1 \leq i < n\). Посматрајмо шта се дешава са низом \(R\) када се у низу \(M\) сви елементи на позицијама \(a\) до \(b\) увећају за \(m\).

• Вредност \(R_a\) једнака је разлици \(M_a - M_{a-1}\) (или евентуално \(M_0\) ако је \(a = 0\)) и она се увећава за \(m\), јер је \(M_a\) увећан за \(m\), док се \(M_{a-1}\) не мења.
• Све вредности од \(R_{a+1}\) до \(R_b\) остају не промењене. Наиме, за све њих важи да је \(R_i = M_{i} - M_{i-1}\), а да су и \(M_i\) и \(M_{i-1}\) увећани за \(m\).
• На крају, вредност \(R_{b+1}\) се умањује за \(m\). Наиме важи да је \(R_{b+1} = M_{b+1} - M_b\), да се \(M_b\) увећава за \(m\), док се \(M_{b+1}\) не мења.

Рецимо да ако је \(b = n-1\), тада не морамо разматрати вредност \(R_{b+1} = R_n\) (мада, униформности ради, можемо, што захтева да низ \(R\) садржи \(n+1\) елемент). Дакле, приликом сваког учитавања бројева \(a\), \(b\) и \(m\) потребно је само да увећавамо елемент \(R_a\) за \(m\), а да елемент \(R_{b+1}\) умањимо за \(m\).

Када знамо елементе низа \(R\) елементе низа \(M\) можемо једноставно реконструисати сабирањем елемената низа \(R\). Наиме, важи да је \(M_0 = R_0\), док је \(M_i = M_{i-1} + R_i\), тако да сваки наредни елемент низа \(M\) можемо израчунати као збир претходног елемента низа \(M\) и њему одговарајућег елемента низа \(R\). Приметимо да је заправо елемент \(M_i\) једнак збиру свих елемената од \(R_0\) до \(R_i\), јер је \(R_0 + R_1 + \ldots + R_i = M_0 + (M_1 - M_0) + \ldots + (M_i - M_{i-1}) = M_i\).

#include <iostream>
#include <vector>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> razlika(n+1, 0);
  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
    int km_od, km_do, masa;
    cin >> km_od >> km_do >> masa;
    razlika[km_od] += masa;
    razlika[km_do+1] -= masa;
  }

  int masa_km = 0;
  for (int km = 0; km < n; km++) {
    masa_km += razlika[km];
    cout << masa_km << " ";
  }

  return 0;
}