Approach 문제를 보자마자 구간에 대한 정보를 계속해서 업데이트 하는 상황이므로 Lazy propagation 문제임은 직관적으로 잘 파악했을 것이다. 하지만, 기본적인 합 세그와 달리 XOR 연산을 처리하는 세그이므로 XOR 연산의 성질을 잘 생각해볼 필요가 있다. a XOR 0 = a b XOR b = 0 a XOR b XOR c = (a XOR b) XOR c = a XOR (b XOR c) : associative 위 성질을 이용하면, 구간 [a, b]에 c를 xor연산을 하게 되면 seg[node] XOR (c * ((b - a + 1) % 2)))와 같다는 것을 쉽게 파악할 수 있다. 왜냐하면 c를 짝수면 XOR처리를 하게 되면 결과적으로 0과 XOR 연산을 하는 것과 같아지고, 홀수면 ..

Approach 단순히 세그먼트 트리로 구간에 대한 정보를 모두 처리하게 되면, 업데이트마다 MlgN만큼이 필요하게 된다. (단, M은 b ~ c 사이의 개수) 최악의 경우 NlgN이 필요하다. 따라서 단순히 세그먼트 트리로 이 문제를 해결할 경우 O(NKlgN) = 1000000 * 10000 * log10000이므로 무조건 시간 초과를 받게 된다. 위와 같은 상황에서 사용할 수 있는 자료구조가 Lazy propagation이다. 해당하는 자료는 다음을 참고하도록 하자. https://m.blog.naver.com/kdr06006/221818523719 세그먼트 트리 with Lazy Propagation 안녕하세요. 오늘은 lazy propagation에 대해 공부해보겠습니다. 세그먼트 트리에 laz..

Approach 일반적인 세그 유형과는 살짝 차이가 있다. 잘 생각해보면 쿼리를 지속적으로 처리해야한다는 점에서 세그먼트 트리 자료구조를 활용하는 것이 유리하다고 판단하는 것까지는 쉽게 생각할 수 있다. 하지만, 일반적인 쿼리 문제와 달리 특정 index에 대한 값을 업데이트하고 구간에 대한 정보를 묻는 것이 아니라 구간에 대한 정보를 업데이트하고, 특정 index에 대한 정보를 묻는다는 점에서 차이가 존재한다. 잘 생각해보면, 세그먼트 트리의 하나의 노드에서 구간에 대한 정보를 가지고 있으므로 정확히 특정 구간이 원하는 구간 안에 정확이 들어왔을 경우에만 업데이트해주면 된다. 특정 index에 대한 정보는 해당 구간 index를 포함하고 있는 모든 노드값들에 대해 값을 더해주면 된다. Code #inc..

Approach 처음에는 세그먼트 트리 + 이분탐색으로 접근하여서 TLE가 나왔다. T가 2인 쿼리가 들어오면 결과적으로 k번째 수를 찾아야 한다. 잘 생각해보면 이는 이분탐색으로 구할 수 있음을 쉽게 알 수 있다. 예를 들어, a라는 숫자가 k번째 수라고 가정했을 경우에는 1 ~ a - 1까지에 값에 존재하는 수는 k 미만이고, a이상의 수에 대해서는 k 이상이므로 구획이 정확하게 분할되게 된다. 따라서 이를 이분탐색을 활용해서 풀기 위해서는 1 ~ i까지에 존재하는 수의 개수만 관리해주면 된다. 여기까지 오면, prefix_sum을 생각할 수도 있고 segment tree를 생각할 수도 있다. 하지만, T가 1일때 값을 바꿔줘야하는 부분도 있기 때문에 segment tree를 사용하는 것이 더 유리하..

Approach 위 문제와 본질적으로 거의 비슷하다. https://viyoung.tistory.com/257 [백준 5419번] [세그먼트 트리 / 좌표 압축 / 스위핑] 북서풍 Approach 본질적으로 위 문제와 접근방법이 완전히 동일하다. https://viyoung.tistory.com/393 [백준 2336번] [세그먼트 트리 / 스위핑] 굉장한 학생 Approach 상당히 재밌는 문제이다. 문제를 요약하자면, 3개.. viyoung.tistory.com 잘 생각해보면, i번째 위치에 놓인 점이 정렬되기 위해서 움직여야 하는 횟수는 자기보다 앞에 앞에 있는 것 중에 자신보다 큰 것의 개수와 같다. 이렇게 되면, i번째 위치에 놓인 점의 이동 횟수를 구하는 시점에 자신보다 숫자가 큰 것의 개수만..

Approach 본질적으로 위 문제와 접근방법이 완전히 동일하다. https://viyoung.tistory.com/393 [백준 2336번] [세그먼트 트리 / 스위핑] 굉장한 학생 Approach 상당히 재밌는 문제이다. 문제를 요약하자면, 3개의 시험에 대해서 모두 다 우월한 학생이 있는지를 판단하는 것이 굉장히 중요하다. 일단 첫번째 시험을 기준으로 오름차순으로 정렬을 viyoung.tistory.com 기본적으로 특정 점에 데헤 차례차례 update하면서 세그먼트 트리에 쿼리를 날리게 되면, 2가지 기준에 대해서 동시에 처리할 수 있는 테크닉에 대해서 잘 알아두도록 하자. 추가적으로 이 문제는 북서풍을 타고 이동하는 것이지만, 북서풍쪽으로 이동할 수 있는 섬을 찾아도 괜찮다. 따라서, x축 기준..

Approach 전체 수의 크기가 65536정도밖에 안되는 상황이므로, k개의 숫자들 중 해당 숫자보다 작은 수의 개수를 질의하는 쿼리를 빠르게 응답해주면 된다. 잘 생각해보면 세그먼트 트리로 쉽게 구할 수 있다는 것을 알 수 있다. 또한 슬라이딩 윈도우 느낌으로 빠지는 부분은 -1, 들어오는 부분은 +1하는 방식으로 update해주면 된다. 추가적으로 위 방식대로 진행하게 되면 0 ~ 특정한 수까지 고려했을 때의 개수가 중앙값 보다 작은 경우와 그렇지 않은 경우가 이분법적으로 갈리게 되므로 이분탐색으로 중앙값을 쉽게 도출할 수 있게 된다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; using ll = ..

Approach 상당히 재밌는 문제이다. 문제를 요약하자면, 3개의 시험에 대해서 모두 다 우월한 학생이 있는지를 판단하는 것이 굉장히 중요하다. 일단 첫번째 시험을 기준으로 오름차순으로 정렬을 한다. 정렬된 결과에서 앞에 위치하는 학생은 적어도 첫번째 시험을 더 잘 본 것이므로, 해당 학생보다 뒤에 위치하는 학생은 굉장한 학생한 학생을 판단하는 과정에서 고려하지 않아도 된다. 따라서 첫 시험을 기준으로 정렬을 한 뒤, 해당 학생의 앞에 있는 학생 중 2, 3번째 시험을 모두 더 잘 본 학생이 없다면 해당 학생은 굉장한 학생이라고 판단해주면 된다. 따라서, 이 문제를 풀기 위해서 실질적으로 해결해야하는 부분은 "해당 학생의 앞에 있는 학생 중 2, 3번째 시험을 모두 더 잘 본 사람이 있는지 여부"이다...