HDU - 4638 Group(经典莫队 - 求区间连续数字集的个数)

Group

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4580 Accepted Submission(s): 2095

Problem Description
There are n men ,every man has an ID(1…n).their ID is unique. Whose ID is i and i-1 are friends, Whose ID is i and i+1 are friends. These n men stand in line. Now we select an interval of men to make some group. K men in a group can create K*K value. The value of an interval is sum of these value of groups. The people of same group’s id must be continuous. Now we chose an interval of men and want to know there should be how many groups so the value of interval is max.

Input
First line is T indicate the case number.
For each case first line is n, m(1<=n ,m<=100000) indicate there are n men and m query.
Then a line have n number indicate the ID of men from left to right.
Next m line each line has two number L,R(1<=L<=R<=n),mean we want to know the answer of [L,R].

Output
For every query output a number indicate there should be how many group so that the sum of value is max.

Sample Input
1
5 2
3 1 2 5 4
1 5
2 4

Sample Output
1
2

Source
2013 Multi-University Training Contest 4

一般看到此类题目，我们可以首先想到离线莫队。然后我们就可以考虑区间转移了。

比如当前我们已知区间 [ L , R ] 的连续数字的个数了，怎么转移呢？

增加元素：我们可以看当前数字的两边，若全部都有数字，并且当前位置没有数字，那么我们加入这个数字之后，必然使得两个连续的数字集连了起来，所以答案减一；若只有一边有，则不变；若都没有，那么就相当于新开了一个连续数字集，所以答案加一；
删除元素：考虑思路和增加元素类似。

但是，同时我们要注意当前的查询区间和我们莫队的左右指针没有交集时，我们应该暴力修改过去（特判）。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int T,n,m,bl,a[N],vis[N],res[N],cnt,cl,cr;
struct node{
	int l,r,id;
}t[N];
int cmp(const node &s1,const node &s2){
	return (s1.l/bl==s2.l/bl)?(s1.r<s2.r):(s1.l<s2.l);
}
inline void add(int x){
	if(vis[a[x]])	return ;
	if(vis[a[x]-1]&&vis[a[x]+1])	cnt--;
	else if(!vis[a[x]-1]&&!vis[a[x]+1])	cnt++;
	vis[a[x]]=1;
}
inline void del(int x){
	if(!vis[a[x]])	return ;
	if(vis[a[x]-1]&&vis[a[x]+1])	cnt++;
	else if(!vis[a[x]-1]&&!vis[a[x]+1])	cnt--;
	vis[a[x]]=0;
}
signed main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d %d",&n,&m);	memset(vis,0,sizeof vis);	bl=sqrt(n);
		for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
		for(int i=1;i<=m;i++)	scanf("%d %d",&t[i].l,&t[i].r),t[i].id=i;
		sort(t+1,t+1+m,cmp);	cl=1,cr=cnt=0;
		for(int i=1;i<=m;i++){
			int L=t[i].l;	int R=t[i].r;
			if(cl>R||cr<L){
				while(cl<=cr)	vis[a[cl++]]=0;
				cnt=0;	cl=t[i].l;	cr=t[i].l-1;
				while(cr<R)	add(++cr);
				res[t[i].id]=cnt;	continue;
			}
			while(cl<L)	del(cl++);
			while(cl>L)	add(--cl);
			while(cr>R)	del(cr--);
			while(cr<R)	add(++cr);
			res[t[i].id]=cnt;
		}
		for(int i=1;i<=m;i++)	printf("%d\n",res[i]);
	}
	return 0;
}