A10 Resort Hotel

問題へのリンク

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("7");
            WillReturn.Add("1 2 5 5 2 3 1");
            WillReturn.Add("2");
            WillReturn.Add("3 5");
            WillReturn.Add("4 6");
            //3
            //5
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        var InsSparseTable = new SparseTable<int>(AArr, false);

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

        foreach (string EachStr in InputList.Skip(3)) {
            SplitAct(EachStr);
            int L = wkArr[0] - 1;
            int R = wkArr[1] - 1;

            var AnswerKouho = new List<int>();

            if (L > 0) {
                int RangeSta = 0;
                int RangeEnd = L - 1;
                int MaxVal = InsSparseTable.Query(RangeSta, RangeEnd);
                AnswerKouho.Add(MaxVal);
            }

            if (R < UB) {
                int RangeSta = R + 1;
                int RangeEnd = UB;
                int MaxVal = InsSparseTable.Query(RangeSta, RangeEnd);
                AnswerKouho.Add(MaxVal);
            }
            Console.WriteLine(AnswerKouho.Max());
        }
    }
}

#region SparseTable
internal class SparseTable<Type> where Type : IComparable<Type>
{
    // 最小値か最大値[2の指数][開始Ind]なArr
    private Type[][] mMinOrMaxJagArr;

    // Log2の値[2べき値] なDict
    private Dictionary<long, long> mLogDict = new Dictionary<long, long>();

    // 対応する2べき値[クエリの区間長]
    private long[] mBeki2Arr;

    // 最小値を取得するか？
    private bool mIsMin = false;

    // コンストラクタ1(配列が引数)
    internal SparseTable(Type[] pInitArr, bool pIsMin)
    {
        mIsMin = pIsMin;

        long Sisuu = 0;
        long Beki2 = 1;
        while (true) {
            mLogDict[Beki2] = Sisuu;
            Beki2 *= 2;

            if (Beki2 > pInitArr.Length) {
                break;
            }
            Sisuu++;
        }

        mMinOrMaxJagArr = new Type[Sisuu + 1][];
        foreach (var EachPair in mLogDict) {
            long CurrBeki2 = EachPair.Key;
            long CurrSisuu = EachPair.Value;
            long CurrUB = pInitArr.GetUpperBound(0) - CurrBeki2 + 1;
            mMinOrMaxJagArr[CurrSisuu] = new Type[CurrUB + 1];
        }

        // 長さ1の分を初期化
        for (long I = 0; I <= pInitArr.GetUpperBound(0); I++) {
            mMinOrMaxJagArr[0][I] = pInitArr[I];
        }

        // コンストラクタのヘルパメソッド
        ConstructorHelper();

        // 対応する2べき値[クエリの区間長]を設定
        SetBeki2Arr(pInitArr.Length);
    }

    // コンストラクタ2(Listが引数)
    internal SparseTable(List<Type> pInitList, bool pIsMin)
    {
        mIsMin = pIsMin;

        long Sisuu = 0;
        long Beki2 = 1;
        while (true) {
            mLogDict[Beki2] = Sisuu;
            Beki2 *= 2;

            if (Beki2 > pInitList.Count) {
                break;
            }
            Sisuu++;
        }

        mMinOrMaxJagArr = new Type[Sisuu + 1][];
        foreach (var EachPair in mLogDict) {
            long CurrBeki2 = EachPair.Key;
            long CurrSisuu = EachPair.Value;
            long CurrUB = pInitList.Count - 1 - CurrBeki2 + 1;
            mMinOrMaxJagArr[CurrSisuu] = new Type[CurrUB + 1];
        }

        // 長さ1の分を初期化
        for (int I = 0; I <= pInitList.Count - 1; I++) {
            mMinOrMaxJagArr[0][I] = pInitList[I];
        }

        // コンストラクタのヘルパメソッド
        ConstructorHelper();

        // 対応する2べき値[クエリの区間長]を設定
        SetBeki2Arr(pInitList.Count);
    }

    // コンストラクタ3(列挙が引数)
    internal SparseTable(IEnumerable<Type> pInitEnum, bool pIsMin)
    {
        mIsMin = pIsMin;

        Type[] InitArr = pInitEnum.ToArray();

        long Sisuu = 0;
        long Beki2 = 1;
        while (true) {
            mLogDict[Beki2] = Sisuu;
            Beki2 *= 2;

            if (Beki2 > InitArr.Length) {
                break;
            }
            Sisuu++;
        }

        mMinOrMaxJagArr = new Type[Sisuu + 1][];
        foreach (var EachPair in mLogDict) {
            long CurrBeki2 = EachPair.Key;
            long CurrSisuu = EachPair.Value;
            long CurrUB = InitArr.GetUpperBound(0) - CurrBeki2 + 1;
            mMinOrMaxJagArr[CurrSisuu] = new Type[CurrUB + 1];
        }

        // 長さ1の分を初期化
        for (int I = 0; I <= InitArr.GetUpperBound(0); I++) {
            mMinOrMaxJagArr[0][I] = InitArr[I];
        }

        // コンストラクタのヘルパメソッド
        ConstructorHelper();

        // 対応する2べき値[クエリの区間長]を設定
        SetBeki2Arr(InitArr.Length);
    }

    // 対応する2べき値[クエリの区間長]を設定
    private void SetBeki2Arr(long pDataLen)
    {
        long[] Beki2Arr = mLogDict.Keys.ToArray();

        mBeki2Arr = new long[pDataLen + 1];
        long CurrBeki2 = 1;
        for (long I = 0; I <= pDataLen; I++) {
            mBeki2Arr[I] = CurrBeki2;
            if (mLogDict.ContainsKey(I)) {
                CurrBeki2 = I;
            }
        }
    }

    // コンストラクタのヘルパメソッド
    private void ConstructorHelper()
    {
        for (long LoopLength = 2; LoopLength < long.MaxValue; LoopLength *= 2) {
            if (mLogDict.ContainsKey(LoopLength) == false) break;

            long HalfRange = LoopLength / 2;
            Type[] CurrArr = mMinOrMaxJagArr[mLogDict[HalfRange]];
            Type[] SendArr = mMinOrMaxJagArr[mLogDict[LoopLength]];
            for (long I = 0; I <= SendArr.GetUpperBound(0); I++) {
                long StaInd1 = I;
                long EndInd1 = I + HalfRange - 1;
                long StaInd2 = EndInd1 + 1;
                long EndInd2 = StaInd2 + HalfRange - 1;

                Type Val1 = CurrArr[I];
                Type Val2 = CurrArr[StaInd2];
                int CompResult = Val1.CompareTo(Val2);
                if (mIsMin) {
                    SendArr[I] = (CompResult >= 1 ? Val2 : Val1);
                }
                else {
                    SendArr[I] = (CompResult >= 1 ? Val1 : Val2);
                }
            }
        }
    }

    // 閉区間 [L,R]の最小値または最大値を求める
    internal Type Query(long pL, long pR)
    {
        // 区間を内包する2べき値を使用
        long RangeLen = pR - pL + 1;
        long Beki2 = mBeki2Arr[RangeLen];
        long Sisuu = mLogDict[Beki2];

        Type Val1 = mMinOrMaxJagArr[Sisuu][pL];
        Type Val2 = mMinOrMaxJagArr[Sisuu][pR - Beki2 + 1];
        int CompResult = Val1.CompareTo(Val2);

        if (mIsMin) {
            return (CompResult >= 1 ? Val2 : Val1);
        }
        return (CompResult >= 1 ? Val1 : Val2);
    }
}
#endregion

解説

区間の最大値なので、スパ−ステーブルを使ってます。