이진 탐색 트리를 그냥 구현하면 당연히 TLE를 받습니다.
플래티넘 5에 이렇게 단순한 구현을 시킬 일은 없습니다.
이진 탐색 트리를 만들었다고 가정하고, 이를 아래로 눌러 일렬로 만들어봅시다.
이 그림에서 잘 살펴보다 보면, 각 노드의 부모는 일렬로 만든 상태에서 각 노드에 인접해있고, 인접한 노드 중 깊이가 깊은 노드임을 알 수 있습니다.
따라서 배열을 항상 정렬된 상태로 유지하고 노드를 삽입할 때 인접한 칸의 깊이를 빠르게 알 수 있다면, 문제를 해결할 수 있는 것입니다.
문제는, vector나 list 등 stl의 기본 컨테이너에서는 이러한 기능을 빠르게 수행할 수 없다는 것입니다.
하지만 값의 범위가 1~N으로 정해져 있으므로 세그먼트 트리를 통해 해결 가능합니다.
#include<bits/stdc++.h>
using namespace std;
struct node{
int lo,hi;
node(int l=0,int h=0):lo(l),hi(h){}
} seg[300010<<2];
int dep[300010];
node f(node a,node b){
return node(min(a.lo,b.lo),max(a.hi,b.hi));
}
void upd(int idx,int l,int r,int p,int v){
if(l>p||r<p)return;
if(l==r){
seg[idx]={v,v};
return;
}
int m=l+r>>1,le=idx<<1,ri=le|1;
upd(le,l,m,p,v);upd(ri,m+1,r,p,v);
seg[idx]=f(seg[le],seg[ri]);
}
node query(int idx,int l,int r,int s,int e){
if(l>e||r<s)return node(1000000000,-1000000000);
if(s<=l&&r<=e)return seg[idx];
int m=l+r>>1,le=idx<<1,ri=le|1;
return f(query(le,l,m,s,e),query(ri,m+1,r,s,e));
}
int main(void){
ios::sync_with_stdio(0);cin.tie(0);
fill(seg,seg+(300010<<2),node(1000000000,-1000000000));
int n;
cin>>n;
long long res=0;
{
int x;
cin>>x;
dep[x]=0;
upd(1,1,n,x,x);
cout<<"0\n";
}
for(int i=1;i<n;i++){
int x;
cin>>x;
node l=query(1,1,n,1,x);
node r=query(1,1,n,x,n);
if(1<=l.hi&&l.hi<=n)dep[x]=max(dep[x],dep[l.hi]);
if(1<=r.lo&&r.lo<=n)dep[x]=max(dep[x],dep[r.lo]);
dep[x]++;
res+=dep[x];
upd(1,1,n,x,x);
cout<<res<<"\n";
}
}