[BOJ-JS] 12844번 - XOR

12844번: XOR (acmicpc.net)

12844번: XOR

 

느리게 갱신되는 세그트리 기본 문제중 하나. 아래 페이지에 잘 설명되어 있다.

느리게 갱신되는 세그먼트 트리 (acmicpc.net)

느리게 갱신되는 세그먼트 트리

이 문제를 풀 때 필요한 아이디어 중에 하나는 여러 숫자들을 xor하는 과정에서 불필요한 연산을 줄이는 것. 구간 XOR 값을 업데이트 할때 같은 숫자를 여러 번 xor하는 일이 벌어질텐데, 이때 a ^ a = 0, a ^ 0 = a가 된다는 사실을 활용해서, a를 짝수개 xor 해야 한다면 0을, 홀수개 xor 해야 한다면 a를 리턴하는 식으로 줄여놓으면 된다.

 

구간 합에 사용한 tree[node] += (end-start+1)*lazy[node]; 부분을 tree[node] ^= ((end-start+1)%2)*lazy[node]; 이렇게 수정한다고 생각하면 된다.

 

lazy propagation 기본 문제의 난이도가 플4로 책정되어 있는데, 위의 아이디어가 더해져서 플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,+t2))
  else update_range(t,lz,1,0,n-1,+t1,+t2,+t3)
}
console.log(s.join('\n'))