Language: C++

#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i32 = int32_t;
using i64 = int64_t;
constexpr char newl = '\n';

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
//#define F first
//#define S second
#define debug(x) cout << #x << ": " << x << '\n';
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1

template<class T>
class SegmentTree {
public:
  SegmentTree(int size) {
    int n = 1;
    while (n < size) n <<= 1;

    int segCount = n * 2 - 1;

    maxes = vector<T>(segCount, 0);
    sums = vector<T>(segCount, 0);

    lazyFlag = vector<bool>(segCount, false);

    lazyAdd = vector<T>(segCount, 0);

    lefts = vector<int>(segCount);
    rights = vector<int>(segCount);
    mp = vector<int>(segCount);
    parent = vector<int>(segCount);
    childs = vector<pair<int, int>>(segCount);

    for (int i = 0, l = 0, w = n; i < segCount; i++) {
      lefts[i] = l;
      rights[i] = lefts[i] + w;
      mp[i] = lefts[i] + (w >> 1);
      parent[i] = ((i + 1) >> 1) - 1;

      if (i > ((segCount + 1) >> 1) - 2)
        childs[i] = { -1,-1 };
      else
        childs[i] = { ((i + 1) << 1) - 1, ((i + 1) << 1) };

      if (rights[i] >= n) {
        w >>= 1; l = 0;
      }
      else {
        l += w;
      }
    }
  }

  void SetValue(T value, int index, int segIndex = 0) {

    resolve(segIndex);

    if (lefts[segIndex] == index && index + 1 == rights[segIndex]) {
      //cout << "max[" << segIndex << "] = " << value << newl;
      T dif = value - sums[segIndex];

      maxes[segIndex] = value;
      sums[segIndex] = value;
      while (segIndex) {
        segIndex = parent[segIndex]; // parent

        sums[segIndex] += dif;
        if (maxes[segIndex] >= value) break;
        maxes[segIndex] = value;
        //cout << "max[" << segIndex << "] = " << value << newl;
      }
    }
    else {
      if (index < mp[segIndex]) {
        SetValue(value, index, childs[segIndex].first);
      }
      else {
        SetValue(value, index, childs[segIndex].second);
      }
    }
  }

  void Add(T value, int left, int right = left + 1, int segIndex = 0) {

    //cout << "Add [" << left << ", " << right << ") -> +" << value << " (si:" << segIndex << ")" << newl;

    if (left <= lefts[segIndex] && rights[segIndex] <= right) {
      // 既に遅延データがあるなら、合算する
      // - 現在は必要ないが、いずれ抽象化するときに備えてこのように分岐しておく
      if (lazyFlag[segIndex]) {
        lazyAdd[segIndex] += value;
      }
      else {
        lazyAdd[segIndex] = value;
        lazyFlag[segIndex]  = true;
      }
      resolve(segIndex);
    }
    else {
      resolve(segIndex);

      sums[segIndex] += value * (right - left);

      if (left < mp[segIndex]) {
        Add(value, left, right, childs[segIndex].first);
      }
      if (mp[segIndex] < right) {
        Add(value, left, right, childs[segIndex].second);
      }

      maxes[segIndex] = max(maxes[childs[segIndex].first], maxes[childs[segIndex].second]);
    }
  }

  // [L, R)
  T GetMax(int pLeft, int pRight = pLeft + 1, int segIndex = 0) {

    //cout << "GetMax(" << pLeft << ", " << pRight << ", " << segIndex << ")" << newl;

    if (pRight <= pLeft) return 0;

    resolve(segIndex);
    if (pLeft <= lefts[segIndex] &&  rights[segIndex] <= pRight) {
      //cout << "return max[" << segIndex << "] = " << maxes[segIndex] << newl;
      return maxes[segIndex];
    }
    else {
      if (pLeft < mp[segIndex]) {
        if (mp[segIndex] < pRight) {
          return max(GetMax(pLeft, pRight, childs[segIndex].first),
            GetMax(pLeft, pRight, childs[segIndex].second));
        }
        return GetMax(pLeft, pRight, childs[segIndex].first);
      }
      else if (mp[segIndex] < pRight) {
        return GetMax(pLeft, pRight, childs[segIndex].second);
      }
    }
  }

  // [L, R)
  T GetSum(int pLeft, int pRight = pLeft + 1, int segIndex = 0) {

    resolve(segIndex);
    if (pLeft <= lefts[segIndex] && rights[segIndex] <= pRight) {
      return sums[segIndex];
    }
    else {
      if (pLeft < mp[segIndex]) {
        if (mp[segIndex] < pRight) {
          return GetSum(pLeft, pRight, childs[segIndex].first) +
            GetSum(pLeft, pRight, childs[segIndex].second);
        }
        return GetSum(pLeft, pRight, childs[segIndex].first);
      }
      else if (mp[segIndex] < pRight) {
        return GetSum(pLeft, pRight, childs[segIndex].second);
      }
    }
  }

  // debug
  void Print() {
    F0R(i, maxes.size()) {
      cout << i << ':' << "max=" << maxes[i] << " sum=" << sums[i];
      cout << " ladd=" << lazyAdd[i];
      cout << newl;
    }
  }

protected:

  // 遅延伝播分の解決
  void resolve(int segIndex) {
    if (!lazyFlag[segIndex]) return;

    if (lazyAdd[segIndex] != 0) {
      maxes[segIndex] += lazyAdd[segIndex];
      sums[segIndex] += lazyAdd[segIndex] * (rights[segIndex] - lefts[segIndex]);

      if (childs[segIndex].first >= 0) {
        Add(lazyAdd[segIndex], lefts[segIndex], mp[segIndex], childs[segIndex].first);
        Add(lazyAdd[segIndex], mp[segIndex], rights[segIndex], childs[segIndex].second);
      }

      lazyAdd[segIndex] = 0;
    }
    lazyFlag[segIndex] = false;
  }

  // 要素ごとのデータ
  vector<T> maxes, sums;

  // 遅延データがあるか
  vector<bool> lazyFlag;

  // 要素ごとの遅延データ
  vector<T> lazyAdd;

  // 区間 [l, r) とその中間
  vector<int> lefts, rights, mp, parent;
  vector<pair<int, int>> childs;
  int power;
};

// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

#if 0
  SegmentTree<i64> st(10);
  F0R(i, 10) {
    st.SetValue(i + 1, i);
  }
  cout << st.GetMax(0, 5) << newl;
  cout << st.GetMax(5, 10) << newl;
  cout << st.GetSum(0, 5) << newl;
  cout << st.GetSum(5, 10) << newl;
  return 0;
#endif

  int N, M;
  cin >> N >> M;

  // sums[i][j] := j で始まり i で終わる区間のスコアの和
  //unordered_map<int, unordered_map<int, i64>> sums;

  // as[i] := i で終わる区間の l とスコア
  vector<vector<pair<int, int>>> as(N + 1);

  F0R(i, M) {
    int l, r, a;
    cin >> l >> r >> a;
    //l--; r--;

    //sums[r][l] += a;
    as[r].emplace_back(l, a);
  }

  // n 文字目まで処理するとき、スコアはn文字までに終わる区間のもののみ考える
  // dp[i][j] = i文字目まで決めたとき、最後の1がj文字目のときの最大スコア
  // dp[i-1][j] + j を含み i で終わる区間のスコアの和 (j < i)
  // max(dp[i-1][0] ~ dp[i-1][j]) + i で終わる区間のスコアの和 (j == i)

  // dp[i]だけ持てばいい。
  // j を含み i で終わる区間のスコアの和 = [j ~ i, i] のスコアの和
  // つまり毎回[0,i]から[i,i]まで順に計算するなら、和をとっていけばいいだけなんだけど
  // それだとO(N^2)

  // なので Segment Tree を使って条件(M個)ごとに区間add(O(logN))していく

  //vector<i64> dp(N + 1);
  SegmentTree<i64> dp(N + 1);
  
  FOR(i, 1, N + 1) {

    //debug(i);

    dp.SetValue(dp.GetMax(0, i-1), i);

    for (auto p : as[i]) {
      dp.Add(p.second, p.first, i + 1); // [L, R) なので i+1
    }
    
    /*
    i64 max = 0, sum = 0;
    FOR(j, 1, i) {
      //debug(sums[i][j]);

      if (sums.find(i) != sums.end() && sums[i].find(j) != sums[i].end())
        sum += sums[i][j];
      chmax(max, dp[j]);
      dp[j] += sum;
    }
    //debug(sums[i][i]);
    dp[i] = max + sum;

    if (sums.find(i) != sums.end() && sums[i].find(i) != sums[i].end())
      dp[i] += sums[i][i];

    //Print(dp);
    */

    //dp.Print();
  }
  i64 result = 0;
  /*
  F0R(i, N + 1) {
    chmax(result, dp[i]);
  }
  */
  result = dp.GetMax(0, N + 1);
  cout << result;
}
#endif


Compiler output:
a.cc:105:43: error: parameter 'left' may not appear in this context
  105 |   void Add(T value, int left, int right = left + 1, int segIndex = 0) {
      |                                           ^~~~
a.cc:138:36: error: parameter 'pLeft' may not appear in this context
  138 |   T GetMax(int pLeft, int pRight = pLeft + 1, int segIndex = 0) {
      |                                    ^~~~~
a.cc:164:36: error: parameter 'pLeft' may not appear in this context
  164 |   T GetSum(int pLeft, int pRight = pLeft + 1, int segIndex = 0) {
      |                                    ^~~~~
a.cc: In member function 'T SegmentTree<T>::GetMax(int, int, int) [with T = long int]':
a.cc:161:3: warning: control reaches end of non-void function [-Wreturn-type]
  161 |   }
      |   ^