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 = 200200;
  struct seg_tree {
    ll sum[maxn * 4], lazy[maxn * 4];
    void build(int l, int r, int rt) {
      sum[rt] = r - l + 1;
      if (l == r) return;
      int mid = (l + r) / 2;
      build(l, mid, rt << 1);
      build(mid + 1, r, rt << 1 | 1);
    }
    void push_down(int l, int r, int rt) {
      if (lazy[rt]) {
        int mid = (l + r) / 2;
        sum[rt << 1] += (mid - l + 1) * lazy[rt];
        sum[rt << 1 | 1] += (r - mid) * lazy[rt];
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        lazy[rt] = 0;
      }
    }
    void add(int L, int R, int v, int l, int r, int rt) {
      if (L <= l && r <= R) {
        sum[rt] += v * (ll)(r - l + 1);
        lazy[rt] += v;
        return;
      }
      push_down(l, r, rt);
      int mid = (l + r) / 2;
      if (L <= mid) add(L, R, v, l, mid, rt << 1);
      if (mid < R) add(L, R, v, mid + 1, r, rt << 1 | 1);
      sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    }
    ll ask(int L, int R, int l, int r, int rt) {
      if (L <= l && r <= R) return sum[rt];
      push_down(l, r, rt);
      int mid = (l + r) / 2;
      ll ans = 0;
      if (L <= mid) ans += ask(L, R, l, mid, rt << 1);
      if (mid < R) ans += ask(L, R, mid + 1, r, rt << 1 | 1);
      return ans;
    }
  } S;
  struct seg_tree2 {
    int n;
    struct node {
      int mx, mx2, num_mx, tag;
    } tr[maxn * 4];
    void build(int l, int r, int rt) {
      if (l == r) {
        tr[rt].mx = l;
        tr[rt].mx2 = 0;
        tr[rt].num_mx = 1;
        return;
      }
      int mid = (l + r) / 2;
      build(l, mid, rt << 1);
      build(mid + 1, r, rt << 1 | 1);
      tr[rt].mx = r;
      tr[rt].mx2 = r - 1;
      tr[rt].num_mx = 1;
    }
    void push_up(int rt) {
      if (tr[rt << 1].mx > tr[rt << 1 | 1].mx) {
        tr[rt].mx = tr[rt << 1].mx;
        tr[rt].mx2 = max(tr[rt << 1].mx2, tr[rt << 1 | 1].mx);
        tr[rt].num_mx = tr[rt << 1].num_mx;
      } else if (tr[rt << 1].mx < tr[rt << 1 | 1].mx) {
        tr[rt].mx = tr[rt << 1 | 1].mx;
        tr[rt].mx2 = max(tr[rt << 1].mx, tr[rt << 1 | 1].mx2);
        tr[rt].num_mx = tr[rt << 1 | 1].num_mx;
      } else {
        tr[rt].mx = tr[rt << 1].mx;
        tr[rt].mx2 = max(tr[rt << 1].mx2, tr[rt << 1 | 1].mx2);
        tr[rt].num_mx = tr[rt << 1].num_mx + tr[rt << 1 | 1].num_mx;
      }
    }
    void push_down(int rt) {
      if (tr[rt].tag) {
        if (tr[rt << 1].mx > tr[rt].tag) {
          tr[rt << 1].mx = tr[rt].tag;
          tr[rt << 1].tag = tr[rt].tag;
        }
        if (tr[rt << 1 | 1].mx > tr[rt].tag) {
          tr[rt << 1 | 1].mx = tr[rt].tag;
          tr[rt << 1 | 1].tag = tr[rt].tag;
        }
        tr[rt].tag = 0;
      }
    }
    void upd_min(int L, int R, int v, int l, int r, int rt) {
      if (l > R || r < L || tr[rt].mx <= v) return;
      if (L <= l && r <= R && tr[rt].mx2 < v) {
        S.add(v + 1, tr[rt].mx, -tr[rt].num_mx, 1, n, 1);
        tr[rt].mx = v;
        tr[rt].tag = v;
        return;
      }
      push_down(rt);
      int mid = (l + r) / 2;
      upd_min(L, R, v, l, mid, rt << 1);
      upd_min(L, R, v, mid + 1, r, rt << 1 | 1);
      push_up(rt);
    }
    void upd(int p, int v, int l, int r, int rt) {
      if (l == r) {
        if (tr[rt].mx > v) {
          S.add(v + 1, tr[rt].mx, -1, 1, n, 1);
        } else if (tr[rt].mx < v) {
          S.add(tr[rt].mx + 1, v, 1, 1, n, 1);
        }
        tr[rt].mx = v;
        return;
      }
      push_down(rt);
      int mid = (l + r) / 2;
      if (p <= mid)
        upd(p, v, l, mid, rt << 1);
      else
        upd(p, v, mid + 1, r, rt << 1 | 1);
      push_up(rt);
    }
  } T;
  int main(void) {
    int n, q;
    scanf("%d%d", &n, &q);
    S.build(1, n, 1);
    T.n = n;
    T.build(1, n, 1);
    for (int i = 0; i < q; i++) {
      int op, x, y;
      scanf("%d%d%d", &op, &x, &y);
      if (op == 1) {
        T.upd(x, y, 1, n, 1);
        if (x > 1) T.upd_min(1, x - 1, x - 1, 1, n, 1);
      } else {
        ll ans = S.ask(x, y, 1, n, 1);
        printf("%lld\n", ans);
      }
    }
    return 0;
  }
  