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;
  const int MAX_N = 2e5 + 14;
  int n, q;
  struct SegmentLazy {
    int lazy[MAX_N << 2];
    long long s[MAX_N << 2];
    void build(int id = 1, int l = 0, int r = n) {
      if (r - l < 2) {
        s[id] = 1;
        return;
      }
      int mid = (l + r) >> 1;
      build(id << 1, l, mid);
      build(id << 1 | 1, mid, r);
      s[id] = s[id << 1] + s[id << 1 | 1];
    }
    void up(int id, int l, int r, int x) {
      lazy[id] += x;
      s[id] += long long(r - l) * x;
    }
    void shift(int id, int l, int r) {
      int mid = (l + r) >> 1;
      up(id << 1, l, mid, lazy[id]);
      up(id << 1 | 1, mid, r, lazy[id]);
      lazy[id] = 0;
    }
    void add(int st, int en, int v, int id = 1, int l = 0, int r = n) {
      if (en <= l || r <= st) return;
      if (st <= l && r <= en) {
        up(id, l, r, v);
        return;
      }
      shift(id, l, r);
      int mid = (l + r) >> 1;
      add(st, en, v, id << 1, l, mid);
      add(st, en, v, id << 1 | 1, mid, r);
      s[id] = s[id << 1] + s[id << 1 | 1];
    }
    long long sum(int st, int en, int id = 1, int l = 0, int r = n) {
      if (en <= l || r <= st) return 0;
      if (st <= l && r <= en) return s[id];
      shift(id, l, r);
      int mid = (l + r) >> 1;
      return sum(st, en, id << 1, l, mid) + sum(st, en, id << 1 | 1, mid, r);
    }
  } segment_lazy;
  struct SegmentBeats {
    struct Node {
      int m, c, s;
      Node operator+(const Node &o) const {
        if (m > o.m) return {m, c, max(s, o.m)};
        if (m < o.m) return {o.m, o.c, max(o.s, m)};
        return {m, c + o.c, max(s, o.s)};
      }
    } seg[MAX_N * 4];
    int lazy[MAX_N * 4];
    SegmentBeats() { memset(lazy, -1, sizeof lazy); }
    void build(int l = 0, int r = n, int id = 1) {
      if (l + 1 == r) {
        seg[id] = {r, 1, -1};
        return;
      }
      int mid = (l + r) / 2;
      build(l, mid, id * 2);
      build(mid, r, id * 2 + 1);
      seg[id] = seg[id * 2] + seg[id * 2 + 1];
    }
    void up(int id, int x) {
      if (seg[id].m <= x) return;
      lazy[id] = seg[id].m = x;
    }
    void shift(int id) {
      if (lazy[id] == -1) return;
      up(id * 2, lazy[id]);
      up(id * 2 + 1, lazy[id]);
      lazy[id] = -1;
    }
    int get(int p, int l = 0, int r = n, int id = 1) {
      if (l + 1 == r) return seg[id].m;
      shift(id);
      int mid = (l + r) / 2;
      return (p < mid ? get(p, l, mid, id * 2) : get(p, mid, r, id * 2 + 1));
    }
    void modify(int p, int x, int l = 0, int r = n, int id = 1) {
      if (l + 1 == r) {
        seg[id].m = x;
        return;
      }
      shift(id);
      int mid = (l + r) / 2;
      if (p < mid)
        modify(p, x, l, mid, id * 2);
      else
        modify(p, x, mid, r, id * 2 + 1);
      seg[id] = seg[id * 2] + seg[id * 2 + 1];
    }
    void upd(int s, int e, int x, int l = 0, int r = n, int id = 1) {
      if (e <= l || r <= s || seg[id].m <= x) return;
      if (s <= l && r <= e && seg[id].s < x) {
        segment_lazy.add(x, seg[id].m, -seg[id].c);
        up(id, x);
        return;
      }
      shift(id);
      int mid = (l + r) / 2;
      upd(s, e, x, l, mid, id * 2);
      upd(s, e, x, mid, r, id * 2 + 1);
      seg[id] = seg[id * 2] + seg[id * 2 + 1];
    }
  } segment_beats;
  int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    segment_lazy.build();
    segment_beats.build();
    while (q--) {
      int t;
      cin >> t;
      if (t == 1) {
        int c, g;
        cin >> c >> g;
        --c;
        int pw = segment_beats.get(c);
        segment_lazy.add(c, pw, -1);
        segment_lazy.add(c, g, +1);
        segment_beats.upd(0, c, c);
        segment_beats.modify(c, g);
      } else {
        int l, r;
        cin >> l >> r;
        cout << segment_lazy.sum(--l, r) << '\n';
      }
    }
  }
  