늒네 기록

[BOJ-JS] 14245번 - XOR 본문

알골 공부 기록/BOJ

[BOJ-JS] 14245번 - XOR

jaeha lee 2024. 3. 11. 21:28

14245번: XOR (acmicpc.net)

 

14245번: XOR

첫 번째 줄에 수열의 크기 n (0 < n ≤ 500,000)이 주어진다. 두 번째 줄에 수열의 원소가 0번부터 n - 1번까지 차례대로 주어진다. 수열의 원소는 100,000보다 크지 않은 음이 아닌 정수이다. 세 번째 줄

www.acmicpc.net

이 문제는 이전 포스팅과 같은 방식으로 풀면 된다.

[BOJ-JS] 12844번 - XOR (tistory.com)

 

[BOJ-JS] 12844번 - XOR

12844번: XOR (acmicpc.net) 12844번: XOR 크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한

jaehaaheaj.tistory.com

이전 문제를 플3으로 기여를 했기 때문에 이 문제도 플3으로 기여.

init=(a,t,n,s,e)=>{
  if(s==e)t[n]=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]=t[n*2]^t[n*2+1]
  }
}
update_lazy=(t,lz,n,s,e)=>{
  if(lz[n]!=0){
    t[n]^=((e-s+1)%2)*lz[n]
    if(s!=e){
      lz[n*2]^=lz[n]
      lz[n*2+1]^=lz[n]
    }
    lz[n]=0
  }
}
update_range=(t,lz,n,s,e,l,r,d)=>{
  update_lazy(t,lz,n,s,e)
  if(l>e||r<s)return
  if(l<=s&&e<=r){
    t[n]^=((e-s+1)%2)*d
    if(s!=e){
      lz[n*2]^=d
      lz[n*2+1]^=d
    }
    return
  }
  update_range(t,lz,n*2,s,Math.floor((s+e)/2),l,r,d)
  update_range(t,lz,n*2+1,Math.floor((s+e)/2)+1,e,l,r,d)
  t[n]=t[n*2]^t[n*2+1]
}
query=(t,lz,n,s,e,l,r)=>{
  update_lazy(t,lz,n,s,e)
  if(l>e||r<s)return 0
  if(l<=s&&e<=r)return t[n]
  let ls=query(t,lz,n*2,s,Math.floor((s+e)/2),l,r)
  let rs=query(t,lz,n*2+1,Math.floor((s+e)/2)+1,e,l,r)
  return ls^rs
}
z=(0+require('fs').readFileSync(0)).split`
`;
n=+z[0]
a=z[1].split` `.map(i=>+i)
h=Math.ceil(Math.log(n)/Math.log(2))
ts=1<<(h+1)
t=Array(ts).fill(0)
lz=Array(ts).fill(0)
m=+z[2]
init(a,t,1,0,n-1)
s=[]
for(i=0;i<m;i++){
  [w,t1,t2,t3]=z[3+i].split` `
  if(w-1)s.push(query(t,lz,1,0,n-1,+t1,+t1))
  else update_range(t,lz,1,0,n-1,+t1,+t2,+t3)
}
console.log(s.join('\n'))
반응형

'알골 공부 기록 > BOJ' 카테고리의 다른 글

[BOJ-JS] 10569번 - 다면체  (0) 2024.03.24
[BOJ-JS] 28113번 - 정보섬의 대중교통  (0) 2024.03.21
[BOJ-JS] 2556번 - 별 찍기 - 14  (0) 2024.03.10
[BOJ-JS] 1274번 - 커피숍1  (0) 2024.03.09
[BOJ-JS] 12844번 - XOR  (0) 2024.03.08
'알골 공부 기록/BOJ' Related Articles more
Comments