ABC288-D Range Add 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("7 3");
            WillReturn.Add("3 -1 1 -2 2 0 5");
            WillReturn.Add("2");
            WillReturn.Add("1 6");
            WillReturn.Add("2 7");
            //Yes
            //No
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("20 4");
            WillReturn.Add("-19 -66 -99 16 18 33 32 28 26 11 12 0 -16 4 21 21 37 17 55 -19");
            WillReturn.Add("5");
            WillReturn.Add("13 16");
            WillReturn.Add("4 11");
            WillReturn.Add("3 12");
            WillReturn.Add("13 18");
            WillReturn.Add("4 10");
            //No
            //Yes
            //No
            //Yes
            //No
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        long K = wkArr[1];

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        Fenwick_Tree[] Fenwick_Tree_Arr = new Fenwick_Tree[K];

        for (int I = 0; I <= Fenwick_Tree_Arr.GetUpperBound(0); I++) {
            Fenwick_Tree_Arr[I] = new Fenwick_Tree(AArr.Length);
        }

        for (int I = 0; I <= AArr.GetUpperBound(0); I++) {
            long Ind = I % K;
            Fenwick_Tree_Arr[Ind].Add(I, AArr[I], true);
        }

        var sb = new System.Text.StringBuilder();
        foreach (string EachStr in InputList.Skip(3)) {
            SplitAct(EachStr);
            long L = wkArr[0] - 1;
            long R = wkArr[1] - 1;

            var SumSet = new HashSet<long>();
            for (int I = 0; I <= Fenwick_Tree_Arr.GetUpperBound(0); I++) {
                SumSet.Add(Fenwick_Tree_Arr[I].GetSum(L, R, true));
            }

            if (SumSet.Count == 1) {
                sb.AppendLine("Yes");
            }
            else {
                sb.AppendLine("No");
            }
        }
        Console.Write(sb.ToString());
    }
}

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

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

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

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

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

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

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

解説

A B C D E F G H I J
という区間で考えます。

添字を振ると下記になります。

0 1 2 3 4 5 6 7 8 9
A B C D E F G H I J

3を法をして分類すると
0 A D G J
1 B E H
2 C F I

考察すると
加算操作は、
modが0のグループ
modが1のグループ
modが2のグループ
に同じ値を加算すると分かります。

なので、グループごとの和が全て等しいことが
必要条件になります。

十分性については、左から0にしていくことができるので
十分条件だと分かります。

実装としては、フェニック木をK本作れば良いです