Educational Codeforces Round 152 (Rated for Div. 2)

Max to the Right of Min

算法本质

思维++、单调栈

题目大意

给定排列p[]，定义[l, r]为合法区间：

• p[l~r]的最大值下标 > p[l~r]的最小值下标

输出合法区间数。

n <= 1e6

思路推演

这样的题，朴素思想一来有两种：

• 固定区间左端点，枚举右端点
• 固定区间最大值，枚举最小值

至于具体固定左还是右，大还是小，本质上是一样的

第一种方式，区间内的最值变化严重，无规律可言，直接放弃。
相比而言，第二种方式可以把合法区间有条理分类去找。

假设找以p[i]为最大值的合法区间，然后这天然就存在的限制是：区间内不能有>p[i]的值，这个由p[i]最大值引起的限制可以用单调栈来搞定。
随后枚举<i的下标，找合法区间的最小值。

通过数次模拟可以发现，左边可行的合法区间最小值，是一个单调递减的形式，其下标用j表示。
用lmin[] lmax[] rmin[] rmax[]表示某个元素左右方向第一个大于、小于其的值的下标。
每个合法区间，将其范围缩减至区间最值暴露于左右两端，用[j, i]表示——即对于a[j]为最小值、a[i]为最大值的合法区间的数目为：$(j-\max(lmin[j], lmax[i]))*(min(rmin[j], rmax[i])-i)$

不过显然，最坏情况这样的复杂度为O(n^2^)，复杂度不支持，思考优化。

可以发现的是，如果枚举最大值下标i是从左往右枚举时，由于最小值在左的规则，i+1作为最大值下标找的合法区间最小值下标与i相同的地方许多，也许可以做些预处理来。而且由于这些最小值下标j从左往右是递增的，所以其rmin[]值也是递减的，而在上面可以公式可以看到，这个公式最大的问题就是max min值的分割处理（才能进行整体特征合并优化），而rmin值递增为公式右侧部分提供了分割处理的基础。
公式左侧部分，可以通过lmin[j]的值来寻找可行的最小值下标。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
a[maxn];
inline void solve()
{
    cin>>n;
    rep(i,1,n)    cin>>a[i];
    ddz(a, n);
    vector<int> s, sum;
    int ans=0;
    for (int i=1; i<=n; i++)
    {
        while (s.size() && a[s.back()]>a[i])    // s[]维护的是一个递增、且全部<a[i]的下标数组
        {
            s.pop_back();
            sum.pop_back();
        }
        // 保证a[i]为最大值的合法区间中，s[l]是最靠左的合法区间最小值下标！（这里比较重要，画图理解）
        int l=upper_bound(s.begin(), s.end(), lmax[i]) - s.begin();
        if (l < s.size())    // 存在这样的值
        {
            int j=s[l];        // j为合法区间最小值下标（以a[i]为最大值、最左边的下标）
            ans += (j-lmax[i]) * (min(rmin[j], rmax[i]) - i);    // 按照公式计算[j,i]的可达合法区间数
            l++;    // 接下来的s[l]不再是最左边的最小值下标，所以公式的左侧取`lmin[j]`而不是`lmax[i]`，同时lmin[j]可以很好的合并
            // 上面这几步代码，实际上已经将公式左侧的情况分开讨论了，随后也讨论右侧的情况
            int r=partition_point(s.begin()+l, s.end(), [&](int x) {    
                return rmin[x] > rmax[i];
            }) - s.begin();        // 找到s[]中第一个rmin[?]<=rmax[i]的下标
            ans += (s[r-1] - s[l-1]) * rmax[i];        // 这部分区间，公式左侧取`lmin[j]`，公式右侧取`rmax[i]`
            ans += sum.back() - sum[r-1];    // 这部分用前缀和处理，具体看sum那的处理
            ans -= (s.back() - s[l-1]) * i;
        }
        int pre = sum.size() ? sum.back() : 0;
        int last = s.size() ? s.back() : 0;
        sum.push_back(pre + (i-last) * rmin[i]);    // 预处理一部分，画图理解
        s.push_back(i);
    }
    cout<<ans<<endl;
    return;
}

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。