测试地址：☞
【题目描述】
原题来自：Vijos P1448
校门外有很多树，学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两种操作：
K=1，读入 l,r 表示在 l 到 r 之间种上一种树，每次操作种的树的种类都不同；
K=2，读入 l,r 表示询问 l 到 r 之间有多少种树。
注意：每个位置都可以重复种树。
【输入】
第一行 n,m 表示道路总长为 n，共有 m 个操作；
接下来 m 行为 m 个操作。
【输出】
对于每个 k=2 输出一个答案。
【输入样例】
5 4 1 1 3 2 2 5 1 2 4 2 3 5【输出样例】
1 2【提示】
数据范围与提示：
对于 20 的数据，1 ≤ n,m ≤ 100；
对于 %60 的数据，1 ≤ n ≤ 10^3,1 ≤ m ≤ 5×10^4；
对于 %100 的数据，1 ≤ n,m ≤ 5×10^4，保证 l,r > 0。
【思路】
相当与给你一大堆线段，问给你的区间与多少线段有交点
于是有了一种十分魔性的方法：括号法
假设有一个长度为 10 的数轴，我们要将区间 [ 2 , 5 ] 中种树，这时，我们将 2 处放一个左括号 ” ( ” ,5处放一个 ” )” ，表示区间 [ 2 , 5 ]种了树。
查询某个区间树的种类，如区间[ 3 , 10]，只需统计10之前（包括10）有多少个‘（’，统计3之前有多少个‘）’，（不包括3）。 然后维护一个树状数组就ok了
【AC代码】
#include<cstdio> const int maxn=1e6+7; int n, m; int a[maxn], b[maxn]; int lowbit(int x){ return x&(-x); } void update(int x, int a[]){ for(int i = x; i <= n; i+=lowbit(i)) a[i]++; } int sum(int x, int a[]){ int sumn = 0; for(int i = x; i > 0; i-=lowbit(i)){ sumn += a[i]; } return sumn; } int main(){ scanf("%d%d", &n, &m); while(m--){ int k, l, r; scanf("%d%d%d", &k, &l, &r); if(k == 1) { update(l, a); //左括号 update(r, b); //右括号 } else{ printf("%d\n", sum(r, a)-sum(l-1, b)); } } return 0; }
