题意：给你n个数，问第l个到第r个可以组成多少连续的数段。
题意为询问一段区间里的数能组成多少段连续的数。先考虑从左往右一个数一个数添加，考虑当前添加了i - 1个数的答案是x，那么添加完i个数后的答案是多少？可以看出，是根据a[i]-1和a[i]+1是否已经添加而定的，如果a[i]-1或者a[i]+1已经添加一个，则段数不变，如果都没添加则段数加1，如果都添加了则段数减1。设v[i]为加入第i个数后的改变量，那么加到第x数时的段数就是sum{v[i]} (1<=i<=x}。仔细想想，若删除某个数，那么这个数两端的数的改变量也会跟着改变，这样一段区间的数构成的段数就还是他们的v值的和。将询问离线处理，按左端点排序后扫描一遍，左边删除，右边插入，查询就是求区间和。
以上是官方解题报告原文。
对于这题，有点难想啊，想明白了就好做了，树状数组和线段数都可以。
树状数组：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int c[100005],a[100005],d[100005],m,n,k,ans[100005];
bool v[100005];
struct query
{
int l,r,id;
}q[100005];
bool cmp(query x,query y)
{
return x.l<y.l;
}
void add(int i,int s)
{
for(int j=i;j<=n;j+=(j&(-j)))c[j]+=s;
}
int sum(int i)
{
int s=0;
for(int j=i;j>0;j-=(j&(-j)))s+=c[j];
return s;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(c,0,sizeof(c));
memset(v,0,sizeof(v));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
d[a[i]]=i;
}
for(int i=0;i<m;i++)
{
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
for(int i=1;i<=n;i++)
{
if(v[a[i]+1]&&v[a[i]-1])add(i,-1);
else if(!v[a[i]+1]&&!v[a[i]-1])add(i,1);
v[a[i]]=1;
}
sort(q,q+m,cmp);
k=1;
for(int i=0;i<m;i++)
{
while(k<q[i].l)
{
if(d[a[k]+1]>d[a[k]]&&a[k]<n)add(d[a[k]+1],1);
if(d[a[k]-1]>d[a[k]]&&a[k]>1)add(d[a[k]-1],1);
k++;
}
ans[q[i].id]=sum(q[i].r)-sum(q[i].l-1);
}
for(int i=0;i<m;i++)printf("%d\n",ans[i]);
}
return 0;
}
线段树：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
int l,r,val,sum;
}t[100004*4];
struct qu
{
int l,r,id;
}q[100005];
int m,n,d[100005],a[100005],va[100005],k,ss,ans[100005];
bool v[100005];
bool cmp(const qu &x,const qu &y)
{
return x.l<y.l;
}
void build(int ll,int rr,int rot)
{
t[rot].l=ll;
t[rot].r=rr;
if(ll==rr)
{
t[rot].val=va[ll];
t[rot].sum=va[ll];
}
else
{
int mid=(ll+rr)/2;
build(ll,mid,rot<<1);
build(mid+1,rr,rot<<1|1);
t[rot].sum=t[rot<<1].sum+t[rot<<1|1].sum;
}
}
void update(int x,int s,int rot)
{
if(t[rot].l==x&&t[rot].r==x)
{
t[rot].val+=s;
t[rot].sum=t[rot].val;
}
else
{
int mid=(t[rot].l+t[rot].r)/2;
if(x>mid)update(x,s,rot<<1|1);
else update(x,s,rot<<1);
t[rot].sum=t[rot<<1].sum+t[rot<<1|1].sum;
}
}
void query(int ll,int rr,int rot)
{
if(t[rot].l==ll&&t[rot].r==rr)
{
ss+=t[rot].sum;
}
else
{
int mid=(t[rot].l+t[rot].r)/2;
if(rr<=mid)query(ll,rr,rot<<1);
else if(ll>mid)query(ll,rr,rot<<1|1);
else
{
query(ll,mid,rot<<1);
query(mid+1,rr,rot<<1|1);
}
}
}
int main()
{
int tt;
scanf("%d",&tt);
while(tt--)
{
memset(v,0,sizeof(v));
memset(va,0,sizeof(va));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
d[a[i]]=i;
if(v[a[i]-1]&&v[a[i]+1])va[i]--;
else if(!v[a[i]-1]&&!v[a[i]+1])va[i]++;
v[a[i]]=1;
}
for(int i=0;i<m;i++)
{
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
build(1,n,1);
sort(q,q+m,cmp);
k=1;
for(int i=0;i<m;i++)
{
while(q[i].l>k)
{
if(d[a[k]+1]>d[a[k]]&&a[k]<n)update(d[a[k]+1],1,1);
if(d[a[k]-1]>d[a[k]]&&a[k]>1)update(d[a[k]-1],1,1);
k++;
}
ss=0;
query(q[i].l,q[i].r,1);
ans[q[i].id]=ss;
}
for(int i=0;i<m;i++)printf("%d\n",ans[i]);
}
return 0;
}