题干：

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

给定一个长度为N的数组A1, A2, ... AN，请你判断其中有几个元素Ai按如下跳跃规则能跳到最后一个元素AN。  

假设你当前位于Ai，跳跃的规则是：

如果这一步是第奇数次跳跃(从1开始计数)，可以跳到Ai之后(Ai+1 .. AN)比Ai大的最小的元素；

如果这一步是第偶数次跳跃，可以跳到Ai之后(Ai+1 .. AN)比Ai小的最大的元素；

如果有多个满足条件的元素，则跳到其中下标最小的元素。  

如果没有满足条件的元素，则在当前的Ai停下来。  

例如对于A = [3, 2, 4, 1, 5]，如果从3开始，第一步从3跳到4，第二步从4跳到1，第三步从1跳到5。

输入

第一行包含一个整数N。  

第二行包含N个整数A1, A2, ... AN。  

对于30%的数据，1 <= N <= 100  

对于60%的数据，1 <= N <= 1000  

对于100%的数据，1 <= N <= 100000  1 <= Ai <= 1000000

输出

一个整数代表答案

样例输入

5  
3 4 1 2 5

样例输出

4

解题报告：

   先用set倒着扫一遍数组，顺便预处理出距离最近的比他大的最小的数的下标，和距离最近的比他小的最大的数的下标，这一步可以用单调栈O(n)实现，但是因为时间允许于是set好写一些。然后dp代表从编号i开始的第偶数/奇数步，能不能到达最后。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#include<cctype>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e6 + 5;
set<int> ss;
bool dp[MAX][2];
int big[MAX],small[MAX],pos[MAX],a[MAX];//预处理出后面第一个比他大的和第一个比他小的 
int main() {
	int n;
	cin>>n;
	
	for(int i = 1; i<=n; i++) scanf("%d",a+i);
	for(int i = n; i>=1; i--) {
		if(ss.count(a[i])) pos[a[i]] = i;
		else ss.insert(a[i]),pos[a[i]] = i;
		auto it = ss.upper_bound(a[i]);
		if(it != ss.end()) big[i] = pos[*it];
		else big[i] = -1;
		it = ss.lower_bound(a[i]);
		if(it == ss.begin()) small[i] = -1;
		else {
			--it;
			small[i] = pos[*it];
		}
	}
//	for(int i = 1; i<=n; i++ ) {
//		printf("i: %d : %d %d\n",i,big[i],small[i]);
//	}
	dp[n][0] = 1,dp[n][1] = 1;
	for(int i = n-1; i>=1; i--) {
		if(big[i] != -1) dp[i][1] = dp[big[i]][0];
		if(small[i] != -1) dp[i][0] = dp[small[i]][1];
	}
	int ans = 0;
	for(int i = 1; i<=n; i++) {
		if(dp[i][1]) ans++;
	}
	printf("%d\n",ans);
	return 0 ;
	
}

注意因为题中的大于和小于都是严格大于和严格小于，所以判断大于必须用upper，否则可能set中已经有一个a[i]了，，你再lower就肯定不对了。

同样的，也可以用map实现：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+55;
int dp[N][2];
int a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    map<int,int> mp;
    map<int,int> ::iterator it;
    mp[a[n]] = n;
    dp[n][1] = 1;
    dp[n][0] = 1;
    for(int i=n-1;i>0;--i)
    {
        it = mp.lower_bound(a[i]);
        if(it==mp.end()||it==mp.begin()) 
            dp[i][0] = 0;
        else dp[i][0] = dp[(--it)->second][1];
        it = mp.upper_bound(a[i]);
        if(it==mp.end()) dp[i][1] = 0;
        else dp[i][1] = dp[it->second][0];
        mp[a[i]]=i;
    }
    int ans = 0;
    for(int i=1;i<=n;++i)
    {
        if(dp[i][1]) ans++;
    }
    cout<<ans;
    return 0;
}