题意
找到区间里有多少组连续数字串
分析：
（转）思路：显然，我们要使得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+100; 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=0; while(x>0) { 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,1,n){ scanf("%d",&A[i]); pos[A[i]]=i; } Q.clear(); node tmp; REP(i,1,m) { scanf("%d%d",&tmp.l,&tmp.r); tmp.index=i; Q.push_back(tmp); } sort(Q.begin(),Q.end()); CL(tree,0); int j=0; for(int i=1;i<=n;i++) { add(i,1); if(A[i]+1<=n&&pos[A[i]+1]<i) { add(pos[A[i]+1],-1); } if(A[i]-1>=1&&pos[A[i]-1]<i) { add(pos[A[i]-1],-1); } while(Q[j].r==i) { ans[Q[j].index]=read(Q[j].r)-read(Q[j].l-1); j++; } } REP(i,1,m) { printf("%d ",ans[i]); } } return 0; }