题意
找到区间里有多少组连续数字串
分析：
（转）思路：显然，我们要使得value最大，就要尽量将连续的ID分在一组，所以问题转化为求一个区间中连续ID区间的个数。我们从左往右扫描，依次考虑右端点为i的询问，设dp[l]为区间[l，i]的连续区间个数，po[i]为i出现的位置，若还未出现，则为0，设我们当前考虑的右端点为a[i]，首先我们假设a[i]不能和区间[1,i-1]中的任何一个数分到一组，则我们要将dp[1]到dp[i-1]全部加1，然后考虑po[a[i]+1]是否不为0，若不为0则说明a[i]-1已经在前面出现，则我们需要将dp[1]到dp[po[a[i]+1]]全部减一个1，因为a[i]可以和a[i]+1分为一组，则我们之前加的1是多余的。对于a[i]-1的情况同理。以上操作可以由线段树或者树状数组什么的实现，然后再将询问按照右端点从小到大排序，离线处理即可，以下是代码实现
// File Name: 1007.cpp
// Author: Zlbing
// Created Time: 2013年08月02日 星期五 07时44分46秒 #include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)
const int MAXN=1e5+;
int tree[MAXN];
int n;
int lowbit(int x)
{
return x&(-x);
} void add(int pos,int val)////如果要把a[i]增加v，可以通过调用如下函数实现
{
while(pos <=n)
{
tree[pos] += val;
pos += lowbit(pos);//pos+lowbit(x)可以理解变成了x的父亲
}
} int read(int x)//前x项和
{
int s=;
while(x>)
{
s += tree[x];
x -= lowbit(x);//x-lowbit(x)可以理解成变成了x的兄弟
}
return s;
}
int A[MAXN],pos[MAXN];
struct node{
int l,r,index;
bool operator <(const node& rsh)const{
if(r==rsh.r)
return l<rsh.l;
else return r<rsh.r;
}
};
vector<node> Q;
int ans[MAXN];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int m;
scanf("%d%d",&n,&m);
REP(i,,n){
scanf("%d",&A[i]);
pos[A[i]]=i;
}
Q.clear();
node tmp;
REP(i,,m)
{
scanf("%d%d",&tmp.l,&tmp.r);
tmp.index=i;
Q.push_back(tmp);
}
sort(Q.begin(),Q.end());
CL(tree,);
int j=;
for(int i=;i<=n;i++)
{
add(i,);
if(A[i]+<=n&&pos[A[i]+]<i)
{
add(pos[A[i]+],-);
}
if(A[i]->=&&pos[A[i]-]<i)
{
add(pos[A[i]-],-);
}
while(Q[j].r==i)
{
ans[Q[j].index]=read(Q[j].r)-read(Q[j].l-);
j++;
}
}
REP(i,,m)
{
printf("%d\n",ans[i]);
}
}
return ;
}