using System; using System.Collections.Generic; using System.Linq; // https://yukicoder.me/problems/no/230 class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("5"); WillReturn.Add("2"); WillReturn.Add("1 0 3"); WillReturn.Add("2 2 4"); //2 3 } else if (InputPattern == "Input2") { WillReturn.Add("5"); WillReturn.Add("3"); WillReturn.Add("1 0 4"); WillReturn.Add("2 1 3"); WillReturn.Add("0 4 4"); //3 3 } else if (InputPattern == "Input3") { WillReturn.Add("6"); WillReturn.Add("6"); WillReturn.Add("1 1 2"); WillReturn.Add("2 4 5"); WillReturn.Add("0 2 4"); WillReturn.Add("2 0 3"); WillReturn.Add("1 1 5"); WillReturn.Add("0 0 5"); //10 1 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static void Main() { List InputList = GetInputList(); int N = int.Parse(InputList[0]); var InsLazySegmentTreeVal = new LazySegmentTree(N); var InsLazySegmentTreeZeroCnt = new LazySegmentTree(N); InsLazySegmentTreeZeroCnt.RangeUpdate(0, N, 1, 0); int[] wkArr = { }; Action SplitAct = pStr => wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray(); long ScoreA = 0; long ScoreB = 0; foreach (string EachStr in InputList.Skip(2)) { SplitAct(EachStr); int X = wkArr[0]; int L = wkArr[1]; int R = wkArr[2]; if (X == 0) { long RangeSum = InsLazySegmentTreeVal.Query(L, R, 0); long RangeNonZeroCnt = InsLazySegmentTreeZeroCnt.Query(L, R, 0); long RangeCnt = R - L + 1; RangeCnt -= RangeNonZeroCnt; long RangePlusCnt, RangeMinusCnt; SolveRenritu(RangeCnt, RangeSum, out RangePlusCnt, out RangeMinusCnt); if (RangePlusCnt > RangeMinusCnt) ScoreA += RangePlusCnt; if (RangeMinusCnt > RangePlusCnt) ScoreB += RangeMinusCnt; } if (X == 1) { InsLazySegmentTreeVal.RangeUpdate(L, R, 1, 0); InsLazySegmentTreeZeroCnt.RangeUpdate(L, R, 0, 0); } if (X == 2) { InsLazySegmentTreeVal.RangeUpdate(L, R, -1, 0); InsLazySegmentTreeZeroCnt.RangeUpdate(L, R, 0, 0); } } long AllSum = InsLazySegmentTreeVal.Query(0, N, 0); long AllNonZeroCnt = InsLazySegmentTreeZeroCnt.Query(0, N, 0); long AllRangeCnt = N + 1; AllRangeCnt -= AllNonZeroCnt; long AllPlusCnt, AllMinusCnt; SolveRenritu(AllRangeCnt, AllSum, out AllPlusCnt, out AllMinusCnt); ScoreA += AllPlusCnt; ScoreB += AllMinusCnt; Console.WriteLine("{0} {1}", ScoreA, ScoreB); } // 下記の連立方程式を加減法で解く // A+B = Cnt // A-B = Sum static void SolveRenritu(long pCnt, long pSum, out long pA, out long pB) { pA = (pCnt + pSum) / 2; pB = pCnt - pA; } } // LazySegmentTreeクラス internal class LazySegmentTree { private int[] mTreeNodeArr; private int UB; // 木のノードの配列のUB private int mLeafCnt; // 葉ノードの数 private int?[] mLazyArr; // 遅延配列 // ノードの添字を引数とし、範囲の開始添字と終了添字を持つ配列 private struct RangeInfoDef { internal int StaInd; internal int EndInd; } private RangeInfoDef[] mRangeInfo; // コンストラクタ internal LazySegmentTree(int pLeafCnt) { // 簡単のため、葉ノード数を2のべき乗に int ArrLength = 0; for (int I = 1; I < int.MaxValue; I *= 2) { ArrLength += I; mLeafCnt = I; if (pLeafCnt < mLeafCnt) break; } // すべての値を0に UB = ArrLength - 1; mTreeNodeArr = new int[UB + 1]; for (int I = 0; I <= UB; I++) { mTreeNodeArr[I] = 0; } // 遅延配列を初期化 mLazyArr = new int?[UB + 1]; // ノードの添字を引数とし、範囲の開始添字と終了添字を持つ配列の作成 mRangeInfo = new RangeInfoDef[UB + 1]; for (int I = 0; I <= UB; I++) { if (I == 0) { RangeInfoDef WillSet1; WillSet1.StaInd = 0; WillSet1.EndInd = mLeafCnt - 1; mRangeInfo[I] = WillSet1; continue; } int ParentNode = DeriveParentNode(I); RangeInfoDef ParentRangeInfo = mRangeInfo[ParentNode]; RangeInfoDef WillSet2; int 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 int DeriveParentNode(int pTarget) { return (pTarget - 1) / 2; } // 子ノードの添字(小さいほう)を取得 private int DeriveChildNode(int pTarget) { return pTarget * 2 + 1; } // カレントノードを引数として、遅延評価を行う void LazyEval(int pCurrNode) { // 遅延配列が空なら何もしない if (mLazyArr[pCurrNode].HasValue == false) return; int CurrNodeStaInd = mRangeInfo[pCurrNode].StaInd; int CurrNodeEndInd = mRangeInfo[pCurrNode].EndInd; // 遅延配列の値を反映する //mTreeNodeArr[pCurrNode] += mLazyArr[pCurrNode].Value; mTreeNodeArr[pCurrNode] = mLazyArr[pCurrNode].Value * (CurrNodeEndInd - CurrNodeStaInd + 1); int ChildNode1 = DeriveChildNode(pCurrNode); int ChildNode2 = ChildNode1 + 1; //if (ChildNode1 <= UB) mLazyArr[ChildNode1] += mLazyArr[pCurrNode] / 2; //if (ChildNode2 <= UB) mLazyArr[ChildNode2] += mLazyArr[pCurrNode] / 2; if (ChildNode1 <= UB) mLazyArr[ChildNode1] = mLazyArr[pCurrNode]; if (ChildNode2 <= UB) mLazyArr[ChildNode2] = mLazyArr[pCurrNode]; // 伝播が終わったので、自ノードの遅延配列を空にする mLazyArr[pCurrNode] = null; } // 開始添字と終了添字とカレントノードを引数として、区間更新を行う internal void RangeUpdate(int pSearchStaInd, int pSearchEndInd, int pUpdateVal, int pCurrNode) { // カレントノードの遅延評価を行う LazyEval(pCurrNode); int CurrNodeStaInd = mRangeInfo[pCurrNode].StaInd; int CurrNodeEndInd = mRangeInfo[pCurrNode].EndInd; // OverLapしてなければ、何もしない if (CurrNodeEndInd < pSearchStaInd || pSearchEndInd < CurrNodeStaInd) { return; } // 完全に含んでいれば、遅延配列に値を入れた後に評価 if (pSearchStaInd <= CurrNodeStaInd && CurrNodeEndInd <= pSearchEndInd) { //mLazyArr[pCurrNode] += pUpdateVal * (CurrNodeEndInd - CurrNodeStaInd + 1); mLazyArr[pCurrNode] = pUpdateVal; LazyEval(pCurrNode); return; } // そうでなければ、2つの区間に再帰呼出し int ChildNode1 = DeriveChildNode(pCurrNode); int ChildNode2 = ChildNode1 + 1; RangeUpdate(pSearchStaInd, pSearchEndInd, pUpdateVal, ChildNode1); RangeUpdate(pSearchStaInd, pSearchEndInd, pUpdateVal, ChildNode2); mTreeNodeArr[pCurrNode] = mTreeNodeArr[ChildNode1] + mTreeNodeArr[ChildNode2]; } // 開始添字と終了添字とカレントノードを引数として、最小値を返す internal int Query(int pSearchStaInd, int pSearchEndInd, int pCurrNode) { // 該当ノードを遅延評価する LazyEval(pCurrNode); int CurrNodeStaInd = mRangeInfo[pCurrNode].StaInd; int CurrNodeEndInd = mRangeInfo[pCurrNode].EndInd; // OverLapしてなければ、0 if (CurrNodeEndInd < pSearchStaInd || pSearchEndInd < CurrNodeStaInd) return 0; // 完全に含んでいれば、このノードの値 if (pSearchStaInd <= CurrNodeStaInd && CurrNodeEndInd <= pSearchEndInd) return mTreeNodeArr[pCurrNode]; // そうでなければ、2つの子のSum int ChildNode1 = DeriveChildNode(pCurrNode); int ChildNode2 = ChildNode1 + 1; int ChildVal1 = Query(pSearchStaInd, pSearchEndInd, ChildNode1); int ChildVal2 = Query(pSearchStaInd, pSearchEndInd, ChildNode2); return ChildVal1 + ChildVal2; } internal void DebugPrint() { for (int I = 0; I <= UB; I++) { if (mLazyArr[I].HasValue) { Console.WriteLine("mTreeNodeArr[{0}] = {1} , mLazyArr[{0}] = {2}", I, mTreeNodeArr[I], mLazyArr[I]); } else { Console.WriteLine("mTreeNodeArr[{0}] = {1}", I, mTreeNodeArr[I]); } } } }