ECR152-E Max to the Right of Min

問題

https://codeforces.com/contest/1849/problem/E (diff 2300)

長さの順列が与えられます。以下の条件を満たすの連続部分列の数を求めてください

• 最小値を取る場所が最大値を取る場所より真に左にある

制約

• 

解法

右端を固定して考える。

を後ろから累積min, 累積maxを取り、その最小値を更新する添字と最大値を更新する添字を観察する。

一回最小値を更新した添字から、以後に最大値を更新する添字について、左端をとするとは条件を満たす。

最小値、最大値を更新する添字の管理はstackで全体でできて( 参考 )、寄与の値も連結リストやsetで適宜管理できる。

実装がかったるい

実装

#include <bits/stdc++.h>

#include "Src/Template/IOSetting.hpp"
using namespace zawa;

int main() {
    SetFastIO();

    int n;
    std::cin >> n;
    std::vector<int> p(n);
    for (auto& x : p) std::cin >> x;
    // int brute_sol{};
    // {
    //     std::mt19937 mt{std::random_device{}()};
    //     std::iota(p.begin(), p.end(), 0);
    //     std::shuffle(p.begin(), p.end(), mt);
    //     int cnt{};
    //     for (int L{} ; L < n ; L++) {
    //         for (int R{L + 1} ; R <= n ; R++) {
    //             int min{L + (int)std::distance(p.begin() + L, std::min_element(p.begin() + L, p.begin() + R))};
    //             int max{L + (int)std::distance(p.begin() + L, std::max_element(p.begin() + L, p.begin() + R))};
    //             if (min < max) cnt++;
    //         }
    //     }
    //     for (auto x : p) std::cout << x + 1 << ' ';
    //     std::cout << std::endl;
    // }
    std::set<std::pair<int, int>> set;
    std::stack<int> stack_m, stack_M;
    long long ans{}, cur{};
    for (int i{} ; i < n ; i++) {
        while (stack_m.size() and p[i] < p[stack_m.top()]) {
            auto it{set.find({ stack_m.top(), 1 })}; 
            assert(it != set.end());
            if (it == set.begin()) {
                cur -= it->first + 1;
            }
            else {
                cur -= it->first - std::prev(it)->first;
            }
            set.erase(it);
            stack_m.pop();
        }
        while (stack_M.size() and p[i] > p[stack_M.top()]) {
            auto it{set.find({ stack_M.top(), 0 })};
            assert(it != set.end());
            if (std::next(it) != set.end()) {
                assert(std::next(it)->second == 1);
                cur -= std::next(it)->first - it->first;
                if (it != set.begin()) {
                    cur += std::next(it)->first - std::prev(it)->first;
                }
                else {
                    cur += std::next(it)->first + 1;
                }
            }
            set.erase(it);
            stack_M.pop();
        }
        set.insert({ i, 0 });
        set.insert({ i, 1 });
        stack_m.push(i);
        stack_M.push(i);
        ans += cur;
        // for (auto [x, j] : set) std::cout << '(' << p[x] << ',' << (j ? 'm' : 'M') << ')' << ' ';
        // std::cout << cur << std::endl;
    }
    std::cout << ans << '\n';
}

感想

• バチャ中には1h以上ありながらも解けず、解説AC
• stackで自分より真に大きい次の要素、前の要素を得るテクを「monotonic stack」と呼ぶらしい。名前は初めて聞いたが、テク自体は蟻本のヒストグラム最大化の問題で紹介されているようだ。