题目：
实则为RMQ问题。
主要求出锚点，锚点即为包含区间的两端，包含区间里面的数统一大于起点，且小于终点；或者统一小于起点，且大于重点。
使用ST表进行求解，其中我们需要求出两个ST表，一个用来存储最大值的，一个用来存储最小值的。
我们通过不断递归搜索区间[l,r]，找出区间中的最大值maxPos和最小值minPos的位置，然后划分为三个区间：
如果maxPos>minPos，则三个区间为：
[l,minPos],[minPos,maxPos],[maxPos,r]
如果maxPos<minPos，则三个区间为：
[l,maxPos],[maxPos,minPos],[minPos,r]
然后挑选出锚点。
描述
你正在协助某人开发某种新的 Linux 下的中文字体。
现在需要给上图里的黄点做「位置锚固」，然而有些黄点的位置可以由「插值（IUP）」确定，这样就可以减少锚固的数量。
例如，在上图中，#46 #49 #52 #53 的位置可以由 #42 和 #57 插值得到， 我就不需要去锚固它们，只需要固定 #42 和 #57 就可以了。 可以给这个字减少至少 12 字节 ……
抽象一下问题，现在给出输入数组 a，
定义 ax 可以被 al 和 ar 插值得到为：
存在 l < x < r
使得 al ≤ ax ≤ ar 或者 al ≥ ax ≥ ar。
求最少的「锚固」元素的数目，使得非锚固元素都可以由其左右最靠近它的锚固元素插值得到。并输出锚固元素的下标。
输入
第一行输入一个数 n，表示数组的大小(1 ≤ n ≤ 105)。 接下来的一行，输入一行 n 个整数 a1, a2, …, an，表示数组中的元素(1 ≤ ai ≤ 109)。所有 ai 互不相同。
输出
输出的第一行包含一个整数 ans，表示锚固元素的数目。 接下来一行包含 ans 个递增的整数，表示锚固元素的下标。
提示
额外的样例数据：
| 样例输入 | 样例输出 |
| 7 1 2 3 10 5 6 4 |
3 1 4 7 |
- 样例输入
-
8 3 4 2 1 8 5 7 6
- 样例输出
-
7 1 2 4 5 6 7 8
AC代码：
[c language=”++”]
/*
题目：
实则为RMQ问题。
主要求出锚点，锚点即为包含区间的两端，包含区间里面的数统一大于起点，且小于终点；或者统一小于起点，且大于重点。
使用ST表进行求解，其中我们需要求出两个ST表，一个用来存储最大值的，一个用来存储最小值的。
我们通过不断递归搜索区间[l,r]，找出区间中的最大值maxPos和最小值minPos的位置，然后划分为三个区间：
如果maxPos>minPos，则三个区间为：
[l,minPos],[minPos,maxPos],[maxPos,r]
如果maxPos<minPos，则三个区间为：
[l,maxPos],[maxPos,minPos],[minPos,r]
然后挑选出锚点
*/
//#include<string>
//#include <iomanip>
#include<fstream>
//#include<set>
//#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;
vector<int> preLog2;
//预先计算log2数组，方便后续处理
void calPreLog2(int n,vector<int>&log2)
{
log2[1] = 0;
for (int i = 2; i <= n; i++)
{
log2[i] = log2[i – 1];
//恰好是2的次方
if ((1 << (log2[i] + 1)) == i)
log2[i]++;
}
}
vector<int> arr;
vector<vector<pair<int, int>>> stMin;
vector<vector<pair<int, int>>> stMax;
//准备st表
void ST_Prepare()
{
for (int i = arr.size() – 1; i >= 0; i–)
{
stMin[i][0] = { arr[i], i };
stMax[i][0] = { arr[i], i };
for (int j = 1; i + (1 << j) – 1 < arr.size(); j++)
{
//求min
if (stMin[i][j – 1].first < stMin[i + (1 << (j – 1))][j – 1].first)
stMin[i][j] = stMin[i][j – 1];
else
stMin[i][j] = stMin[i + (1 << (j – 1))][j – 1];
//求max
if (stMax[i][j – 1].first > stMax[i + (1 << (j – 1))][j – 1].first)
stMax[i][j] = stMax[i][j – 1];
else
stMax[i][j] = stMax[i + (1 << (j – 1))][j – 1];
}
}
}
//查询最小值
int queryMin(int l, int r)
{
int len = r – l + 1;
int k = preLog2[len];
if (stMin[l][k].first < stMin[r – (1 << k) + 1][k].first)
return stMin[l][k].second;
else
return stMin[r – (1 << k) + 1][k].second;
}
//查询最大值
int queryMax(int l, int r)
{
int len = r – l + 1;
int k = preLog2[len];
if (stMax[l][k].first > stMax[r – (1 << k) + 1][k].first)
return stMax[l][k].second;
else
return stMax[r – (1 << k) + 1][k].second;
}
map<int,int> ans;
//递归找出包含区间，这些区间的特点是起点和终点分别是最大值和最小值（或最小值和最大值）
void dfs(int l,int r)
{
//求出最大值最小值的位置
int minPos = queryMin(l, r);
int maxPos = queryMax(l, r);
if (l == r)
{//如果左右相等，则压入答案后直接返回
ans[l]=1;
return;
}
//如果最大值和最小值恰好是区间的两端，则压入答案后直接返回
else if ((l == minPos&&r == maxPos) || (l == maxPos &&r == minPos))
{
ans[l] = 1;
ans[r] = 1;
return;
}
//进行递归
dfs(l, min(minPos, maxPos));
dfs(min(minPos, maxPos), max(minPos, maxPos));
dfs(max(minPos, maxPos), r);
}
/*
函数名 ：main
函数功能：主函数
*/
int main(void)
{
int n;
scanf("%d", &n);
arr = vector<int>(n, 0);
for (int i = 0; i < n;i++)
{
scanf("%d", &arr[i]);
}
preLog2 = vector<int>(n+1, 0);
stMin = vector<vector<pair<int, int>>>(n, vector<pair<int, int>>(32, { 0, 0 }));
stMax = vector<vector<pair<int, int>>>(n, vector<pair<int, int>>(32, { 0, 0 }));
//预处理求出log2，log2向下取整
calPreLog2(n, preLog2);
//预处理stTable，包括最大值和最小值
ST_Prepare();
//进行递归搜索
dfs(0, n – 1);
printf("%d\n", ans.size());
for (map<int, int>::iterator ite = ans.begin(); ite != ans.end(); ite++)
{
printf("%d ", ite->first + 1);
}
printf("\n");
return 0;
}
[/c]