题目链接：hdu 4638 Group 代码 #include <cstdio>#include <cstring>#include <vector>#include <algorithm>using namespace std;#define lowbit(x) ((x)&(-x))const int maxn = 100005;typedef pair<int,int> pii

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4638 题意：给你n个数字，m个要查询的区间。 查询的是l-r区间内有几段连续的数字。  样例解释： 1 - 5 有数字3 1 2 5 4.排一下序：1 2 3 4 5.连续。所以输出1。  2 - 4 有数字1 2 5 4.排一下序：1 2  4 5，1 2连续，4 5连续。所以输出2。  思路：

线段树 题解： 题意为询问一段区间里的数能组成多少段连续的数。先考虑从左往右一个数一个数添加，考虑当前添加了i - 1个数的答案是x，那么添加完i个数后的答案是多少？可以看出，是根据a[i]-1和a[i]+1是否已经添加而定的，如果a[i]-1或者a[i]+1已经添加一个，则段数不变，如果都没添加则段数加1，如果都添加了则段数减1。设v[i]为加入第i个数后的改变量，那么加到第x数时的段数就是