ABC253-F Operations on a Matrix

問題へのリンク

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

    struct QueryInfoDef
    {
        internal long QueryNo;
        internal long Type;
        internal long? L;
        internal long? R;
        internal long? X;
        internal long? I;
        internal long? J;
    }
    static List<QueryInfoDef> mQueryInfoList = new List<QueryInfoDef>();

    // 座標圧縮の結果
    static Dictionary<long, long> mXZaatuDict;

    // クエリ2に対応する、クエリ3のListを設定する
    // クエリ2 : クエリ3 = 1 : 多
    static Dictionary<long, List<long>> m2To3ListDict = new Dictionary<long, List<long>>();

    // クエリ3に対応するクエリ2の情報
    struct Query2Info
    {
        internal long SetVal; // クエリ2で代入した値
        internal long LazySegTreeVal; // 遅延セグ木の該当X座標の値
    }
    // Query2Info[クエリ3]なDict
    static Dictionary<long, Query2Info> mQuery2InfoDict = new Dictionary<long, Query2Info>();

    static void Main()
    {
        // クエリ情報をListに設定
        SetQueryInfo();

        // クエリ2に対応する、クエリ3のListを設定する
        // クエリ2 : クエリ3 = 1 : 多
        Create2To3List();

        // 登場するX座標を、座標圧縮
        ExecZaatu();

        Solve();
    }

    // クエリ情報をListに設定
    static void SetQueryInfo()
    {
        List<string> InputList = GetInputList();

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

        long QueryNo = 0;
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);

            long Type = wkArr[0];

            QueryInfoDef WillAdd;
            WillAdd.QueryNo = QueryNo++;
            WillAdd.Type = Type;
            WillAdd.L = null;
            WillAdd.R = null;
            WillAdd.X = null;
            WillAdd.I = null;
            WillAdd.J = null;

            if (Type == 1) {
                WillAdd.L = wkArr[1];
                WillAdd.R = wkArr[2];
                WillAdd.X = wkArr[3];
                mQueryInfoList.Add(WillAdd);
            }
            if (Type == 2) {
                WillAdd.I = wkArr[1];
                WillAdd.X = wkArr[2];
                mQueryInfoList.Add(WillAdd);
            }
            if (Type == 3) {
                WillAdd.I = wkArr[1];
                WillAdd.J = wkArr[2];
                mQueryInfoList.Add(WillAdd);
            }
        }
    }

    static void Create2To3List()
    {
        // クエリ番号のList[クエリ2のY座標]なDict
        var Query2ListDict = new Dictionary<long, List<long>>();

        foreach (QueryInfoDef EachQuery in mQueryInfoList.Where(pX => pX.Type == 2)) {
            long I = EachQuery.I.Value;
            if (Query2ListDict.ContainsKey(I) == false) {
                Query2ListDict[I] = new List<long>();
            }
            Query2ListDict[I].Add(EachQuery.QueryNo);
        }

        foreach (QueryInfoDef EachQuery in mQueryInfoList.Where(pX => pX.Type == 3)) {
            long I = EachQuery.I.Value;
            if (Query2ListDict.ContainsKey(I) == false) {
                continue;
            }
            long LowerMax = ExecNibunhou_LowerMax(EachQuery.QueryNo, Query2ListDict[I]);
            if (LowerMax == -1) continue;
            long LowerMaxVal = Query2ListDict[I][(int)LowerMax];

            if (m2To3ListDict.ContainsKey(LowerMaxVal) == false) {
                m2To3ListDict[LowerMaxVal] = new List<long>();
            }
            m2To3ListDict[LowerMaxVal].Add(EachQuery.QueryNo);
        }
    }

    // 二分法で、Val未満で最大の値を持つ、添字を返す
    static long ExecNibunhou_LowerMax(long pVal, List<long> pList)
    {
        // 最後の要素がVal未満の特殊ケース
        if (pVal > pList.Last()) {
            return pList.Count - 1;
        }
        // 最初の要素がVal以上の特殊ケース
        if (pVal <= pList[0]) {
            return -1;
        }

        long L = 0;
        long R = pList.Count - 1;

        while (L + 1 < R) {
            long Mid = (L + R) / 2;

            if (pList[(int)Mid] < pVal) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }

    // 登場するX座標を、座標圧縮
    static void ExecZaatu()
    {
        // 登場するX座標
        var AppearXSet = new HashSet<long>();

        foreach (QueryInfoDef EachQuery in mQueryInfoList) {
            if (EachQuery.Type == 1) {
                AppearXSet.Add(EachQuery.L.Value);
                AppearXSet.Add(EachQuery.R.Value);
            }
            if (EachQuery.Type == 3) {
                AppearXSet.Add(EachQuery.J.Value);
            }
        }

        mXZaatuDict = DeriveZaatuDict(AppearXSet);
    }

    //////////////////////////////////////////////////////////////////////////
    // 列挙を引数として、座標圧縮し、座圧後の値[座圧前の値]なDictを返す
    //////////////////////////////////////////////////////////////////////////
    static Dictionary<long, long> DeriveZaatuDict(HashSet<long> pSet)
    {
        var ZaatuDict = new Dictionary<long, long>();
        long No = 0;
        foreach (long EachVal in pSet.OrderBy(pX => pX)) {
            ZaatuDict[EachVal] = No;
            No++;
        }
        return ZaatuDict;
    }

    static void Solve()
    {
        var InsLazySegmentTree = new LazySegmentTree(mXZaatuDict.Count);

        var sb = new System.Text.StringBuilder();
        foreach (QueryInfoDef EachQuery in mQueryInfoList) {
            if (EachQuery.Type == 1) {
                long L = EachQuery.L.Value;
                long R = EachQuery.R.Value;
                L = mXZaatuDict[L];
                R = mXZaatuDict[R];

                long X = EachQuery.X.Value;

                InsLazySegmentTree.RangeAdd(L, R, X, 0);
            }
            if (EachQuery.Type == 2) {
                if (m2To3ListDict.ContainsKey(EachQuery.QueryNo) == false) {
                    continue;
                }
                foreach (long EachQuery3 in m2To3ListDict[EachQuery.QueryNo]) {
                    long J = mQueryInfoList[(int)EachQuery3].J.Value;
                    J = mXZaatuDict[J];
                    Query2Info WillAdd;
                    WillAdd.SetVal = EachQuery.X.Value;
                    WillAdd.LazySegTreeVal = InsLazySegmentTree.Query(J, J, 0);
                    mQuery2InfoDict[EachQuery3] = WillAdd;
                }
            }
            if (EachQuery.Type == 3) {
                long J = EachQuery.J.Value;
                J = mXZaatuDict[(int)J];
                long Answer = InsLazySegmentTree.Query(J, J, 0);
                if (mQuery2InfoDict.ContainsKey(EachQuery.QueryNo)) {
                    Answer -= mQuery2InfoDict[EachQuery.QueryNo].LazySegTreeVal;
                    Answer += mQuery2InfoDict[EachQuery.QueryNo].SetVal;
                }
                sb.Append(Answer);
                sb.AppendLine();
            }
        }
        Console.Write(sb.ToString());
    }
}

#region LazySegmentTree
// LazySegmentTreeクラス (RSQ and RAQ)
internal class LazySegmentTree
{
    private long[] mTreeNodeArr;
    private long UB; // 木のノードの配列のUB
    private long mLeafCnt; // 葉ノードの数

    private long[] mLazyArr; // 遅延配列

    // ノードの添字を引数とし、範囲の開始添字と終了添字を持つ配列
    private struct RangeInfoDef
    {
        internal long StaInd;
        internal long EndInd;
    }
    private RangeInfoDef[] mRangeInfo;

    // コンストラクタ
    internal LazySegmentTree(long pLeafCnt)
    {
        // 簡単のため、葉ノード数を2のべき乗に
        long ArrLength = 0;
        for (long I = 1; I < long.MaxValue; I *= 2) {
            ArrLength += I;
            mLeafCnt = I;

            if (pLeafCnt < mLeafCnt) break;
        }

        // すべての値を0に
        UB = ArrLength - 1;
        mTreeNodeArr = new long[UB + 1];
        for (int I = 0; I <= UB; I++) {
            mTreeNodeArr[I] = 0;
        }

        // 遅延配列を初期化
        mLazyArr = new long[UB + 1];

        // ノードの添字を引数とし、範囲の開始添字と終了添字を持つ配列の作成
        mRangeInfo = new RangeInfoDef[UB + 1];
        for (long I = 0; I <= UB; I++) {
            if (I == 0) {
                RangeInfoDef WillSet1;
                WillSet1.StaInd = 0;
                WillSet1.EndInd = mLeafCnt - 1;
                mRangeInfo[I] = WillSet1;
                continue;
            }
            long ParentNode = DeriveParentNode(I);
            RangeInfoDef ParentRangeInfo = mRangeInfo[ParentNode];

            RangeInfoDef WillSet2;
            long Mid = (ParentRangeInfo.StaInd + ParentRangeInfo.EndInd) / 2;

            if (I % 2 == 1) { // 奇数ノードの場合
                WillSet2.StaInd = ParentRangeInfo.StaInd;
                WillSet2.EndInd = Mid;
            }
            else { // 偶数ノードの場合
                WillSet2.StaInd = Mid + 1;
                WillSet2.EndInd = ParentRangeInfo.EndInd;
            }
            mRangeInfo[I] = WillSet2;
        }
    }

    // 親ノードの添字を取得
    private long DeriveParentNode(long pTarget)
    {
        return (pTarget - 1) / 2;
    }

    // 子ノードの添字(小さいほう)を取得
    private long DeriveChildNode(long pTarget)
    {
        return pTarget * 2 + 1;
    }

    // 開始添字と終了添字とカレントノードを引数として、区間加算を行う
    internal void RangeAdd(long pSearchStaInd, long pSearchEndInd, long pAddVal, long pCurrNode)
    {
        // カレントノードの遅延評価を行う
        LazyEval(pCurrNode);

        long CurrNodeStaInd = mRangeInfo[pCurrNode].StaInd;
        long CurrNodeEndInd = mRangeInfo[pCurrNode].EndInd;

        // OverLapしてなければ、何もしない
        if (CurrNodeEndInd < pSearchStaInd || pSearchEndInd < CurrNodeStaInd)
            return;

        // 完全に含んでいれば、遅延配列に値を入れた後に評価
        if (pSearchStaInd <= CurrNodeStaInd && CurrNodeEndInd <= pSearchEndInd) {
            mLazyArr[pCurrNode] += pAddVal * (CurrNodeEndInd - CurrNodeStaInd + 1);
            LazyEval(pCurrNode);
            return;
        }

        // そうでなければ、2つの区間に再帰呼出し
        long ChildNode1 = DeriveChildNode(pCurrNode);
        long ChildNode2 = ChildNode1 + 1;

        RangeAdd(pSearchStaInd, pSearchEndInd, pAddVal, ChildNode1);
        RangeAdd(pSearchStaInd, pSearchEndInd, pAddVal, ChildNode2);
        mTreeNodeArr[pCurrNode] = mTreeNodeArr[ChildNode1] + mTreeNodeArr[ChildNode2];
    }

    // 開始添字と終了添字とカレントノードを引数として、Sumを返す
    internal long Query(long pSearchStaInd, long pSearchEndInd, long pCurrNode)
    {
        // 該当ノードを遅延評価する
        LazyEval(pCurrNode);

        long CurrNodeStaInd = mRangeInfo[pCurrNode].StaInd;
        long CurrNodeEndInd = mRangeInfo[pCurrNode].EndInd;

        // OverLapしてなければ、0
        if (CurrNodeEndInd < pSearchStaInd || pSearchEndInd < CurrNodeStaInd)
            return 0;

        // 完全に含んでいれば、このノードの値
        if (pSearchStaInd <= CurrNodeStaInd && CurrNodeEndInd <= pSearchEndInd)
            return mTreeNodeArr[pCurrNode];

        // そうでなければ、2つの子のSum
        long ChildNode1 = DeriveChildNode(pCurrNode);
        long ChildNode2 = ChildNode1 + 1;

        long ChildVal1 = Query(pSearchStaInd, pSearchEndInd, ChildNode1);
        long ChildVal2 = Query(pSearchStaInd, pSearchEndInd, ChildNode2);
        return ChildVal1 + ChildVal2;
    }

    // カレントノードを引数として、遅延評価を行う
    void LazyEval(long pCurrNode)
    {
        // 遅延配列が0なら何もしない
        if (mLazyArr[pCurrNode] == 0) return;

        // 遅延配列の値を設定する
        mTreeNodeArr[pCurrNode] += mLazyArr[pCurrNode];

        long ChildNode1 = DeriveChildNode(pCurrNode);
        long ChildNode2 = ChildNode1 + 1;

        if (ChildNode1 <= UB) mLazyArr[ChildNode1] += mLazyArr[pCurrNode] / 2;
        if (ChildNode2 <= UB) mLazyArr[ChildNode2] += mLazyArr[pCurrNode] / 2;

        // 伝播が終わったので、自ノードの遅延配列を空にする
        mLazyArr[pCurrNode] = 0;
    }

    internal void DebugPrint()
    {
        for (int I = 0; I <= UB; I++) {
            if (mLazyArr[I] > 0) {
                Console.WriteLine("mTreeNodeArr[{0}] = {1} , mLazyArr[{0}] = {2}",
                    I, mTreeNodeArr[I], mLazyArr[I]);
            }
            else {
                Console.WriteLine("mTreeNodeArr[{0}] = {1}", I, mTreeNodeArr[I]);
            }
        }
    }
}
#endregion

解説

クエリ1は、区間更新なので遅延セグ木が使えます。

考察すると
クエリ2とクエリ3は、
クエリ2 : クエリ3 = 1 : 多
の関係になっているので
クエリを先読みして、相互リンクを作っておきます。

後は、クエリを順に読んで
クエリ1なら、遅延セグ木を更新
クエリ2なら、リンク先のクエリ3に
クエリ2で代入する値と、遅延セグ木の該当X座標の値を設定
クエリ3なら、リンク先のクエリ2情報
と現時点の遅延セグ木の値から、当該座標の値を取得

として、解くことができます。