ABC282-F Union of Two Sets

問題へのリンク

C#のソース

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

class Program
{
    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static long mN;

    static void Main()
    {
        mN = long.Parse(Console.ReadLine());
        SetRangeInfoList();

        Console.WriteLine(mRangeInfoList.Count);
        foreach (RangeInfoDef EachRangeInfo in mRangeInfoList) {
            Console.WriteLine("{0} {1}", EachRangeInfo.RangeSta, EachRangeInfo.RangeEnd);
        }

        long Q = long.Parse(Console.ReadLine());
        for (long I = 1; I <= Q; I++) {
            string StrLine = Console.ReadLine();
            long[] wkArr = GetSplitArr(StrLine);
            long RangeSta = wkArr[0];
            long RangeEnd = wkArr[1];
            GetCoverRangeInfo(RangeSta, RangeEnd);
        }
    }

    struct RangeInfoDef
    {
        internal long No;
        internal long RangeSta;
        internal long RangeEnd;
    }
    static List<RangeInfoDef> mRangeInfoList = new List<RangeInfoDef>();

    // No[区間情報のハッシュ値]なDict
    static Dictionary<string, long> mRangeDict = new Dictionary<string, long>();

    // Nを引数とし、スパーステーブルのRangeのListを設定
    static void SetRangeInfoList()
    {
        long Beki2 = 1;
        while (true) {
            if (Beki2 > mN) {
                break;
            }

            for (long I = 1; I <= mN; I++) {
                long RangeSta = I;
                long RangeEnd = RangeSta + Beki2 - 1;
                if (RangeEnd > mN) break;
                RangeInfoDef WillAdd;
                WillAdd.No = mRangeInfoList.Count + 1;
                WillAdd.RangeSta = RangeSta;
                WillAdd.RangeEnd = RangeEnd;
                mRangeInfoList.Add(WillAdd);
            }
            Beki2 *= 2;
        }

        mRangeInfoList.ForEach(pX =>
        {
            string Hash = GetHash(pX.RangeSta, pX.RangeEnd);
            mRangeDict[Hash] = pX.No;
        });
    }

    // RangeStaとRangeEndからなるハッシュ値
    static string GetHash(long pSta, long pEnd)
    {
        return string.Format("{0},{1}", pSta, pEnd);
    }

    // 区間を引数として、カバーする二つのRange情報を出力
    static void GetCoverRangeInfo(long RangeSta, long pRangeEnd)
    {
        long RangeLength = pRangeEnd - RangeSta + 1;
        long Beki2 = 1;
        while (true) {
            if (Beki2 * 2 > RangeLength) break;
            Beki2 *= 2;
        }

        long No1 = mRangeDict[GetHash(RangeSta, RangeSta + Beki2 - 1)];
        long No2 = mRangeDict[GetHash(pRangeEnd - Beki2 + 1, pRangeEnd)];
        Console.WriteLine("{0} {1}", No1, No2);
    }
}

解説