using System; using System.Collections.Generic; using System.Linq; // https://yukicoder.me/problems/no/778 class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("6"); WillReturn.Add("3 2 1 1 2 3"); //3 3 3 3 3 3 } else if (InputPattern == "Input2") { WillReturn.Add("6"); WillReturn.Add("3 1 10 3 10 2"); //3 3 10 10 10 2 } else if (InputPattern == "Input3") { WillReturn.Add("6"); WillReturn.Add("1 3 10 1 10 2"); //1 3 10 10 10 2 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } class RangeInfoDef { internal int RangeSta; internal int RangeEnd; } static void Main() { List InputList = GetInputList(); int[] AArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray(); int LeafCnt = AArr.Length; var InsLazySegmentTree = new LazySegmentTree(LeafCnt); var RangeDict = new Dictionary(); for (int I = 0; I <= AArr.GetUpperBound(0); I++) { if (RangeDict.ContainsKey(AArr[I]) == false) { RangeDict[AArr[I]] = new RangeInfoDef(); RangeDict[AArr[I]].RangeSta = I; } RangeDict[AArr[I]].RangeEnd = I; } foreach (var EachPair in RangeDict.OrderBy(pX => pX.Key)) { InsLazySegmentTree.RangeUpdate( EachPair.Value.RangeSta, EachPair.Value.RangeEnd, EachPair.Key, 0); } var AnswerList = new List(); for (int I = 0; I <= AArr.GetUpperBound(0); I++) { int MinVal = InsLazySegmentTree.Query(I, I, 0); AnswerList.Add(MinVal); } string[] AnswerArr = Array.ConvertAll(AnswerList.ToArray(), pX => pX.ToString()); Console.WriteLine(string.Join(" ", AnswerArr)); } } // 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; } // すべての値をint.MaxValueに UB = ArrLength - 1; mTreeNodeArr = new int[UB + 1]; for (int I = 0; I <= UB; I++) { mTreeNodeArr[I] = int.MaxValue; } // 遅延配列を初期化 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; // 遅延配列の値を反映する mTreeNodeArr[pCurrNode] = mLazyArr[pCurrNode].Value; int ChildNode1 = DeriveChildNode(pCurrNode); int ChildNode2 = ChildNode1 + 1; if (ChildNode1 <= UB) { mLazyArr[ChildNode1] = mLazyArr[pCurrNode].Value; } if (ChildNode2 <= UB) { mLazyArr[ChildNode2] = mLazyArr[pCurrNode].Value; } // 伝播が終わったので、自ノードの遅延配列を空にする 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; LazyEval(pCurrNode); return; } // そうでなければ、2つの区間に再帰呼出し int ChildNode1 = DeriveChildNode(pCurrNode); int ChildNode2 = ChildNode1 + 1; RangeUpdate(pSearchStaInd, pSearchEndInd, pUpdateVal, ChildNode1); RangeUpdate(pSearchStaInd, pSearchEndInd, pUpdateVal, ChildNode2); // カレントノードの更新 mTreeNodeArr[pCurrNode] = Math.Min(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してなければ、int.MaxValue if (CurrNodeEndInd < pSearchStaInd || pSearchEndInd < CurrNodeStaInd) return int.MaxValue; // 完全に含んでいれば、このノードの値 if (pSearchStaInd <= CurrNodeStaInd && CurrNodeEndInd <= pSearchEndInd) return mTreeNodeArr[pCurrNode]; // そうでなければ、2つの子の最小値 int ChildNode1 = DeriveChildNode(pCurrNode); int ChildNode2 = ChildNode1 + 1; int ChildVal1 = Query(pSearchStaInd, pSearchEndInd, ChildNode1); int ChildVal2 = Query(pSearchStaInd, pSearchEndInd, ChildNode2); return Math.Min(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]); } } } }