20220609学习记录（st表、动态规划、数学）

G-ACM is all you need

因为是对所有的函数值进行，所以后面的b其实不重要，重要的是看绝对值里面的部分。

找到每三个点当中最中间的点不是局部最小点的b的区间范围，其实就是计算a[i]到b的距离。

三个点是低中高三者的排列组合，一共有6种情况。如果连续的两个点高度相等，那么它们绝对不会是局部最小点，所以不用计算在内。

例如三个点是 左高中中右低 这种情况，那么此时b的选择范围有两个，分别是 到 （加1是因为b是整数，而且保证中间不是局部最小）和 到 。

但这六种情况可以通过min和max合并成3种情况，如代码所示。

现在有很多区间，要计算区间覆盖最多的数。如下图所示，区间的左端点记为+1，右端点的下一个点记为-1，如此每个点从小到大顺下去加减，这样就能求出每个点被区间覆盖的次数。

用map实现。

 可以看到，本来是局部最小点的区间都是x到正无穷，其他两种本来就不是局部极小值的点都是有负无穷到x的。

于是在计算的时候，设本来就是局部极小的点有ans个，区间覆盖的最大次数为sum。

如果取到的这个b刚好让一个不是局部极小的点p变成局部极小了，那么这个sum肯定会先对点p这个区间右端点减去1了。所以最终的答案是ans-sum。

代码：（当然还有一种解法是找出中间的点是局部极小点的区间，然后求区间覆盖的最少，但这里不做了）

#include
using namespace std;
int a[100005];
map mp;
int main()
{
 int T;cin>>T;
    while(T--){
        mp.clear();
        int n;cin>>n;int ans=0;
        for(int i=1;i<=n;i++){cin>>a[i];}
        for(int i=2;i<=n-1;i++){
            if(a[i]a[i+1]&&a[i]>a[i-1]){//防止转换后，中间的点变小了
                int r=(a[i]+max(a[i-1],a[i+1]))/2;//到无限小
                mp[r+1]--;//--方面一定是+1后计算的
            }
            else if(a[i]>a[i+1]&&a[i]a[i-1]){
                //防止转换后，中间的点变小了
                int l=(a[i]+max(a[i-1],a[i+1])+1)/2;//到无限大
                mp[l]++;
                int r=(a[i]+min(a[i-1],a[i+1]))/2;//到无限小
                mp[r+1]--;
            }
        }int res=0,sum=0,a=0;
        for(auto i:mp){res+=i.second;sum=max(sum,res);}
        cout<