Approach 현대대수나 집합론에서 다루는 것처럼, 연산 자체를 잘 정의해주면 된다. 궁극적으로 이 문제가 naive하게 풀기 어려운 이유는 본질적으로 연산을 함에 있어 덧셈과 곱셈 중 곱셈의 우선순위가 더 높기 때문이다. 잘 생각해보면 본질적으로 더하고 곱하는 연산은 다음과 같이 정의할 수 있다. f : R X R X R |-> R 이다. 즉 예를 들어서 기존에 가지고 있는 값을 x, 곱하는 수를 y, 더하는 수를 z라고 하면 x * y + z로 나타낼 수 있는데, 궁극적으로 3개의 실수값을 1개의 실수값으로 대응시키는 함수를 통과시켰다고 할 수 있다. 이를 좀 단순하게 표현하면 $f_{a, b}(c)$ 이런 형식으로 표현할 수 있을 것이다. 그렇다면, 연산을 여러번 적용한다는 의미는 합성함수를 정의..

Approach https://viyoung.tistory.com/406 [백준 2820번] [Lazy propagation / Euler Tour] 자동차 공장 Approach https://viyoung.tistory.com/400 [백준 14268번] [오일러 투어 테크닉 / Lazy propagation] 회사 문화 2 Approach 상사가 칭찬을 받으면 해당 상사 밑에 위치한 부하들이 전부 다 칭찬을 받는 구조이다.. viyoung.tistory.com Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; using ll = long long; using pii = pair; using tiii = tu..

Approach https://viyoung.tistory.com/400 [백준 14268번] [오일러 투어 테크닉 / Lazy propagation] 회사 문화 2 Approach 상사가 칭찬을 받으면 해당 상사 밑에 위치한 부하들이 전부 다 칭찬을 받는 구조이다. 좀만 생각해보면, 직급 관계는 트리 구조를 활용하여서 표현할 수 있고 해당 노드를 기준으로 아래 viyoung.tistory.com 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[4] = {-1, 1, 0, 0}; in..

Approach 구간에 대한 정보를 변경하는 쿼리와 구간에 대한 질의를 하고 있는 쿼리를 보내고 있는 상황이므로, Lazy propagation임은 쉽게 파악할 수 있었을 것이다. 그러면, lazy를 어떻게 정의할 것인지를 파악하는 것이 중요할 것이다. 아이디어 자체는 이 문제와 상당히 유사하다. https://viyoung.tistory.com/399 [백준 12844번] [Lazy propagation] XOR Approach 문제를 보자마자 구간에 대한 정보를 계속해서 업데이트 하는 상황이므로 Lazy propagation 문제임은 직관적으로 잘 파악했을 것이다. 하지만, 기본적인 합 세그와 달리 XOR 연산을 처리하는 viyoung.tistory.com 이 문제도 XOR의 성질을 활용하여 XOR을..

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 구간에 대한 정보를 업데이트를 하는 상황이므로 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..