题目大意：
给出的询问，求出这个区间的里 差小于等于 2 的数字的对数。
思路分析：
莫队算法。
然后分析一下。
假设添加了一个数字。那么就要加它旁边相差为2 的数字的和。
反之降低一个。就要降低相差为2 的数字的和。再减去自己这个1.。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 100005 using namespace std; int app[maxn];
int save[maxn];
int pos[maxn]; struct foo
{
int l,r,index;
int ans;
bool operator < (const foo &cmp)const
{
if(pos[l] == pos[cmp.l])
return r<cmp.r;
return pos[l]<pos[cmp.l];
}
}Q[maxn];
bool cmp_id(const foo &a, const foo &b)
{
return a.index < b.index;
}
void debug()
{
for(int i=0;i<=7;i++)
printf("%d ",app[i]);
puts("");
}
void modify(int p,int &ans,int add)
{
int tot=0;
for(int i=max(save[p]-2,0);i<=save[p]+2;i++)
{
tot+=app[i];
} if(add>0)ans+=tot;
else ans-=tot-1;
app[save[p]]+=add;
}
int main()
{
int n,m;
int cas=1;
while(scanf("%d%d",&n,&m)!=EOF)
{
int SIZE=(int)sqrt(1.0*n);
memset(app,0,sizeof app); for(int i=1;i<=n;i++)
{
scanf("%d",&save[i]);
pos[i]=(i-1)/SIZE+1;
} for(int i=0;i<m;i++)
{
scanf("%d%d",&Q[i].l,&Q[i].r);
Q[i].index=i;
} sort(Q,Q+m);
int ans=0;
for(int i=0,l=1,r=0;i<m;i++)
{
if(r<Q[i].r)
{
for(r=r+1;r<=Q[i].r;r++)
modify(r,ans,1);
r--;
}
if(r>Q[i].r)
{
for(;r>Q[i].r;r--)
modify(r,ans,-1);
}
if(l<Q[i].l)
{
for(;l<Q[i].l;l++)
modify(l,ans,-1);
}
if(l>Q[i].l)
{
for(l=l-1;l>=Q[i].l;l--)
modify(l,ans,1);
l++;
}
Q[i].ans=ans;
} sort(Q,Q+m,cmp_id);
printf("Case %d:\n",cas++);
for(int i=0;i<m;i++)
printf("%d\n",Q[i].ans);
}
return 0;
}