HDU-4638
题意：
给定n个数，值为1~n。m次询问，每次询问一个区间内拥有连续数段有多少个。
解法：
1、利用树状数组可以做。
2、利用莫队暴力访问（更简单）；
莫队做法：
我们知道莫队是对询问区间进行处理的，因此需要去寻找区间变化过程中的情况和对答案的影响。
假定区间（l,r），若要加一个数x进去则只需判断x-1，x+1在（l,r）分布即可。
有四种情况：
a、x+1，x-1两个都没有在（l,r）则新增了一组数，故cnt++;
b、x+1，x-1两个都在（l，r）则该数将两组数连在一起了减少了一组数，故cnt–；
c、x+1、x-1两个数有一个在（l,r），则相当于没有增加新的组数。
d、当x为1和n时要单独判断。
若要从区间减一个数x出去也需判断x-1，x+1在（l,r）分布即可。
有四种情况：
a、x+1，x-1两个都没有在（l,r）则减去一组数，故cnt–;
b、x+1，x-1两个都在（l，r）则该数将两组数断开了增加了一组数，故cnt++；
c、x+1、x-1两个数有一个在（l,r），则相当于没有减去组数。
d、当x为1和n时要单独判断。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
const int N=1e5+55;
int a[N],pos[N],s[N];
int cnt,l,r,n,m;
struct node{     //对莫队分块的处理int l,r,id,bl;node(int l=0,int r=0,int id=0,int bl=0):l(l),r(r),id(id),bl(bl){}friend bool operator <(node x, node y){return x.bl==y.bl?(x.bl&1)?x.r<y.r:x.r>y.r:x.l<y.l;}
}q[N];
inline int read()   //快读
{register int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;
}
inline void add(int x)   //增加一个数
{if(a[x]==1&&(pos[2]<l||pos[2]>r)) cnt++;else if(a[x]==n&&(pos[n-1]<l||pos[n-1]>r)) cnt++;else if(a[x]!=1&&a[x]!=n&&(pos[a[x]-1]<l||pos[a[x]-1]>r)&&(pos[a[x]+1]>r||pos[a[x]+1]<l)) cnt++;else if(a[x]!=1&&a[x]!=n&&pos[a[x]-1]>=l&&pos[a[x]+1]<=r&&pos[a[x]-1]<=r&&pos[a[x]+1]>=l) cnt--;
}
inline void del(int x)   //减去一个数
{if(a[x]==1&&(pos[2]<l||pos[2]>r)) cnt--;else if(a[x]==n&&(pos[n-1]<l||pos[n-1]>r)) cnt--;else if(a[x]!=1&&a[x]!=n&&(pos[a[x]-1]<l||pos[a[x]-1]>r)&&(pos[a[x]+1]>r||pos[a[x]+1]<l)) cnt--;else if(a[x]!=1&&a[x]!=n&&pos[a[x]-1]>=l&&pos[a[x]+1]<=r&&pos[a[x]-1]<=r&&pos[a[x]+1]>=l) cnt++;
}
int main()
{int t;scanf("%d",&t);while(t--){n=read(),m=read();for(int i=1;i<=n;++i){a[i]=read();pos[a[i]]=i;}int blocksize=(int)sqrt(n);for(int i=1;i<=m;++i){l=read(),r=read();q[i]=node(l,r,i,(l-1)/blocksize+1);}sort(q+1,q+m+1);cnt=0;l=1,r=0;for(int i=1;i<=m;++i){int ll=q[i].l,rr=q[i].r;while(r<rr) add(++r);while(r>rr) del(r--);while(l<ll) del(l++);while(l>ll) add(--l);s[q[i].id]=cnt;}for(int i=1;i<=m;++i)printf("%d\n",s[i]);}return 0;
}