ABC174-F Range Set 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("4 3");
            WillReturn.Add("1 2 1 3");
            WillReturn.Add("1 3");
            WillReturn.Add("2 4");
            WillReturn.Add("3 3");
            //2
            //3
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 10");
            WillReturn.Add("2 5 6 5 2 1 7 9 7 2");
            WillReturn.Add("5 5");
            WillReturn.Add("2 4");
            WillReturn.Add("6 7");
            WillReturn.Add("2 2");
            WillReturn.Add("7 8");
            WillReturn.Add("7 9");
            WillReturn.Add("1 8");
            WillReturn.Add("6 9");
            WillReturn.Add("8 10");
            WillReturn.Add("6 8");
            //1
            //2
            //2
            //1
            //2
            //2
            //6
            //3
            //3
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    class QueryInfoDef
    {
        internal int Time;
        internal int RangeSta;
        internal int RangeEnd;
        internal int Answer;
    }

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

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

        var QueryInfoList = new List<QueryInfoDef>();
        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            var WillAdd = new QueryInfoDef(); ;
            WillAdd.Time = QueryInfoList.Count;
            WillAdd.RangeSta = wkArr[0] - 1;
            WillAdd.RangeEnd = wkArr[1] - 1;
            QueryInfoList.Add(WillAdd);
        }
        QueryInfoList = QueryInfoList.OrderBy(pX => pX.RangeSta).ToList();

        var QueueDict = new Dictionary<int, Queue<int>>();

        for (int I = 0; I <= CArr.GetUpperBound(0); I++) {
            if (QueueDict.ContainsKey(CArr[I]) == false) {
                QueueDict[CArr[I]] = new Queue<int>();
            }
            QueueDict[CArr[I]].Enqueue(I);
        }

        int MaxRangeEnd = QueryInfoList.Max(pX => pX.RangeEnd);

        var Ins_Fenwick_Tree = new Fenwick_Tree(MaxRangeEnd + 1);
        foreach (var EachPair in QueueDict) {
            int DequeuedVal = EachPair.Value.Dequeue();
            Ins_Fenwick_Tree.Add(DequeuedVal, 1, true);
        }

        for (int I = 0; I <= QueryInfoList.Count - 1; I++) {
            int CurrRangeSta = QueryInfoList[I].RangeSta;
            int CurrRangeEnd = QueryInfoList[I].RangeEnd;
            int Answer = Ins_Fenwick_Tree.GetSum(CurrRangeSta, CurrRangeEnd, true);
            QueryInfoList[I].Answer = Answer;

            if (I < QueryInfoList.Count - 1) {
                int NextRangeSta = QueryInfoList[I + 1].RangeSta;

                while (CurrRangeSta < NextRangeSta) {
                    int CurrVal = CArr[CurrRangeSta];

                    if (QueueDict[CurrVal].Count > 0) {
                        int DequeuedVal = QueueDict[CurrVal].Dequeue();
                        Ins_Fenwick_Tree.Add(DequeuedVal, 1, true);
                    }
                    CurrRangeSta++;
                }
            }
        }

        var sb = new System.Text.StringBuilder();
        foreach (QueryInfoDef EachQueryInfo in QueryInfoList.OrderBy(pX => pX.Time)) {
            sb.Append(EachQueryInfo.Answer);
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }
}

#region Fenwick_Tree
// フェニック木
internal class Fenwick_Tree
{
    private int[] mBitArr;
    private int mN;

    // コンストラクタ
    internal Fenwick_Tree(int pItemCnt)
    {
        mN = pItemCnt;
        mBitArr = new int[pItemCnt + 1];
    }

    // [pSta,pEnd] のSumを返す
    internal int GetSum(int pSta, int pEnd, bool pIsZeroOrigin)
    {
        return GetSum(pEnd, pIsZeroOrigin) - GetSum(pSta - 1, pIsZeroOrigin);
    }

    // [0,pEnd] のSumを返す
    internal int GetSum(int pEnd, bool pIsZeroOrigin)
    {
        if (pIsZeroOrigin) {
            pEnd++; // 1オリジンに変更
        }

        int Sum = 0;
        while (pEnd >= 1) {
            Sum += mBitArr[pEnd];
            pEnd -= pEnd & -pEnd;
        }
        return Sum;
    }

    // [I] に Xを加算
    internal void Add(int pI, int pX, bool pIsZeroOrigin)
    {
        if (pIsZeroOrigin) {
            pI++; // 1オリジンに変更
        }

        while (pI <= mN) {
            mBitArr[pI] += pX;
            pI += pI & -pI;
        }
    }
}
#endregion

解説

下記の入力を考えます。
3 1 4 1 5 9 2 6 5 3 5

各数値の1番目は1、2番目以降は0を記述すると下記になります。

3 1 4 1 5 9 2 6 5 3 5
1 1 1 0 1 1 1 1 0 0 0

クエリを先読みして、RangeStaの昇順に見ていき
区間和を求めれば、解だと分かります。

各値が、どのIndにあるかは、Dictionary<int, Queue<int>>
で管理できます。