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;
  template <typename T>
  void rd(T& x) {
    int f = 0, c;
    while (!isdigit(c = getchar())) f ^= !(c ^ 45);
    x = (c & 15);
    while (isdigit(c = getchar())) x = x * 10 + (c & 15);
    if (f) x = -x;
  }
  template <typename T>
  void pt(T x, int c = -1) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) pt(x / 10);
    putchar(x % 10 + 48);
    if (c != -1) putchar(c);
  }
  const int N = 200005, INF = 0X3F3F3F3F;
  int n, Q;
  struct seg2 {
    long long t[N * 4], tg[N * 4];
    int length[N * 4];
    void pst(int k1, long long k2) {
      tg[k1] += k2;
      t[k1] += k2 * length[k1];
    }
    void psd(int k1) {
      if (tg[k1]) {
        pst(k1 * 2, tg[k1]);
        pst(k1 * 2 + 1, tg[k1]);
        tg[k1] = 0;
      }
    }
    void upd(int k1) { t[k1] = t[k1 * 2] + t[k1 * 2 + 1]; }
    void bud(int k1, int k2, int k3) {
      length[k1] = k3 - k2 + 1;
      if (k2 == k3) {
        t[k1] = 1;
        return;
      }
      int mid = (k2 + k3) >> 1;
      bud(k1 * 2, k2, mid), bud(k1 * 2 + 1, mid + 1, k3);
      upd(k1);
    }
    void add(int k1, int k2, int k3, int k4, int k5, int k6) {
      if (k2 > k5 || k3 < k4) return;
      if (k4 <= k2 && k3 <= k5) {
        pst(k1, k6);
        return;
      }
      psd(k1);
      int mid = (k2 + k3) >> 1;
      add(k1 * 2, k2, mid, k4, k5, k6), add(k1 * 2 + 1, mid + 1, k3, k4, k5, k6);
      upd(k1);
    }
    long long res;
    void ask(int k1, int k2, int k3, int k4, int k5) {
      if (k2 > k5 || k3 < k4) return;
      if (k4 <= k2 && k3 <= k5) {
        res += t[k1];
        return;
      }
      psd(k1);
      int mid = (k2 + k3) >> 1;
      ask(k1 * 2, k2, mid, k4, k5), ask(k1 * 2 + 1, mid + 1, k3, k4, k5);
    }
    long long ask(int l, int r) {
      res = 0;
      ask(1, 1, n, l, r);
      return res;
    }
    void out(int k1, int k2, int k3) {
      if (k2 == k3) {
        ((void)0);
        return;
      }
      psd(k1);
      int mid = (k2 + k3) >> 1;
      out(k1 * 2, k2, mid), out(k1 * 2 + 1, mid + 1, k3);
    }
    void out() {
      ((void)0);
      out(1, 1, n), ((void)0);
    }
  } T;
  int mx[N * 4], cnt[N * 4], mx_[N * 4];
  void upd(int k1) {
    if (mx[k1 * 2] == mx[k1 * 2 + 1]) {
      mx[k1] = mx[k1 * 2];
      cnt[k1] = cnt[k1 * 2] + cnt[k1 * 2 + 1];
      mx_[k1] = max(mx_[k1 * 2], mx_[k1 * 2 + 1]);
    } else if (mx[k1 * 2] > mx[k1 * 2 + 1]) {
      mx[k1] = mx[k1 * 2];
      cnt[k1] = cnt[k1 * 2];
      mx_[k1] = max(mx_[k1 * 2], mx[k1 * 2 + 1]);
    } else {
      mx[k1] = mx[k1 * 2 + 1];
      cnt[k1] = cnt[k1 * 2 + 1];
      mx_[k1] = max(mx_[k1 * 2 + 1], mx[k1 * 2]);
    }
  }
  void bud(int k1, int k2, int k3) {
    if (k2 == k3) {
      mx[k1] = k2, mx_[k1] = ~INF;
      cnt[k1] = 1;
      return;
    }
    int mid = (k2 + k3) >> 1;
    bud(k1 * 2, k2, mid), bud(k1 * 2 + 1, mid + 1, k3);
    upd(k1);
  }
  void mdf(int k1, int k2, int k3, int k4, int k5, int k6) {
    if (k2 > k5 || k3 < k4 || mx[k1] <= k6) return;
    if (k4 <= k2 && k3 <= k5) {
      if (mx_[k1] < k6) {
        T.add(1, 1, n, k6 + 1, mx[k1], -cnt[k1]);
        mx[k1] = k6;
        return;
      }
    }
    mx[k1 * 2] = min(mx[k1 * 2], mx[k1]);
    mx[k1 * 2 + 1] = min(mx[k1 * 2 + 1], mx[k1]);
    int mid = (k2 + k3) >> 1;
    mdf(k1 * 2, k2, mid, k4, k5, k6), mdf(k1 * 2 + 1, mid + 1, k3, k4, k5, k6);
    upd(k1);
  }
  void chg(int k1, int k2, int k3, int k4, int k5) {
    if (k2 == k3) {
      if (k2 < mx[k1]) {
        T.add(1, 1, n, k2 + 1, mx[k1], -1);
      }
      mx[k1] = k5;
      if (k2 < mx[k1]) {
        T.add(1, 1, n, k2 + 1, mx[k1], 1);
      }
      return;
    }
    mx[k1 * 2] = min(mx[k1 * 2], mx[k1]);
    mx[k1 * 2 + 1] = min(mx[k1 * 2 + 1], mx[k1]);
    int mid = (k2 + k3) >> 1;
    if (k4 <= mid)
      chg(k1 * 2, k2, mid, k4, k5);
    else
      chg(k1 * 2 + 1, mid + 1, k3, k4, k5);
    upd(k1);
  }
  void out(int k1, int k2, int k3) {
    if (k2 == k3) {
      ((void)0);
      return;
    }
    mx[k1 * 2] = min(mx[k1 * 2], mx[k1]);
    mx[k1 * 2 + 1] = min(mx[k1 * 2 + 1], mx[k1]);
    int mid = (k2 + k3) >> 1;
    out(k1 * 2, k2, mid), out(k1 * 2 + 1, mid + 1, k3);
    upd(k1);
  }
  int main() {
    rd(n), rd(Q);
    T.bud(1, 1, n);
    bud(1, 1, n);
    for (int i = (1); i <= (Q); ++i) {
      int tp;
      rd(tp);
      if (tp == 1) {
        int c, g;
        rd(c), rd(g);
        if (1 <= c - 1) mdf(1, 1, n, 1, c - 1, c - 1);
        chg(1, 1, n, c, g);
      } else {
        int l, r;
        rd(l), rd(r);
        printf("%lld\n", T.ask(l, r));
      }
    }
    return 0;
  }
  