ABC393-F Prefix LIS Query

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5 3");
            WillReturn.Add("2 4 1 3 3");
            WillReturn.Add("2 5");
            WillReturn.Add("5 2");
            WillReturn.Add("5 3");
            //2
            //1
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 8");
            WillReturn.Add("2 5 6 5 2 1 7 9 7 2");
            WillReturn.Add("7 8");
            WillReturn.Add("5 2");
            WillReturn.Add("2 3");
            WillReturn.Add("2 6");
            WillReturn.Add("7 3");
            WillReturn.Add("8 9");
            WillReturn.Add("9 6");
            WillReturn.Add("8 7");
            //4
            //1
            //1
            //2
            //1
            //5
            //3
            //4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    class QueryDef
    {
        internal long Time;
        internal long R;
        internal long X;
        internal long? Answer;
    }
    static List<QueryDef> mQueryList = new List<QueryDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            var WillAdd = new QueryDef();
            WillAdd.Time = mQueryList.Count();
            WillAdd.R = wkArr[0] - 1;
            WillAdd.X = wkArr[1];
            WillAdd.Answer = null;
            mQueryList.Add(WillAdd);
        }

        mQueryList = mQueryList.OrderBy(pX => pX.R).ToList();

        // LISの最終値の最小値[LISの長さ] なDP表
        var DPSortedList = new SortedList<long, long>();

        int CurrQueryInd = 0;

        for (long I = 0; I <= AArr.GetUpperBound(0); I++) {
            long EachA = AArr[I];

            if (DPSortedList.Count == 0) {
                DPSortedList[1] = EachA;
            }
            else {
                long UpsertKeyInd = ExecNibunhou(DPSortedList, EachA);

                long CurrUB = DPSortedList.Count - 1;
                var Keys = DPSortedList.Keys;

                // 更新する位置によって分岐
                if (UpsertKeyInd <= CurrUB) {
                    DPSortedList[Keys[(int)UpsertKeyInd]] = EachA;
                }
                else {
                    long PrevKey = Keys[(int)CurrUB];
                    DPSortedList[PrevKey + 1] = EachA;
                }
            }

            // クエリに解を設定
            while (true) {
                if (CurrQueryInd <= mQueryList.Count - 1) {
                    var CurrQuery = mQueryList[CurrQueryInd];
                    if (CurrQuery.R == I) {
                        int ResultInd = ExecNibunhou_LowerOrEqual_Max(CurrQuery.X, DPSortedList);
                        if (ResultInd == -1) {
                            CurrQuery.Answer = 0;
                        }
                        else {
                            CurrQuery.Answer = ResultInd;
                        }
                        CurrQueryInd++;
                        continue;
                    }
                }
                break;
            }
        }

        foreach (QueryDef EachQuery in mQueryList.OrderBy(pX => pX.Time)) {
            Console.WriteLine(EachQuery.Answer);
        }
    }

    // 二分法で、Val以下で最大の値を持つ、キーを返す(LISのSortedList用)
    static int ExecNibunhou_LowerOrEqual_Max(long pVal, SortedList<long, long> pDPSortedList)
    {
        if (pDPSortedList.Count == 0) return -1;
        var Keys = pDPSortedList.Keys;
        int UB = pDPSortedList.Count;

        // 最後の要素がVal以下の特殊ケース
        if (pVal >= pDPSortedList[UB]) {
            return UB;
        }
        // 最初の要素がVal超えの特殊ケース
        if (pVal < pDPSortedList[1]) {
            return -1;
        }

        int L = 1;
        int R = UB;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            if (pDPSortedList[Mid] <= pVal) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }

    // 二分法で、引数の値を設定する、キーの配列の添字を返す
    static long ExecNibunhou(SortedList<long, long> pDPSortedList, long pTargetVal)
    {
        long UB = pDPSortedList.Count - 1;
        var Keys = pDPSortedList.Keys;

        // 最小値以下の場合
        if (pTargetVal <= pDPSortedList[Keys[0]]) {
            return 0;
        }

        // 最大値より大きい場合
        if (pTargetVal > pDPSortedList[Keys[(int)UB]]) {
            return UB + 1;
        }

        long L = 0;
        long R = UB;

        while (L + 1 < R) {
            long Mid = (L + R) / 2;
            if (pDPSortedList[Keys[(int)Mid]] < pTargetVal) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return R;
    }
}

解説

LISを求めるDPで使用する、
LISの最終値の最小値[LISの長さ] なDP表
は、狭義単調増加になるので、
クエリを先読みし、
解を二分探索で設定してます。