ABC434-D Clouds

問題へのリンク

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

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

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

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        long UB = 2000 - 1;

        /////////////////////////////////////////////////////////////////
        // 2次元いもす法
        /////////////////////////////////////////////////////////////////
        long[,] ImosArr = new long[UB + 1, UB + 1];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long StaY = wkArr[0] - 1;
            long EndY = wkArr[1] - 1;
            long StaX = wkArr[2] - 1;
            long EndX = wkArr[3] - 1;

            EndX++;
            EndY++;

            ImosArr[StaX, StaY]++;
            if (EndX <= UB) ImosArr[EndX, StaY]--;
            if (EndY <= UB) ImosArr[StaX, EndY]--;
            if (EndX <= UB && EndY <= UB) ImosArr[EndX, EndY]++;
        }

        //横方向の累積和を求める
        for (int X = 1; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                ImosArr[X, Y] += ImosArr[X - 1, Y];
            }
        }

        //縦方向の累積和を求める
        for (int Y = 1; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                ImosArr[X, Y] += ImosArr[X, Y - 1];
            }
        }

        /////////////////////////////////////////////////////////////////
        // BaseAnswerを求める
        /////////////////////////////////////////////////////////////////
        long BaseAnswer = 2000 * 2000;
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                if (ImosArr[X, Y] > 0) {
                    BaseAnswer--;
                }
            }
        }

        /////////////////////////////////////////////////////////////////
        // 2次元累積和
        /////////////////////////////////////////////////////////////////
        long[,] RunSumArr = new long[UB + 1, UB + 1];
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                if (ImosArr[X, Y] == 1) {
                    RunSumArr[X, Y] = 1;
                }
            }
        }

        // 累積和を設定する (横方向)
        for (int LoopX = 1; LoopX <= UB; LoopX++) {
            for (int LoopY = 0; LoopY <= UB; LoopY++) {
                RunSumArr[LoopX, LoopY] += RunSumArr[LoopX - 1, LoopY];
            }
        }

        // 累積和を設定する (縦方向)
        for (int LoopX = 0; LoopX <= UB; LoopX++) {
            for (int LoopY = 1; LoopY <= UB; LoopY++) {
                RunSumArr[LoopX, LoopY] += RunSumArr[LoopX, LoopY - 1];
            }
        }

        /////////////////////////////////////////////////////////////////
        // クエリに回答する
        /////////////////////////////////////////////////////////////////
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long StaY = wkArr[0] - 1;
            long EndY = wkArr[1] - 1;
            long StaX = wkArr[2] - 1;
            long EndX = wkArr[3] - 1;

            long CurrSum = DeriveSumRect(RunSumArr, EndX, EndY);
            CurrSum -= DeriveSumRect(RunSumArr, StaX - 1, EndY);
            CurrSum -= DeriveSumRect(RunSumArr, EndX, StaY - 1);
            CurrSum += DeriveSumRect(RunSumArr, StaX - 1, StaY - 1);
            Console.WriteLine(BaseAnswer + CurrSum);
        }
    }

    // (0,0)と(pX,pY)からなる長方形の数の和を返す
    static long DeriveSumRect(long[,] pRunSumArr, long pX, long pY)
    {
        if (pX < 0) return 0;
        if (pY < 0) return 0;
        return pRunSumArr[pX, pY];
    }
}

解説

最初に、マス目ごとに
何個の雲で覆われてるかを
2次元いもす法で求めます。

次に1つの雲でしか覆われてないマスを0
そうでないマスを1とし、2次元累積和を求めます。

すると、各クエリにO(1)で回答可能になります。