BaaaaaaaarkingDog
코딩, 해킹
[BOJ] 13925번: 수열과 쿼리 13

https://www.acmicpc.net/problem/13925

 

Segment Tree의 lazy propagation 문제인데 각 노드는 자신이 담당하는 구간의 원소의 합(코드에서의 변수 $seg$)과 더불어 $a \times seg[node] + b$로 업데이트를 하면 된다는 것을 나타내는 $a, b$(코드에서의 변수 $lazy1, lazy2$를 들고 있으면 됩니다.

 

https://github.com/blisstoner/BOJ/blob/master/13925.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 16685번: XOR 포커  (0) 2019.09.12
[BOJ] 11191번: XOR Maximization  (0) 2019.09.12
[BOJ] 4798번: Dirichlet's Theorem  (0) 2019.09.11
[BOJ] 13925번: 수열과 쿼리 13  (0) 2019.09.09
[BOJ] 14897번: 서로 다른 수와 쿼리 1  (0) 2019.09.08
[BOJ] 17373번: 녜힁  (0) 2019.09.07
[BOJ] 16765번: Teamwork  (0) 2019.08.09
  Comments
댓글 쓰기
[BOJ] 14897번: 서로 다른 수와 쿼리 1

https://www.acmicpc.net/problem/14897

 

직관적으로는 Mo's algorithm으로 해결할 수 있고, merge sort tree 혹은 persistent segment tree로도 해결할 수 있다고 합니다.(https://www.acmicpc.net/board/view/40731)

 

저는 Mo's algorithm으로 해결했습니다.

 

https://github.com/blisstoner/BOJ/blob/master/14897.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 11191번: XOR Maximization  (0) 2019.09.12
[BOJ] 4798번: Dirichlet's Theorem  (0) 2019.09.11
[BOJ] 13925번: 수열과 쿼리 13  (0) 2019.09.09
[BOJ] 14897번: 서로 다른 수와 쿼리 1  (0) 2019.09.08
[BOJ] 17373번: 녜힁  (0) 2019.09.07
[BOJ] 16765번: Teamwork  (0) 2019.08.09
[BOJ] 16764번: Cowpatibility  (0) 2019.08.09
  Comments
댓글 쓰기
[BOJ] 17373번: 녜힁

https://www.acmicpc.net/problem/17373

 

쿼리를 정렬하지 않을 경우 PST로, 정렬할 경우 그냥 일반 세그먼트 트리로 해결 가능합니다. 저는 PST로 풀이했습니다. 역시 구현은 쉽지 않네요.

 

https://github.com/blisstoner/BOJ/blob/master/17373.cpp

 

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 4798번: Dirichlet's Theorem  (0) 2019.09.11
[BOJ] 13925번: 수열과 쿼리 13  (0) 2019.09.09
[BOJ] 14897번: 서로 다른 수와 쿼리 1  (0) 2019.09.08
[BOJ] 17373번: 녜힁  (0) 2019.09.07
[BOJ] 16765번: Teamwork  (0) 2019.08.09
[BOJ] 16764번: Cowpatibility  (0) 2019.08.09
[BOJ] 16763번: Fine Dining  (0) 2019.08.08
  Comments
댓글 쓰기