[BOJ-JS] 6213번 - Balanced Lineup

6213번: Balanced Lineup (acmicpc.net)

6213번: Balanced Lineup

 

이 문제는 세그먼트 트리를 활용해서 최대, 최소값을 찾는 문제를 풀었다면 사실상 같은 문제다.

세그트리 문제가 골1이므로 난이도 기여에 골1을 주었다.

init=(a,t,n,s,e)=>{
  if(s==e)t[n]=[a[s],a[s]]
  else{
    init(a,t,n*2,s,Math.floor((s+e)/2))
    init(a,t,n*2+1,Math.floor((s+e)/2)+1,e)
    t[n]=[Math.min(t[n*2][0],t[n*2+1][0]),Math.max(t[n*2][1],t[n*2+1][1])]
  }
}
query=(t,n,s,e,l,r)=>{
  if(l>e||r<s)return [1e10,-1]
  if(l<=s&&e<=r)return t[n]
  let ls=query(t,n*2,s,Math.floor((s+e)/2),l,r)
  let rs=query(t,n*2+1,Math.floor((s+e)/2)+1,e,l,r)
  return [Math.min(ls[0],rs[0]),Math.max(ls[1],rs[1])]
}
z=(0+require('fs').readFileSync(0)).split`
`;
[n,m]=z[0].split` `.map(i=>+i)
a=z.slice(1,n+1).map(i=>+i)
h=Math.ceil(Math.log(n)/Math.log(2))
ts=1<<(h+1)
t=Array(ts).fill(0)
init(a,t,1,0,n-1)
s=[]
for(i=0;i<m;i++){
  [t1,t2]=z[n+1+i].split` `;
  [x,y]=query(t,1,0,n-1,t1-1,t2-1)
  s.push(y-x)
}
console.log(s.join`\n`)