【AtCoder】ABC 393 F - Prefix LIS Query | 緑コーダーが解くAtCoder

atcoder.jp

配点: 500 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 1284

問題概要
制約
考察
実装例
コメント

問題概要

長さ $N$ の整数列 $A$ が与えられるので、 $Q$ 個のクエリを処理せよ。なお、 $i$ 番目のクエリは以下の通り。

整数 $R_i,X_i$ が与えられる。数列 $(A_1,A_2,\cdots,A_{R_i})$ の部分列であって、狭義単調増加であり、かつ全ての要素が $X_i$ 以下であるようなものの長さの最大値を求めよ。

制約

$1\leq N,Q \leq 2\times 10^5$
$1\leq A_i \leq 10^9$
$1\leq R_i\leq N$
$\min(A_1, A_2,\cdots,A_{R_i})\leq X_i\leq 10^9$
入力は全て整数。

考察

ある数列の部分列であって増加列であるもののうち、その長さが最大のものを最長部分増加列(Longest Increasing Subsequence 、略して LIS)と言う。

LIS は動的計画法によって求められるが、ここではその詳細な実装は扱わないので、以下の記事を参照のこと。

qiita.com

zenn.dev

ところで、動的計画法の際に用いる DP テーブルの定義は以下のものであった。

$\mathrm{dp}_i :=$ 長さ $i+1$ の LIS を作るときの末尾の要素の最小値(存在しなければ $\infty$ )

ここで、クエリを $R_i$ の小さい順に先読みしておき、 $i = 1, 2, \cdots$ と更新しながら、 $\mathrm{dp}_{R_k}$ を更新した時点で、

$\mathrm{dp}_j \leq X_k$ を満たす最大の $j$

を二分探索で求め、それをそのままクエリ $k$ の答えとしてやればよい。

実装においては、 DP テーブルを「 $i+1$ の長さの LIS」で考えているので、 $X_k$ をキーとしたupper_boundを用いればよいだろう。

実装例

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

#define all(x) (x).begin(), (x).end()
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

constexpr long long INFL = 1e+18;

using ll = long long;
using Pair_int = pair<int, int>;

// ======================================== //

int main()
{
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];
    vector<vector<Pair_int>> queries(N);
    rep(i, 0, Q)
    {
        int R, X;
        cin >> R >> X;
        R--;
        queries[R].push_back({X, i});
    }

    vector<int> ans(Q);
    vector<ll> dp(N, INFL);
    rep(i, 0, N)
    {
        auto itr = lower_bound(all(dp), A[i]);
        if (itr == dp.end())
        {
            dp.push_back(A[i]);
        }
        else
        {
            *itr = A[i];
        }

        for (auto &&query : queries[i])
        {
            ans[query.second] = upper_bound(all(dp), query.first) - dp.begin();
        }
    }

    for (auto &&x : ans)
    {
        cout << x << endl;
    }

    return 0;
}