인간승리

삽질하던 도중 깨달음을 얻고 코드를 갈아엎고 AC.. 수쿼26보다 훨씬 직관적이었지만 그 내용은 훨씬 어려웠다.

 

간단히 풀이를 적자면, OR쿼리에서 k의 켜진 i번째 비트에 대해 구간의 i번째 비트가 모두 꺼져있을 때만 갱신하면 된다. AND쿼리도 비슷하다.

 

나는 세그트리에 max, or, and값을 저장하고 풀려고 했는데, or과 and 대신 그냥 구간 내에서 모두 켜진 비트와 꺼진 비트들을 저장하는 것이 편할 것 같아서 그렇게 했다. 사실 별 차이는 없고, 코드에 대한 가독성이 이게 훨씬 좋아서 디버깅에도 도움이 많이 되고 그랬다.. or과 and를 쓰는 코드를 다시 보니, 헷갈려서 잘못 쓴 부분들이 많았다. 나는 스도 코드(pseudo code)를 잘 쓰지 않는 습관이 있고, 이게 독이 되었다. 코드를 쓰기 전 노트에 확실하게 정리하는 습관을 들이도록 노력해야겠다(고 다짐을 벌써 수십번째 하는 듯)

 

아 그리고 시간복잡도는 (수쿼 26처럼) 노드들이 합쳐지기 때문에 많아봤자 O(20N)정도만 일어나게 된다.