歸來賽 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;
}