连接：http://acm.hdu.edu.cn/showproblem.php?pid=4638
题意：就给给你n个数（大小在1-n里），然后给你连续的可以构成一个块，再给你N个询问，每个询问一个l,一个r问你l-r里面有多少个连续的段
其实每一个数都是一个独立的段，当有连续的时候连续段数就会-1，因为连续的段中，位置最靠前的哪一个只会影响以这个位置为l的询问，不会影响后面的，所以，我们可以对询问从后向前去找，离线话去找。这样的话就可以用树状数组去解决问题、
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <queue>
#define loop(s,i,n) for(i = s;i < n;i++)
#define cl(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x&-x
using namespace std;
int c[];
vector<int> e[];
struct node
{
int r,num;
};
vector <node> q[];
int m,n;
int sum(int x)
{
int res = ;
while(x > )
{
res += c[x];
x -= lowbit(x);
}
return res;
} void add(int x,int d)
{
while(x <= n)
{
c[x] += d;
x += lowbit(x);
}
}
int loc[];
int a[];
int ans[]; int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int i,j;
cl(c,);
scanf("%d %d",&n,&m);
loop(,i,n+)
{
scanf("%d",a+i);
loc[a[i]] = i;
}
loop(,i,n+)
e[i].clear();
loop(,i,n+)
{
if(a[i]> )
{
if(loc[a[i]-] > loc[a[i]])
e[loc[a[i]]].push_back(loc[a[i]-]);
else
e[loc[a[i]-]].push_back(loc[a[i]]);
}
}
loop(,i,m+)
{
q[i].clear();
}
loop(,i,m+)
{
int l,r;
struct node temp;
scanf("%d %d",&l,&r);
temp.num = i,temp.r = r; q[l].push_back(temp);
} for(i = n;i >= ;i--)
{
loop(,j,e[i].size())
{
int v;
v = e[i][j];
add(v,);
} loop(,j,q[i].size())
{
ans[q[i][j].num] = q[i][j].r-i-sum(q[i][j].r)+;
} } loop(,i,m+)
printf("%d\n",ans[i]); }
return ;
}