思路与算法

每次种树新增一种独立的树，保留它的区间 [l,r]。它与查询 [L,R] 相交，当且仅当 l≤R 且 r≥L。因此答案等于“左端点≤R的区间数”减去“右端点<L的区间数”。用两棵树状数组分别维护左端点与右端点的出现次数；插入时各做一次点加，查询时各取一次前缀和。

正确性说明

左端点大于 R 的区间不可能相交；剩下的区间中，只有右端点小于 L 的区间完全在查询左侧，需要排除。由于区间满足 l≤r，所有右端点<L的区间都已包含在左端点≤R的集合中，恰好减去一次，不会漏计或重复。

复杂度

时间 O(N+M log N)，空间 O(N)。

易错点

一次种树对应一个种类，即使区间完全相同也要再次计数。不要把答案误写成覆盖长度或覆盖次数之和。闭区间在端点相等时仍然相交，所以右端点查询使用 L-1。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> left(n + 1), right(n + 1);
    auto add = [&](vector<int> &t, int x) {
        for (; x <= n; x += x & -x)
            t[x]++;
    };
    auto sum = [&](vector<int> &t, int x) {
        int ans = 0;
        for (; x; x -= x & -x)
            ans += t[x];
        return ans;
    };
    while (m--) {
        int k, l, r;
        cin >> k >> l >> r;
        if (k == 1) {
            add(left, l);
            add(right, r);
        } else
            cout << sum(left, r) - sum(right, l - 1) << '\n';
    }
}