B. New Year and Ascent Sequence (Codeforces Hello 2020)

問題

https://codeforces.com/contest/1284/problem/B

問題概要

長さlの数値の配列a = [a1, a2,..., al]を考えたとき、1 <= i < j <= l かつ ai < ajを満たす要素が存在する場合、配列aは「ascentを持つ」と呼ぶことにする。

二つの配列を順序を入れ替えずに並べてできる新しい配列を「連結された配列」と呼ぶことにする。例えばa = [0, 1, 2]とb = [9, 8, 7, 6]を連結すると[0, 1, 2, 9, 8, 7, 6]となる。

異なる長さのn個の数値の配列が与えられる。この配列のペア'n²'すべての組み合わせ（順序あり、重複あり）を考えたとき、連結された配列が「ascentを持つ」場合はいくつあるか。

解説

まず、配列単体でascentを持つ配列は、連結された配列となった場合でも必ずascentを持ちます。単体でascentを持つ配列が含まれるペアの数は、n^2 - (単体でascentを持たない配列の数)^2となります。

あとは、単体でascentを持たない配列どうしを連結した時、ascentを持つ配列になる場合がいくつあるかを数えればよいです。これは、前の配列のmin < 後の配列のmaxとなる組み合わせの個数を考えればよいです。なので、ascentを持たない配列のminとmaxをそれぞれ配列で持って、各minに対してより大きくなるmaxがいくつ存在するかを調べていけば求めることができます。ここで、すべての値を順次確認していくと最悪O(n^2)となり間に合いませんが、maxをソートして二分法を使用すればlogに落とすことができて間に合わせることができます。

#include <bits/stdc++.h>
using namespace std;

template<typename D> class BinarySearchR {
    D left;
    D right;
    function<bool(D)> func;
 
    public:
        BinarySearchR(D l, D r, function<bool(D)> f) {
            left = l;
            right = r;
            func = f;
        }
 
        D calc() {
            while (abs(right - left) > 1) {
                D m = (left + right) / 2;
                if (func(m)) {
                    right = m;
                } else {
                    left = m;
                }
            }
            return right;
        }
};
 
int main() {
    int n;
    cin >> n;
    vector<int> mn;
    vector<int> mx;
    int c = 0;
    for (int i = 0; i < n; i++) {
        int l;
        cin >> l;
        int p_min = 1000000001;
        int p_max = 0;
        bool ok = false;
        for (int j = 0; j < l; j++) {
            int a;
            cin >> a;
            if (p_min < a) {
                c++;
                ok = true;
            }
            p_min = min(p_min, a);
            p_max = max(p_max, a);
        }
        if (!ok) {
            mn.emplace_back(p_min);
            mx.emplace_back(p_max);
        }
    }
    sort(mx.begin(), mx.end());
    int u = mn.size();
    long long ans = (long long)n * n - (long long)u * u; 
    for (int i = 0; i < u; i++) {
        function<bool(int)> f = [&](int m) {
            if (mx[m] > mn[i]) return true;
            else return false;
        };
        BinarySearchR<int> bs(-1, u, f);
        ans += (long long)u - bs.calc();
    }
    cout << ans << endl;
}