Approach 구간에 대한 정보를 업데이트를 하는 상황이므로 Lazy propagation임은 쉽게 파악할 수 있었을 것이다. 문제 출제 범위에 대해서는 쉽게 파악이 가능하지만, 가장 껄끄러운 지점은 구간에 대한 정보가 업데이트 될 때 각 위치 별로 업데이트 되는 양이 다르다는 것이다. 즉 이러한 문제점으로 인해 세그먼트 트리의 update과정에서 공통된 연산을 정의할 수 없게 된다. 즉. 이 문제를 Lazy propagation으로 풀기 위해서는 이 문제에서 각 위치 별로 업데이트 되는 양이 달라서 발생하는 문제점을 해결해주면 된다. 잘 생각해보면 업데이트 되는 정도가 1씩 증가하는 양상을 볼 수 있다. 즉 차이가 일정하다. "차이가 일정하다는 것을 활용해서 업데이트 되는 것을 정의할 수 없을까"라는..

Approach 부하들이 칭찬을 받는 경우는 https://viyoung.tistory.com/400를 참고하면 된다. [백준 14268번] [오일러 투어 테크닉 / Lazy propagation] 회사 문화 2 Approach 상사가 칭찬을 받으면 해당 상사 밑에 위치한 부하들이 전부 다 칭찬을 받는 구조이다. 좀만 생각해보면, 직급 관계는 트리 구조를 활용하여서 표현할 수 있고 해당 노드를 기준으로 아래 viyoung.tistory.com 하지만, 이 문제의 경우 상사 방향쪽으로도 칭찬이 업데이트 되어야 한다는 점에서 차이가 존재한다. 잘 생각해보면, 오일러 투어 테크닉을 통해 자식들의 범위를 알 수 있다. 예를 들어 오일러 투어 결과 dfs_in과 dfs_out이 각각 1, 5라고 하면, 자신을 포..

Approach 상사가 칭찬을 받으면 해당 상사 밑에 위치한 부하들이 전부 다 칭찬을 받는 구조이다. 좀만 생각해보면, 직급 관계는 트리 구조를 활용하여서 표현할 수 있고 해당 노드를 기준으로 아래 있는 모든 노드들에 영향을 준다는 점에서 오일러 투어 테크닉 기법을 생각할 수 있다. 추가적으로 구간에 대한 정보를 업데이트를 하기 위한 자료구조가 필요한데, Lazy propagation이 가장 적합하다는 것은 쉽게 떠올릴 수 있을 것이다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; using ll = long long; using pii = pair; using tiii = tuple; int move_x..

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번째 위치에 놓인 점의 이동 횟수를 구하는 시점에 자신보다 숫자가 큰 것의 개수만..