description: There are n cities in a row numbered from 1 to n.
  
  The cities will be building broadcasting stations. The station in the i-th city has height h_i and range w_i. It can broadcast information to city j if the following constraints are met: 
  
    * i ≤ j ≤ w_i, and 
    * for each k such that i < k ≤ j, the following condition holds: h_k < h_i. 
  
  In other words, the station in city i can broadcast information to city j if j ≥ i, j is in the range of i-th station, and i is strictly highest on the range from i to j (including city j).
  
  At the beginning, for every city i, h_i = 0 and w_i = i.
  
  Then q events will take place. During i-th event one of the following will happen: 
  
    * City c_i will rebuild its station so that its height will be strictly highest among all stations and w_{c_i} will be set to g_i. 
    * Let b_j be the number of stations that can broadcast information to city j. Print the sum of b_j over all j satisfying l_i ≤ j ≤ r_i. 
  
  
  
  Your task is to react to all events and print answers to all queries.
  
  Input
  
  The first line contains two integers n and q (1 ≤ n, q ≤ 2⋅10^5) — number of cities and number of events.
  
  Then q lines follow. The i-th line begins with an integer p_i (p_i = 1 or p_i = 2).
  
  If p_i = 1 a station will be rebuilt. Then two integers c_i and g_i (1 ≤ c_i ≤ g_i ≤ n) follow — the city in which the station is rebuilt and its new broadcasting range.
  
  If p_i = 2 you are given a query. Then two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n) follow — the range of cities in the query.
  
  Output
  
  For each query, print in a single line the sum of b_j over the given interval.
  
  Examples
  
  Input
  
  
  1 3
  2 1 1
  1 1 1
  2 1 1
  
  
  Output
  
  
  1
  1
  
  
  Input
  
  
  5 10
  1 3 4
  2 3 5
  1 1 5
  2 1 5
  1 4 5
  2 2 4
  1 2 3
  2 1 3
  1 5 5
  2 2 5
  
  
  Output
  
  
  4
  10
  5
  4
  5
  
  Note
  
  In the first test case, only station 1 reaches city 1 before and after it is rebuilt.
  
  In the second test case, after each rebuild, the array b looks as follows: 
  
    1. [1, 1, 1, 2, 1]; 
    2. [1, 2, 2, 3, 2]; 
    3. [1, 2, 2, 1, 2]; 
    4. [1, 1, 2, 1, 2]; 
    5. [1, 1, 2, 1, 1]. 
solution: #include <bits/stdc++.h>
  using namespace std;
  using LL = long long;
  const int MAXN = 200010;
  const int INF = 0x7fffffff;
  class SegTree {
   public:
    SegTree() {}
    void Build(int t, int l, int r) {
      if (l == r) {
        x[t] = sum[t] = ox[l];
        return;
      }
      int mid = (l + r) >> 1;
      Build(t + t, l, mid);
      Build(t + t + 1, mid + 1, r);
      sum[t] = sum[t + t] + sum[t + t + 1];
    }
    void PushDown(int t, int l, int r) {
      if (l == r) return;
      if (x[t] == 0) return;
      x[t + t] += x[t];
      x[t + t + 1] += x[t];
      LL mid = (l + r) >> 1;
      sum[t + t] += (mid - l + 1) * x[t];
      sum[t + t + 1] += (r - mid) * x[t];
      x[t] = 0;
    }
    void Insert(int t, int a, int l, int r, int p, int q) {
      PushDown(t, l, r);
      if (p <= l && r <= q) {
        x[t] += a;
        sum[t] += (r - l + 1LL) * a;
        return;
      }
      int mid = (l + r) >> 1;
      if (p <= mid) Insert(t + t, a, l, mid, p, q);
      if (mid + 1 <= q) Insert(t + t + 1, a, mid + 1, r, p, q);
      sum[t] = sum[t + t] + sum[t + t + 1];
    }
    LL Query(int t, int l, int r, int p, int q) {
      PushDown(t, l, r);
      if (p <= l && r <= q) return sum[t];
      int mid = (l + r) >> 1;
      LL ans = 0;
      if (p <= mid) ans += Query(t + t, l, mid, p, q);
      if (mid + 1 <= q) ans += Query(t + t + 1, mid + 1, r, p, q);
      return ans;
    }
    int ox[MAXN];
    LL x[MAXN * 4], sum[MAXN * 4];
  } tree;
  struct Node {
    int mx, mx2, mn, mn2, cmx, cmn, tmx, tmn, tad;
    LL sum;
  };
  class SegmentTreeBeats {
   public:
    void Merge(int t) {
      const int lt = t << 1, rt = t << 1 | 1;
      x[t].sum = x[lt].sum + x[rt].sum;
      if (x[lt].mx == x[rt].mx) {
        x[t].mx = x[lt].mx;
        x[t].cmx = x[lt].cmx + x[rt].cmx;
        x[t].mx2 = max(x[lt].mx2, x[rt].mx2);
      } else if (x[lt].mx > x[rt].mx) {
        x[t].mx = x[lt].mx;
        x[t].cmx = x[lt].cmx;
        x[t].mx2 = max(x[lt].mx2, x[rt].mx);
      } else {
        x[t].mx = x[rt].mx;
        x[t].cmx = x[rt].cmx;
        x[t].mx2 = max(x[lt].mx, x[rt].mx2);
      }
      if (x[lt].mn == x[rt].mn) {
        x[t].mn = x[lt].mn;
        x[t].cmn = x[lt].cmn + x[rt].cmn;
        x[t].mn2 = min(x[lt].mn2, x[rt].mn2);
      } else if (x[lt].mn < x[rt].mn) {
        x[t].mn = x[lt].mn;
        x[t].cmn = x[lt].cmn;
        x[t].mn2 = min(x[lt].mn2, x[rt].mn);
      } else {
        x[t].mn = x[rt].mn;
        x[t].cmn = x[rt].cmn;
        x[t].mn2 = min(x[lt].mn, x[rt].mn2);
      }
    }
    void PushAdd(int t, int l, int r, int v) {
      x[t].sum += (r - l + 1LL) * v;
      x[t].mx += v;
      x[t].mn += v;
      if (x[t].mx2 != -INF) x[t].mx2 += v;
      if (x[t].mn2 != INF) x[t].mn2 += v;
      if (x[t].tmx != -INF) x[t].tmx += v;
      if (x[t].tmn != INF) x[t].tmn += v;
      x[t].tad += v;
    }
    void PushMin(int t, int tg) {
      if (x[t].mx <= tg) return;
      x[t].sum += (tg * 1LL - x[t].mx) * x[t].cmx;
      if (x[t].mn2 == x[t].mx) x[t].mn2 = tg;
      if (x[t].mn == x[t].mx) x[t].mn = tg;
      if (x[t].tmx > tg) x[t].tmx = tg;
      x[t].mx = tg;
      x[t].tmn = tg;
    }
    void PushMax(int t, int tg) {
      if (x[t].mn > tg) return;
      x[t].sum += (tg * 1LL - x[t].mn) * x[t].cmn;
      if (x[t].mx2 == x[t].mn) x[t].mx2 = tg;
      if (x[t].mx == x[t].mn) x[t].mx = tg;
      if (x[t].tmn < tg) x[t].tmn = tg;
      x[t].mn = tg;
      x[t].tmx = tg;
    }
    void PushDown(int t, int l, int r) {
      const int lt = t << 1, rt = t << 1 | 1;
      const int mid = (l + r) >> 1;
      if (x[t].tad) {
        PushAdd(lt, l, mid, x[t].tad);
        PushAdd(rt, mid + 1, r, x[t].tad);
      }
      if (x[t].tmx != -INF) {
        PushMax(lt, x[t].tmx);
        PushMax(rt, x[t].tmx);
      }
      if (x[t].tmn != INF) {
        PushMin(lt, x[t].tmn);
        PushMin(rt, x[t].tmn);
      }
      x[t].tad = 0;
      x[t].tmx = -INF;
      x[t].tmn = INF;
    }
    void Build(int t, int l, int r) {
      x[t].tmn = INF;
      x[t].tmx = -INF;
      if (l == r) {
        x[t].sum = x[t].mx = x[t].mn = ox[l];
        x[t].mx2 = -INF;
        x[t].mn2 = INF;
        x[t].cmx = x[t].cmn = 1;
        return;
      }
      int mid = (l + r) >> 1;
      Build(t << 1, l, mid);
      Build(t << 1 | 1, mid + 1, r);
      Merge(t);
    }
    void Add(int t, int l, int r, int L, int R, int v) {
      if (R < l || r < L) return;
      if (L <= l && r <= R) return PushAdd(t, l, r, v);
      int mid = (l + r) >> 1;
      PushDown(t, l, r);
      Add(t << 1, l, mid, L, R, v);
      Add(t << 1 | 1, mid + 1, r, L, R, v);
      Merge(t);
    }
    void SetMin(int t, int l, int r, int L, int R, int v) {
      if (R < l || r < L || x[t].mx <= v) return;
      if (L <= l && r <= R && x[t].mx2 < v) {
        tree.Insert(1, -x[t].cmx, 1, n, v + 1, x[t].mx);
        return PushMin(t, v);
      }
      int mid = (l + r) >> 1;
      PushDown(t, l, r);
      SetMin(t << 1, l, mid, L, R, v);
      SetMin(t << 1 | 1, mid + 1, r, L, R, v);
      Merge(t);
    }
    void SetMax(int t, int l, int r, int L, int R, int v) {
      if (R < l || r < L || x[t].mn >= v) return;
      if (L <= l && r <= R && x[t].mn2 > v) return PushMax(t, v);
      int mid = (l + r) >> 1;
      PushDown(t, l, r);
      SetMax(t << 1, l, mid, L, R, v);
      SetMax(t << 1 | 1, mid + 1, r, L, R, v);
      Merge(t);
    }
    LL QuerySum(int t, int l, int r, int L, int R) {
      if (R < l || r < L) return 0;
      if (L <= l && r <= R) return x[t].sum;
      int mid = (l + r) >> 1;
      PushDown(t, l, r);
      return QuerySum(t << 1, l, mid, L, R) +
             QuerySum(t << 1 | 1, mid + 1, r, L, R);
    }
    LL QueryMax(int t, int l, int r, int L, int R) {
      if (R < l || r < L) return -INF;
      if (L <= l && r <= R) return x[t].mx;
      int mid = (l + r) >> 1;
      PushDown(t, l, r);
      return max(QueryMax(t << 1, l, mid, L, R),
                 QueryMax(t << 1 | 1, mid + 1, r, L, R));
    }
    LL QueryMin(int t, int l, int r, int L, int R) {
      if (R < l || r < L) return INF;
      if (L <= l && r <= R) return x[t].mn;
      int mid = (l + r) >> 1;
      PushDown(t, l, r);
      return min(QueryMin(t << 1, l, mid, L, R),
                 QueryMin(t << 1 | 1, mid + 1, r, L, R));
    }
    int n;
    int ox[MAXN];
    Node x[MAXN * 4];
  } treeb;
  int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    treeb.n = n;
    for (int i = 1; i <= n; ++i) {
      tree.ox[i] = 1;
      treeb.ox[i] = i;
    }
    tree.Build(1, 1, n);
    treeb.Build(1, 1, n);
    while (q--) {
      int t, a, b;
      cin >> t >> a >> b;
      if (t == 1) {
        int r = treeb.QueryMax(1, 1, n, a, a);
        if (r > b) {
          tree.Insert(1, -1, 1, n, b + 1, r);
        } else if (r < b) {
          tree.Insert(1, 1, 1, n, r + 1, b);
        }
        if (r != b) {
          treeb.Add(1, 1, n, a, a, b - r);
        }
        if (a == 1) continue;
        treeb.SetMin(1, 1, n, 1, a - 1, a - 1);
      } else {
        cout << tree.Query(1, 1, n, a, b) << "\n";
      }
    }
    return 0;
  }
  