典型90問 010 Score Sum Queries（★2）

問題へのリンク

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 72");
            WillReturn.Add("2 78");
            WillReturn.Add("2 94");
            WillReturn.Add("1 23");
            WillReturn.Add("2 89");
            WillReturn.Add("1 40");
            WillReturn.Add("1 75");
            WillReturn.Add("1");
            WillReturn.Add("2 6");
            //63 261
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7");
            WillReturn.Add("1 72");
            WillReturn.Add("2 78");
            WillReturn.Add("2 94");
            WillReturn.Add("1 23");
            WillReturn.Add("2 89");
            WillReturn.Add("1 40");
            WillReturn.Add("1 75");
            WillReturn.Add("10");
            WillReturn.Add("1 3");
            WillReturn.Add("2 4");
            WillReturn.Add("3 5");
            WillReturn.Add("4 6");
            WillReturn.Add("5 7");
            WillReturn.Add("1 5");
            WillReturn.Add("2 6");
            WillReturn.Add("3 7");
            WillReturn.Add("1 6");
            WillReturn.Add("2 7");
            //72 172
            //23 172
            //23 183
            //63 89
            //115 89
            //95 261
            //63 261
            //138 183
            //135 261
            //138 261
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1");
            WillReturn.Add("1 100");
            WillReturn.Add("3");
            WillReturn.Add("1 1");
            WillReturn.Add("1 1");
            WillReturn.Add("1 1");
            //100 0
            //100 0
            //100 0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("20");
            WillReturn.Add("2 90");
            WillReturn.Add("1 67");
            WillReturn.Add("2 9");
            WillReturn.Add("2 17");
            WillReturn.Add("2 85");
            WillReturn.Add("2 43");
            WillReturn.Add("2 11");
            WillReturn.Add("1 32");
            WillReturn.Add("2 16");
            WillReturn.Add("1 19");
            WillReturn.Add("2 65");
            WillReturn.Add("1 14");
            WillReturn.Add("1 51");
            WillReturn.Add("2 94");
            WillReturn.Add("1 4");
            WillReturn.Add("1 55");
            WillReturn.Add("2 90");
            WillReturn.Add("1 89");
            WillReturn.Add("1 35");
            WillReturn.Add("2 81");
            WillReturn.Add("20");
            WillReturn.Add("3 17");
            WillReturn.Add("5 5");
            WillReturn.Add("11 11");
            WillReturn.Add("8 10");
            WillReturn.Add("3 13");
            WillReturn.Add("2 6");
            WillReturn.Add("3 7");
            WillReturn.Add("3 5");
            WillReturn.Add("12 18");
            WillReturn.Add("4 8");
            WillReturn.Add("3 16");
            WillReturn.Add("6 8");
            WillReturn.Add("3 20");
            WillReturn.Add("1 12");
            WillReturn.Add("1 6");
            WillReturn.Add("5 16");
            WillReturn.Add("3 10");
            WillReturn.Add("17 19");
            WillReturn.Add("4 4");
            WillReturn.Add("7 15");
            //175 430
            //0 85
            //0 65
            //51 16
            //116 246
            //67 154
            //0 165
            //0 111
            //213 184
            //32 156
            //175 340
            //32 54
            //299 511
            //132 336
            //67 244
            //175 314
            //51 181
            //124 90
            //0 17
            //120 186
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mN;

    struct CPInfoDef
    {
        internal int Ind;
        internal int C;
        internal int P;
    }
    static List<CPInfoDef> mCPInfoList = new List<CPInfoDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();

        mN = int.Parse(InputList[0]);

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

        for (int I = 1; I <= mN; I++) {
            SplitAct(InputList[I]);
            CPInfoDef WillAdd;
            WillAdd.Ind = I;
            WillAdd.C = wkArr[0];
            WillAdd.P = wkArr[1];
            mCPInfoList.Add(WillAdd);
        }

        int MaxInd = mCPInfoList.Max(pX => pX.Ind);
        var InsFenwick_Tree1 = new Fenwick_Tree(MaxInd + 1);
        var InsFenwick_Tree2 = new Fenwick_Tree(MaxInd + 1);

        foreach (CPInfoDef EachCPInfo in mCPInfoList) {
            if (EachCPInfo.C == 1) {
                InsFenwick_Tree1.Add(EachCPInfo.Ind, EachCPInfo.P, true);
            }
            if (EachCPInfo.C == 2) {
                InsFenwick_Tree2.Add(EachCPInfo.Ind, EachCPInfo.P, true);
            }
        }

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

            int Sum1 = InsFenwick_Tree1.GetSum(L, R, true);
            int Sum2 = InsFenwick_Tree2.GetSum(L, R, true);
            Console.WriteLine("{0} {1}", Sum1, Sum2);
        }
    }
}

#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

解説

1点更新の区間和なのでフェニック木が使えます。