201902 썸네일형 리스트형 BOJ(백준) 3653 - 영화 수집 ★ 아이디어처음에 query를 이용해서 간단히 구간합을 뽑을 수는 있는데, 그 이후가 쉽지 않다. DVD를 뽑아서 맨 위로 올리는 것을 어떤 식으로 표현할 것인가?? 처음에는 또 인덱스 및 구간에다가 합을 부여하고 싶다. lazy propergation 같은 아이디어가 떠올랐는데, 그때마다 항상 0과 1, 리프노드를 잘 활용하는 아이디어가 필요했다. 세그먼트트리의 리프를 N + M만큼으로 구성하는 아이디어가 필요하다. N = 8, M = 3이면 0 0 0 1 2 3 4 5 6 7 8 더보기 BOJ(백준) 3006 - 터보소트 ★ 아이디어index자체를 바꾸려면 시간이 엄청 걸린다. 구간에다가 합을 부여하고 싶은 생각이 든다. lazy propergation이 떠오르긴 하는데, 그것말고 또 다른 아이디어가 있을까 찾다가, 바꾸는 횟수를 카운트 = 리프노드가 1인 세그먼트트리로 구간합을 구하는 아이디어 이것을 떠올리면 간단해진다. https://github.com/jongwuner/Algorithm/blob/master/BOJ/3006.cpp 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include#include#includeusing namespace std;typedef pair Pair;int N, segSize .. 더보기 BOJ(백준) 12837 - 가계부(Hard) 아이디어 기본적인 세그먼트트리 구현문제. update 시 편차를 더해주거나 빼주거나 하는 것 빼곤 특별한 것이 없다. https://github.com/jongwuner/Algorithm/blob/master/BOJ/12837.cpp 12345678910111213141516171819202122232425262728293031323334353637383940#include#includeusing namespace std;typedef long long ll;vector seg;int segSize = 1, N, M;void update(int idx, ll val) { idx += segSize; seg[idx] += val; while (idx > 1) { idx /= 2; seg[idx] = seg.. 더보기 이전 1 다음
