Approach Inversion counting임을 파악하고 병합정렬을 활용해서 풀어줄 수도 있다. 잘 생각해보면, B의 i번째 위치에 놓인 점에 의해 교차점이 발생하는 횟수는 자기보다 먼저 대응된 것 중에 자신보다 큰 것의 개수와 같다. 이렇게 되면, i번째 위치에 놓인 점의 이동 횟수를 구하는 시점에 자신보다 숫자가 큰 것의 개수만 구한 것과 B의 i ~ inf번째 위치에 놓인 것 중 대응된 것의 개수를 구하는 것이 동치가 된다. 예를 들어, a의 i번쨰 수가 B에 대응되는 index가 $b_{a_i}$라고 할 떄, 결과적으로 해당 선에 의해 교차점이 생기는 상황은 $b_{a_i}$부터 50000(inf) 위치 사이에 놓인 대응된 점의 개수와 동치이다. https://viyoung.tistory.c..

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

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 위 문제와 본질적으로 거의 비슷하다. 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 = ..