\(LOJ \ 10115\). 「一本通 4.1 例 3」校门外的树
一、题目描述
校门外有很多树，学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两种操作：
- \(K=1\)，读入 \(l,r\) 表示在 \(l\) 到 \(r\) 之间种上一种树，每次操作种的树的种类都不同；
- \(K=2\)，读入 \(l,r\) 表示询问 \(l\) 到 \(r\) 之间有多少种树。
注意：每个位置都可以重复种树。
输入格式
第一行 \(n,m\) 表示道路总长为 \(n\)，共有 \(m\) 个操作；
接下来 \(m\) 行为 \(m\) 个操作。
输出格式
对于每个 \(k=2\) 输出一个答案。
二、题目解析
开始怎么想都不知道怎么维护不同段中树的种类是否相同的情况，感觉这题有个思维技巧还是挺难想的，就是我们要开两个数组，\(sum_1\)分别维护左端点的数目，另一个数组\(sum_2\)维护右端点的数目。这样区间\([l,r]\)的树的种类的数目就是\(1-r\)中左端点的数目减去\(1-(l-1)\)中右端点的数目，即表示为\(sum_1[r]-sum_2[l-1]\)。
如图假如我们第一次在区间\(a[2,6]\)种上一种树，然后再在区间\(b[5,10]\)种上一种树，这时我们要统计区间\(c[8,12]\)中树的种类数目，我们就统计\([1,12]\)中左端点的数目即 \(sum_1[12]\)等于\(2\)，说明有两种树可能在给定区间内，然后我们再求区间\([1,7]\)中右端点的数目即\(sum_2[7]=1\),表示有一种树完全在给定区间左边，并不是我们要求的，所以减去就好了，所以答案就为\(sum_1[12]-sum_2[7]\)了。
\(Code\)
#include <bits/stdc++.h>
using namespace std;
int const N = 50010;
int n, m;
// 树状数组模板
int sum1[N], sum2[N];
int lowbit(int x) {
return x & -x;
}
void add(int tr[], int x, int c) {
for (int i = x; i < N; i += lowbit(i)) tr[i] += c;
}
int sum(int tr[], int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("LOJ10115.in", "r", stdin);
#endif
int k, l, r;
scanf("%d%d", &n, &m); // 第一行 n,m 表示道路总长为 n，共有 m 个操作；
// n下面没有使用过。为什么呢？其实是n的上限N有用！我们就没有用到n,代码模板中也去掉了n的
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &k, &l, &r);
if (k == 1)
add(sum1, l, 1), add(sum2, r, 1); // sum1记录左括号的个数，sum2记录右括号的个数
else
printf("%d\n", sum(sum1, r) - sum(sum2, l - 1));
}
return 0;
}