归来赛 kAri-OJ 399 都谁有趣

399. Who Is Joyful

时间限制 3000 ms  内存限制 65536 KB

题目描述

There are several little buddies standing in a line. We say someone is a joyful little buddy, if there exists a little buddy whose height is smaller than him in the front of him and there exists a little buddy whose height is bigger than him in the back of him. Now there are N little buddies, numbered from 1 to N. Their heights h are known. Give you two numbers A and B. Query that in the closed interval whose two ends are A and B, if the joyfulness of the little buddies in the interval have nothing to do with the little buddies out of the interval, how many little buddies are joyful in total in the interval.

输入格式

In the first line there is an integer T (T<=50), indicates the number of test cases. For each case, the first line contains one integer N (1<=N<=1e5). The second line contains N integers hi (1<=hi<=1e9, 1<=i<=N), indicate the heights of the little buddies from the beginning to the end. The third line contains an integer Q (1<=Q<=1e5), indicates the number of queries. And in the following Q lines, each line contains two integers A and B (1<=A, B<=N).

输出格式

For each case, output the case number as shown, and then print the answers to the queries, every query in a single line.

输入样例

2
6
5 2 3 1 4 5
1
2 5
8
1 4 5 5 1 1 3 2
2
3 6
1 3
           

输出样例

Case 1:
1
Case 2:
0
1
           

大概题意：求给定序列，指定区间内，前有小后有大的数字的个数      

思路：若最近的“前大”、“后小”在区间内，则满足要求；否则，则不满足。 所以，用pre[],nex[]记录每个数的最近前驱与后继。      

用Pre[]记录以该数为最近后继的数所在位置，便于对后继是否满足条件做判断。      

先筛选出后继满足条件的点，并对其前继做标记。然后做差，求出区间内前继满足条件的数的个数，即为所求。   利用树状数组记录和计算，降低时间复杂度。      

离线处理：以区间后端点递增为标准对查询排序——因为后继满足较小y，必然也满足较大的y，可利用之前的标记。      

代码：       
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#define maxn 100010
using namespace std;
int a[maxn],pre[maxn],nex[maxn],ans[maxn],sum[maxn];
/*
a——序列；
pre——前方较小且距离最近的位置
nex——后方较大且距离最近的位置 
sum——树状数组
ans——满足要求的数的个数 
*/ 
struct query//储存询问 
{
	int x,y,pos;
	//重载运算符 
	bool operator < (const query k) const
	{
		return ((y<k.y)||(y==k.y&&x<k.x));
	}
};
query qus[maxn];
stack <int> cp;
vector <int> p[maxn];

/*树状数组*/ 
int lowbit(int i)
{
	return i&(-i);
}
void up_date(int a,int b)
{
	if(a==0)
		return;
	while(a<maxn)
	{
		sum[a]+=b;
		a+=lowbit(a);
	}
}
int get_sum(int n)
{
	int Sum=0;
	while(n>0)
	{
		Sum+=sum[n];
		n-=lowbit(n);
	}
	return Sum;
}

main()
{
	int t,n,m,i,j,k;
	scanf("%d",&t);
	for(i=1;i<=t;i++)
	{
		memset(a,0,sizeof(a));
		memset(pre,0,sizeof(pre));
		memset(nex,0,sizeof(nex));
		memset(sum,0,sizeof(sum));
		memset(ans,0,sizeof(ans));
		memset(qus,0,sizeof(qus));
		printf("Case %d:\n",i);
		scanf("%d",&n);
		for(j=1;j<=n;j++)
		{
			scanf("%d",&a[j]);
			p[j].clear();
		}
		scanf("%d",&m);
		for(j=1;j<=m;j++)
		{
			scanf("%d %d",&qus[j].x,&qus[j].y);
			//x,y大小顺序不定 
			if(qus[j].x>qus[j].y)
				swap(qus[j].x,qus[j].y);
			qus[j].pos=j;
		}
		//按照y递增排序 
		sort(qus+1,qus+m+1);
		
		//求算pre[] 
		while(!cp.empty())
			cp.pop();
		for(j=1;j<=n;j++)
		{
			while(!cp.empty()&&a[cp.top()]>=a[j])
				cp.pop();
			if(cp.empty())
				pre[j]=0;
			else 
				pre[j]=cp.top();
			cp.push(j);
		}
		//求算nex[] 
		while(!cp.empty())
			cp.pop();
		for(j=n;j>=1;j--)
		{
			while(!cp.empty()&&a[cp.top()]<=a[j])
				cp.pop();
			if(cp.empty())
				nex[j]=0;
			else 
				nex[j]=cp.top();
			cp.push(j);
		}
		
		//p[i]储存以i为最近后继的节点 
		for(j=1;j<n;j++)
			p[nex[j]].push_back(j);
		
		int r=0;
		for(j=1;j<=m;j++)
		{
			while(r<qus[j].y)//后继满足要求 
			{
				r++;
				for(k=0;k<p[r].size();k++)
				{
					up_date(pre[p[r][k]],1);//对其前继做标记 
				}
			}	
			ans[qus[j].pos]=get_sum(qus[j].y)-get_sum(qus[j].x-1);//前继也满足要求的个数	
		}
		
		for(j=1;j<=m;j++)
			printf("%d\n",ans[j]);
	}
	return 0;
}