#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include//assert(); //#include //xAOJ ///////// #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define P(p) cout<<(p)< ///////// typedef long long LL; typedef long double LD; typedef unsigned long long ULL; ///////// using namespace::std; ///////// ///////// void solve(){ int N; cin >> N; vector data(N); vector uni(N); for(int i=0;i> data[i]; uni[i] = data[i]; } // /*int N = 100000; vector data(N); for(int i=0;i::iterator it,endit,start; it = uni.begin(); endit = uni.end(); vector< vector > list( uni.size() ); int uSize = uni.size(); int temp; int Pos; for(int i=0;i pTemp,Atemp[2]; bool Aflag[2]; pTemp.first = 0; pTemp.second = N-1; vector< pair > hani; hani.push_back( pTemp ); vector< pair >::iterator pIt,pEnd; for(int i=uSize-1;i>=0; --i){ ter = uni[i]; sPos = *(list[i].begin()); ePos = *(list[i].end()-1); pIt = hani.begin(); pEnd = hani.end(); while( sPos <= ePos && pIt != hani.end() ){ if( ePos < pIt->first ) break; if( pIt->second < sPos ){ ++pIt; continue; } int A,B; A = max( sPos,pIt->first ); B = min( ePos,pIt->second ); Aflag[0] = false; Aflag[1] = false; for(int j=A;j<=B;++j){ data[j] = ter; } if( pIt->first != A ){ Atemp[0].first = pIt->first; Atemp[0].second = A-1; Aflag[0] = true; } if( pIt->second != B ){ Atemp[1].first = B+1; Atemp[1].second = pIt->second; Aflag[1] = true; } sPos = pIt->second + 1; hani.erase( pIt ); for(int j=0;j<2;++j){ if( Aflag[j] ){ hani.push_back( Atemp[j] ); } } sort( hani.begin(), hani.end() ); pIt = hani.begin(); } } //結果表示 cout << data[0]; for(int i=1;i