题目描述

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

• k == 1，读入l, r表示在 l 到 r 之间种上一种树，每次操作种的树的种类都不同；

• k == 2，读入l, r表示询问 l 到 r 之间有多少种树。

注意：每个位置都可以重复种树。

输入格式

第一行 n 表示道路总长为 n，共有 m 个操作；
接下来 m 行为 m 个操作。

输出格式

对于每个 k == 2 输出一个答案。

样例

样例输入

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

样例输出

1
2

题解

拿到题第一眼，发现这不和HH的项链很像吗，但仔细观察就会发现，那道题是给出了确定的数列与确定的区间，而这道题的序列是变化的，这决定了区间询问不能由上一步继承下来，所以要换思路；

仔细思考，我们不难发现，如果要求一段区间的种类数，只需用1~右端点这段区间的总种类数-1~左端点这段区间的总种类数，即可得到解；

对于上述思路，很容易发现要求很多前缀和，于是用两个树状数组分别求左端点总数和右端点总数，最后用1~右端点这段区间的总左端点数 - 1~左端点这段区间的总右端点数（不包括左端点，因为种树是也会在左端点种）即为结果；

证明此做法的正确性：

1~右端点这段区间的总左端点数 相当于 1~右端点这段区间的总种类数；

1~左端点这段区间的总右端点数 相当于 1~左端点这段区间的总种类数；

根据上述结论，即可得知此做法正确；

如果还不明白，那就画画图理解理解，我有点懒，就不画了；

所以，这道题的本质就是树状数组的单点修改与区间查询；

代码

#include <iostream>
using namespace std;
int t[1000005]; //左端点；
int t1[1000005]; //右端点；
int n, m;
int lowbit(int x) {
	return x & (-x);
}
void add_dian(int x, int k) { //左端点加点；
	while(x <= n) {
		t[x] += k;
		x += lowbit(x);
	}
}
void add_dian1(int x, int k) { //右端点加点；
	while(x <= n) {
		t1[x] += k;
		x += lowbit(x);
	}
}
long long ask_sum(int x) { //左端点求和；
	long long ans = 0;
	while(x > 0) {
		ans += t[x];
		x -= lowbit(x);
	}
	return ans;
}
long long ask_sum1(int x) { //右端点求和；
	long long ans = 0;
	while(x > 0) {
		ans += t1[x];
		x -= lowbit(x);
	}
	return ans;
}
int main() {
	cin >> n >> m;
	int k, a, b;
	for (int i = 1; i <= m; i++) {
		cin >> k >> a >> b;
		if (k == 1) {
			add_dian(a, 1);
			add_dian1(b, 1);
		}
		if (k == 2) {
			cout << ask_sum(b) - ask_sum1(a - 1) << endl; //不包括区间左端点，所以要a - 1；
		}
	}
	return 0;
}