#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;

// 两棵树状数组，支持区间加法 + 区间求和
int c1[MAXN], c2[MAXN];

// lowbit：取最低位为 1 的值
inline int low(int x) {
    return x & -x;
}

// 区间更新：给 [l..r] 每个点加 1
void range_add(int l, int r, int n) {
    // 在 c1 上，l 及以后的前缀加 1
    for (int i = l; i <= n+1; i += low(i)) {
        c1[i] += 1;
    }
    // 在 c2 上，r+1 及以后的前缀减 1
    for (int i = r + 1; i <= n+1; i += low(i)) {
        c2[i] += 1;
    }
}

// 区间求和：计算 [l..r] 上所有点的增量总和
int range_sum(int l, int r) {
    int res = 0;
    // sum1 = sum_{i=1..r} c1[i]
    for (int i = r; i > 0; i -= low(i)) {
        res += c1[i];
    }
    // sum2 = sum_{i=1..l-1} c2[i]
    for (int i = l - 1; i > 0; i -= low(i)) {
        res -= c2[i];
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    // 操作
    while (m--) {
        int k, l, r;
        cin >> k >> l >> r;
        if (k == 1) {
            // 类型 1：在区间 [l..r] 种新树
            range_add(l, r, n);
        } else {
            // 类型 2：查询 [l..r] 有多少种树
            cout << range_sum(l, r) << "\n";
        }
    }
    return 0;
}

详细注释说明

1. 两棵树状数组 c1 和 c2

   • 用来在 $O(\log n)$ 完成区间加法与区间求和。
   • c1 记录「从左端开始，每个点的累积加次数」。
   • c2 记录「从右端结束，每个点的累积减次数」。

2. range_add(l,r,n)

   • 对所有 $i \ge l$，c1[i] += 1，表示从位置 $l$ 开始每个点都要加 1。
   • 对所有 $i \ge r+1$，c2[i] += 1，表示从位置 $r+1$ 开始要「撤销」这次加 1。

3. range_sum(l,r)

   • 先累加 c1[1..r]，得到所有在 $\le r$ 的「前缀加次数」。
   • 再减去 c2[1..(l-1)]，去掉那些在 $\le l-1$ 范围内「被撤销」的次数。
   • 剩下的就是区间 $[l..r]$ 上有效的「加 1」总次数，也就是有多少次在此区间种过树——即有多少种树。

4. 复杂度

   • 每次更新或查询均为 $O(\log n)$，处理 $m \le 5\times10^4$ 条操作总共 $O(m\log n)$，高效通过。