[Vijos P1448] 校门外的树 题解
题目描述
校门外有很多树，学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两种操作：
-
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;
}