hdu 4638 Group

2016-02-17 · 2 min read · 分块莫队算法

http://acm.hdu.edu.cn/showproblem.php?pid=4638 题意：给定一个序列，序列由1-N个元素全排列而成，求任意区间连续的段数。例如序列2,3,5,6,9就是三段(2, 3) (5, 6)(9)。思路：增加一个元素，如果它两边的元素都出现了，那么段数-1（相当于把两段连接起来合并成了一段），如果两边元素都没有出现，那么段数+1.反过来，减少一个元素时，如果两边元素都出现了，俺么段数+1（相当于把完整的一段断开成两段），如果两边元素都没有出现，那么段数-1.操作可以O(1)完成。。。上莫队。因为id大小最大才100000，所以判断某个元素是否出现开一个100000大小的布尔数组即可（我竟然傻逼得去用set....然后华丽丽得TLE了2333）

/* ***********************************************
Author :111qqz
Created Time :2016年02月18日 星期四 03时03分48秒
File Name :code/hdu/4638.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=1E5+7;
 7int n,m;
 8int pos[N];
 9int a[N];
10int ans[N];
11int sum;
12bool vis[N];

1struct node
2{
3    int l,r;
4    int id;

1    bool operator <(node b)const
2    {
3	if (pos[l]==pos[b.l]) return r<b.r;
4	return pos[l]<pos[b.l];
5    }
6}q[N];

void update( int x,int d)
{

1   // cout<<"cnt1:"<<cnt1<<" cnt2:"<<cnt2<<endl;
2    if (d>0)
3    {
4	if (vis[a[x]-1]&&vis[a[x]+1])
5	    sum--;
6	if (!vis[a[x]-1]&&!vis[a[x]+1])
7	    sum++;

 1	vis[a[x]] = true;
 2    }
 3    else
 4    {
 5	if (vis[a[x]-1]&&vis[a[x]+1]) sum++;
 6	if (!vis[a[x]-1]&&!vis[a[x]+1])sum--;
 7	vis[a[x]] = false;
 8    }
 9}
10int main()
11{
12	#ifndef  ONLINE_JUDGE 
13	freopen("code/in.txt","r",stdin);
14  #endif
15	int T;
16	cin>>T;
17	while (T--)
18	{
19	    ms(ans,0);
20	    ms(vis,false);
21	    scanf("%d %d",&n,&m);
22	    int siz = 316; //sqrt(100000)
23	    for ( int  i = 1 ; i  <= n ; i++)
24	    {
25		scanf("%d",&a[i]);
26		pos[i] = (i-1)/siz;
27	    }

1	    for ( int i =1 ; i <= m ; i++)
2	    {
3		scanf("%d %d",&q[i].l,&q[i].r);
4		q[i].id = i;
5	    }
6	    sort(q+1,q+m+1);
7//	    for ( int i = 1 ; i <= m ; i++) cout<<q[i].l<<" "<<q[i].r<<endl;

1	    int pl=1,pr=0;
2	    int id,l,r;
3	    sum = 0 ;
4	    for ( int i = 1 ; i <= m ; i++)
5	    {
6		id = q[i].id;
7		l = q[i].l;
8		r = q[i].r;

1		if (pr<r)
2		{
3		    for ( int j = pr +1 ; j <= r ; j++) update(j,1);
4		}
5		else
6		{
7		    for ( int j = r + 1 ; j <= pr ; j++) update(j,-1);
8		}
9		pr = r;

1		if (l<pl)
2		{
3		    for ( int j = l ; j <= pl-1 ; j++) update(j,1);
4		}
5		else
6		{
7		    for ( int j = pl ; j <= l-1 ; j++) update(j,-1);
8		}
9		pl = l;

		ans[id]=sum;
	    }
	    
	    for ( int i = 1 ; i  <= m ; i++) printf("%d\n",ans[i]);
	}

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}