LIS ( Longest Increasing SubSequence )

ABC134-Eが解けない。解いている途中。 E - Sequence Decomposing

解説ではLIS（最長増加部分列）と同等のものを調べることでACできるとある。
LISは結構前に1度、かなり苦労して解けたのだけど解けなくなっていたので復習しないといけない。
てことで他の方のコードを見ていたら面白い解答があったので載せてみる。

Submission #6447713 - AtCoder Beginner Contest 134

何か要素数が大きい数列を構築するようなとき、追加と消去を繰り返すようなやり方では遅くなる傾向があって、その対策でLISでは2次元配列等に計算結果を記録していくのだと思っていたが通る場合もあるのか。(大抵vectorとかで作ったときの記憶なので遅いのは仕方ない)

でも考えてみると * erase ... O(1) * lower_bound/upper_bound ... O( log2 (ms.size()) ) * emplace/insert ... O(log (ms.size()) ) ?

なのでせいぜい O(N * log N) くらいなんだろうか。 それだと通りそう。解説もO(N logN)だ。 とりあえず O(N²)だと10¹⁰回ループしてTLEするので、それ以下に落とさないといけないのは分かる。

https://wandbox.org/permlink/uYEAlfaUcGHYNoNI

#include<iostream>
#include<set>
#include<algorithm>
#include<cstddef>
#include<vector>
#include<iterator>

using ui32 = std::uint32_t;
using ui64 = std::uint64_t;

//
//Longest Incresing SubSequence
//By multiset
int main(){
    ui32 n;
    std::cin >> n;


    std::vector<ui32> an(n);
    
    for( auto& e : an )
        std::cin >> e;


    auto solve1 = [&]()
    {
        std::multiset<ui32, std::greater<>> ms;
        // a1 > a2 > a3 > ...;
        auto p = [&]( auto it_ )
        {

            std::cout << "*it = ";
            if( it_ == std::end( ms ) )
                std::cout << "null";
            else
                std::cout << *it_;

            std::cout << ";\t";

            std::cout << "size = " << ms.size() << ";\t";

            std::cout << "ms:";
            for( auto e : ms )
                std::cout << e << " ";
            std::cout << "\n";
        };



        for( const auto e : an )
        {
            //upper_boundは最初に登場する e より大きい値のイテレータを返す
            //したがって x1 < x2 が成り立つ部分列をmsが構築していくことになる
            const auto it = ms.upper_bound( e );
            p(it );


            //最大値でないなら消す。
            //つまり max(ms) < e を満たす e の場合だけ ms.size() は増加する
            if( it != ms.begin() )
                ms.erase( std::prev( it ) );

            ms.emplace( e );
        }

        p( std::end( ms ) );

        std::cout << "LIS:" << ms.size() << "\n";
    };


    auto solve2 = [&]()
    {
        std::multiset<ui32> ms;
        // a1 < a2 < a3 <...
        auto p = [&](auto it_ ) {
            if( it_ == std::end( ms ) )
                std::cout << "null";
            else
                std::cout << *it_;

            std::cout << "\tsize = " << ms.size();
            
            std::cout << "\tms:";
            for( const auto e : ms )
                std::cout << e << " ";
            std::cout << "\n";

        };

        for( const auto e : an )
        {
            const auto it = ms.upper_bound( e );
            p( it );
            if( it != std::end( ms ) )
                ms.erase( it );

            ms.emplace( e );
            
        }

        p( std::end(ms) );

        std::cout << "LIS = " << ms.size() << "\n";

    };

    solve2();

    return 0;
}