求一段区间内有几段连续的数。。。

考虑从左开始往右扫:

对于数a 如果a+1和a-1都没有那么区间段数加1；如果a+1或a-1中的一个已经在被扫过了，那么区间段数没有增加；

如果a+1和a-1都在，正好把两个数连起来区间段数-1。。

变化总和就是。。。最终的段数。

将询问离线按L排序处理，删除数a的时候，如果与a相邻的数还在后面，那么对应的变化值+1。。。。

数状数组维护即可

Group

1
5 2
3 1 2 5 4
1 5
2 4

1
2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;

const int maxn=110000;

int n,m,a[maxn],tr[maxn],ans[maxn],ntop[maxn];

struct Question
{
	int L,R,id;
}Q[maxn];

bool cmp(Question a,Question b)
{
	if(a.L!=b.L) return a.L<b.L;
	return a.R<b.R;
}

int lowbit(int x)
{
	return x&(-x);
}

void ADD(int p,int v)
{
	for(int i=p;i<maxn;i+=lowbit(i))
		tr[i]+=v;
}

int SUM(int p)
{
	int sum=0;
	for(int i=p;i;i-=lowbit(i))
		sum+=tr[i];
	return sum;
}

int main()
{
	int T_T;
	scanf("%d",&T_T);
	while(T_T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) 
		{
			scanf("%d",a+i);
			ntop[a[i]]=i;
		}
		for(int i=0;i<m;i++)
		{
			Q[i].id=i;
			scanf("%d%d",&Q[i].L,&Q[i].R);
		}
		sort(Q,Q+m,cmp);
		memset(tr,0,sizeof(tr));
		set<int> st;
		///一遍扫过去
		for(int i=1;i<=n;i++)	
		{
			int temp=0,left=st.count(a[i]-1),right=st.count(a[i]+1);
			st.insert(a[i]);
			if(left&&right) temp=-1;
			if(left==0&&right==0) temp=1;
			ADD(i,temp);
		}
		int cur=1;
		for(int i=0;i<m;i++)
		{
			while(cur<Q[i].L)
			{
				if(st.count(a[cur]-1))	ADD(ntop[a[cur]-1],1);
				if(st.count(a[cur]+1))  ADD(ntop[a[cur]+1],1);
				st.erase(a[cur]);
				cur++;
			}
			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;
}

HDOJ 4638 Group,布布扣,bubuko.com

HDOJ 4638 Group

原文：http://blog.csdn.net/ck_boss/article/details/22895881