using System; using System.Collections.Generic; using System.Linq; 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.Internal_RangeUpdate(0, N, 1); 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.Internal_Query(L, R); long RangeNonZeroCnt = InsLazySegmentTreeZeroCnt.Internal_Query(L, R); 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.Internal_RangeUpdate(L, R, 1); InsLazySegmentTreeZeroCnt.Internal_RangeUpdate(L, R, 0); } if (X == 2) { InsLazySegmentTreeVal.Internal_RangeUpdate(L, R, -1); InsLazySegmentTreeZeroCnt.Internal_RangeUpdate(L, R, 0); } } long AllSum = InsLazySegmentTreeVal.Internal_Query(0, N); long AllNonZeroCnt = InsLazySegmentTreeZeroCnt.Internal_Query(0, N); 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; } } #region LazySegmentTree // LazySegmentTreeクラス (RSQ and RUQ) internal class LazySegmentTree { private long[] mTreeNodeArr; private long UB; // 木のノードの配列のUB private long mLeafCnt; // 葉ノードの数 private long mExternalArrUB; private long?[] mLazyArr; // 遅延配列 // ノードの添字を引数とし、範囲の開始添字と終了添字を持つ配列 private struct RangeInfoDef { internal long StaInd; internal long EndInd; } private RangeInfoDef[] mRangeInfo; // ノードのIndexの列挙を返す internal IEnumerable GetNodeIndEnum() { for (long I = 0; I <= mExternalArrUB; I++) { yield return I; } } // 木のノードのUBを返す internal long GetUB() { return mExternalArrUB; } // コンストラクタその1 // 引数 外部IndのUB internal LazySegmentTree(long pExternalArrUB) { mExternalArrUB = pExternalArrUB; ConstructorTreeInit(); } // コンストラクタその2 // 引数 初期化用の配列 internal LazySegmentTree(long[] pInitArr) { mExternalArrUB = pInitArr.GetUpperBound(0); ConstructorTreeInit(); for (long I = 0; I <= pInitArr.GetUpperBound(0); I++) { long TreeNode = DeriveTreeNode(I); mTreeNodeArr[TreeNode] = pInitArr[I]; } // 木DPの要領で、葉から根に伝播 ExecTreeDP(); } // コンストラクタその3 // 引数 初期化用のList internal LazySegmentTree(List pInitList) { mExternalArrUB = pInitList.Count - 1; ConstructorTreeInit(); for (long I = 0; I <= pInitList.Count - 1; I++) { long TreeNode = DeriveTreeNode(I); mTreeNodeArr[TreeNode] = pInitList[(int)I]; } // 木DPの要領で、葉から根に伝播 ExecTreeDP(); } // コンストラクタのヘルパメソッド(木の初期化) private void ConstructorTreeInit() { // 簡単のため、葉ノード数を2のべき乗に long ArrLength = 0; for (long I = 1; I < long.MaxValue; I *= 2) { ArrLength += I; mLeafCnt = I; if (mExternalArrUB + 1 < mLeafCnt) break; } UB = ArrLength - 1; mTreeNodeArr = new long[UB + 1]; // 遅延配列を初期化 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; } } // 木DPの要領で、葉から根に伝播 private void ExecTreeDP() { for (long I = UB; 0 < I; I--) { long SendNode = DeriveParentNode(I); mTreeNodeArr[SendNode] += mTreeNodeArr[I]; } } // インデクサ internal long this[long pInd] { get { return Internal_Query(pInd, pInd); } set { Internal_RangeUpdate(pInd, pInd, value); } } // 親ノードの添字を取得 private long DeriveParentNode(long pTarget) { return (pTarget - 1) / 2; } // 子ノードの添字(小さいほう)を取得 private long DeriveChildNode(long pTarget) { return pTarget * 2 + 1; } // 葉ノードの配列の添字を木の添字に変換して返す private long DeriveTreeNode(long pLeafArrInd) { long BaseInd = UB - mLeafCnt + 1; return BaseInd + pLeafArrInd; } // カレントノードを引数として、遅延評価を行う private void LazyEval(long pCurrNode) { // 遅延配列が空なら何もしない if (mLazyArr[pCurrNode].HasValue == false) return; long CurrNodeStaInd = mRangeInfo[pCurrNode].StaInd; long CurrNodeEndInd = mRangeInfo[pCurrNode].EndInd; // 遅延配列の値を反映する mTreeNodeArr[pCurrNode] = mLazyArr[pCurrNode].Value * (CurrNodeEndInd - CurrNodeStaInd + 1); long ChildNode1 = DeriveChildNode(pCurrNode); long ChildNode2 = ChildNode1 + 1; if (ChildNode1 <= UB) mLazyArr[ChildNode1] = mLazyArr[pCurrNode]; if (ChildNode2 <= UB) mLazyArr[ChildNode2] = mLazyArr[pCurrNode]; // 伝播が終わったので、自ノードの遅延配列を空にする mLazyArr[pCurrNode] = null; } // 開始添字と終了添字とカレントノードを引数として、区間更新を行う internal void Internal_RangeUpdate(long pSearchStaInd, long pSearchEndInd, long pUpdateVal) { Private_RangeUpdate(pSearchStaInd, pSearchEndInd, pUpdateVal, 0); } private void Private_RangeUpdate(long pSearchStaInd, long pSearchEndInd, long pUpdateVal, 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] = pUpdateVal; LazyEval(pCurrNode); return; } // そうでなければ、2つの区間に再帰呼出し long ChildNode1 = DeriveChildNode(pCurrNode); long ChildNode2 = ChildNode1 + 1; Private_RangeUpdate(pSearchStaInd, pSearchEndInd, pUpdateVal, ChildNode1); Private_RangeUpdate(pSearchStaInd, pSearchEndInd, pUpdateVal, ChildNode2); mTreeNodeArr[pCurrNode] = mTreeNodeArr[ChildNode1] + mTreeNodeArr[ChildNode2]; } // 開始添字と終了添字とカレントノードを引数として、Sumを返す internal long Internal_Query(long pSearchStaInd, long pSearchEndInd) { return Private_Query(pSearchStaInd, pSearchEndInd, 0); } private long Private_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 = Private_Query(pSearchStaInd, pSearchEndInd, ChildNode1); long ChildVal2 = Private_Query(pSearchStaInd, pSearchEndInd, ChildNode2); return ChildVal1 + ChildVal2; } internal void DebugPrint() { for (long 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]); } } } } #endregion