好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

---

题目描述

原题来自：Vijos P1448

校门外有很多树，学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两种操作：

• $K=1$，读入 $l, r$ 表示在 $[l, r]$ 之间种上一种树，每次操作种的树的种类都不同；
• $K=2$，读入 $l, r$ 表示询问 $[l, r]$ 之间有多少种树。

注意：每个位置都可以重复种树（即不同种类的树可以覆盖同一位置）。

---

输入格式

第一行两个整数 $n, m$，表示道路总长为 $n$，共有 $m$ 个操作；

接下来 $m$ 行，每行三个整数 $K, l, r$，表示一个操作。

---

输出格式

对于每个 $K=2$ 的操作，输出一行一个整数，表示询问 $[l, r]$ 之间有多少种树。

---

样例

样例输入

5 4
1 1 3
2 2 5
1 2 4
2 3 5

样例输出

1
2

样例解释

道路长度 $n=5$，初始没有树。

操作1：在 $[1,3]$ 种一种树（种类1）。
操作2：询问 $[2,5]$ 有多少种树。此时只有种类1覆盖了位置 $2,3$，所以答案是 $1$。
操作3：在 $[2,4]$ 种一种树（种类2）。
操作4：询问 $[3,5]$ 有多少种树。此时：

• 位置3被种类1和种类2覆盖；
• 位置4被种类2覆盖；
• 位置5没有被任何树覆盖。
  所以覆盖 $[3,5]$ 的树的种类有 $\{1,2\}$，共 $2$ 种。

---

数据范围

• 对于 $20\%$ 的数据，$1 \le n, m \le 100$；
• 对于 $60\%$ 的数据，$1 \le n \le 10^3, 1 \le m \le 5\times 10^4$；
• 对于 $100\%$ 的数据，$1 \le n, m \le 5\times 10^4$，保证 $l, r > 0$。

---

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$（512 MB）

---

提示
此题为 区间覆盖种类数查询 问题，可以用 树状数组 或 线段树 维护 区间左端点/右端点信息。

转化思路： 对于一次询问 $[l, r]$，一种树（即一次种植操作 $[L, R]$）被计入答案，当且仅当 $[L, R]$ 与 $[l, r]$ 有交集。

交集条件：$[L, R] \cap [l, r] \neq \varnothing$ 等价于 不是 $R < l$ 且不是 $L > r$，即 $R \ge l$ 且 $L \le r$。

因此，对于询问 $[l, r]$，答案 = 总种植次数 − $R < l$ 的种植数 − $L > r$ 的种植数。

但是这样计算不方便，更常见的方法是：

• 统计所有 $L \le r$ 的种植数（即左端点在 $r$ 及其左边的种植数）；
• 统计所有 $R < l$ 的种植数（即右端点在 $l$ 左边的种植数）；
• 交集数量 = $L \le r$ 的数量 − $R < l$ 的数量。

证明： 所有种植区间分为三类：

1. $R < l$：完全在 $[l, r]$ 左边，与询问区间无交集；
2. $L > r$：完全在 $[l, r]$ 右边，与询问区间无交集；
3. 其他：与 $[l, r]$ 有交集。

因此，有交集的种植数 = 总种植数 − $R < l$ 的数量 − $L > r$ 的数量。
但 $L > r$ 的数量 = 总种植数 − $L \le r$ 的数量。
所以：

$$\text{答案} = (\text{总种植数}) - (\text{R<l 的数量}) - (\text{总种植数} - \text{L≤r 的数量}) = \text{L≤r 的数量} - \text{R<l 的数量}$$

实现：

• 用两个树状数组（或线段树）分别维护所有种植区间的左端点 $L$ 和右端点 $R$；
• 对于每次种植操作 $[L,R]$，在左端点树状数组的 $L$ 位置加 $1$，在右端点树状数组的 $R$ 位置加 $1$；
• 对于每次查询 $[l,r]$：
  • $cntL = sumL(r)$（左端点 $\le r$ 的种植数）；
  • $cntR = sumR(l-1)$（右端点 $< l$ 的种植数）；
  • 答案 $= cntL - cntR$。

复杂度：每次操作 $O(\log n)$。

注意：$n$ 是道路长度，但 $L, R$ 范围也是 $[1, n]$，因此树状数组大小应为 $n$。