526互联

Educational Codeforces Round 152 (Rated for Div. 2)E. Max to the Right of Min（数据结构，分治）

发布时间 2023-08-27 19:54:32作者: XiCen

题目链接：https://codeforces.com/problemset/problem/1849/E

 

大致题意：

 

长度为n的序列，求有多少个区间满足区间最大值在区间最小值的右边？

 

解题思路：

 

（此题有使用线段树等其他做法，本处使用的是单调栈做法）

 

我们先求出每个a【i】 的左边的比他小的LMIN，左边比他大的LMAX，右边比他大的RMAX，右边比他小的RMIN；

 

我们枚举每个a【i】为最大值，此刻以他为最大值的区间为，L= LMAX【i】，R = RMAX【i】；

 

1：枚举k从 i 到 L+1 ：

 

以k为左端点的时候，比 k 到 i 中的数都  小的 数在 x 的时候，

　　a: x < i，那么答案增加 i - x

　　b：x > R时，答案增加R - i

其他时候答案不增加

 

2：枚举k从i 到R-1；

 

以k为右端点的时候，比i到k中的数都小的数在x的时候，

　　如果x大于L，那么答案增加x-L

其他时候答案都不增加

 

以上结论都是比较显然的，读者可以思考一下就推出；

 

复杂度的话，我们将俩种情况结合起来，也就是，如果 i - L < R - i，那么使用第一种情况，否则使用第二种情况；

我们思考区间最大值从大到小来看，每个区间扫描都会不大于之前那个区间的一半；

 

故时间复杂度：O（nlogn）；

 

代码：

#include<bits/stdc++.h>

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);

    int n; std::cin >> n;

    std::vector<int> a(n + 1, 0);

    std::vector<int> LMIN(n + 1, 0), LMAX(n + 1, 0), RMIN(n + 1, n + 1), RMAX(n + 1, n + 1);

    for (int i = 1; i <= n; ++i)std::cin >> a[i];

    std::stack<int> st;

    for (int i = 1; i <= n; ++i)
    {
        while (st.size() && a[st.top()] > a[i])RMIN[st.top()] = i, st.pop();
        st.push(i);
    }
    while (st.size())st.pop();

    for (int i = 1; i <= n; ++i)
    {
        while (st.size() && a[st.top()] < a[i])RMAX[st.top()] = i, st.pop();
        st.push(i);
    }
    while (st.size())st.pop();

    for (int i = n; i >= 1; --i)
    {
        while (st.size() && a[st.top()] > a[i])LMIN[st.top()] = i, st.pop();
        st.push(i);
    }
    while (st.size())st.pop();

    for (int i = n; i >= 1; -- i)
    {
        while (st.size() && a[st.top()] < a[i])LMAX[st.top()] = i, st.pop();
        st.push(i);
    }
    while (st.size())st.pop();

    //for (int i = 1; i <= n; ++i)std::cout << LMIN[i] << " \n"[i == n];
    //for (int i = 1; i <= n; ++i)std::cout << LMAX[i] << " \n"[i == n];
    //for (int i = 1; i <= n; ++i)std::cout << RMIN[i] << " \n"[i == n];
    //for (int i = 1; i <= n; ++i)std::cout << RMAX[i] << " \n"[i == n];

    long long ans = 0;

    for (int i = 1; i <= n; ++i)
    {
        int L = LMAX[i], R = RMAX[i];

        if (i - L < R - i)
        {
            int mi = RMIN[i], I = i;
            for (int j = i; j > L; --j)
            {
                if (a[j] < a[I])I = j;
                mi = RMIN[I];
                if (mi >= R)ans += R - i - (i == j);
                else if (mi > i)ans += mi - i - (i == j);
            }
        }
        else
        {
            int mi = LMIN[i], I = i;
            for (int j = i; j < R; ++j)
            {
                if (a[j] < a[I])I = j;
                mi = LMIN[I];
                if (mi > L)ans += mi - L;
                //std::cout << mi << " " << L << "\n";
            }
        }
        //std::cout << ans << "\n";
    }

    std::cout << ans << "\n";

    return 0;
}

其实说难也不是很难，就是需要考虑的有些细：）