Baekjoon Online Judge/세그먼트 트리4 1395 스위치 with Lazy Propagation Lazy Propagation으로 구간 합 구하기 2를 풀고 바로 다음 문제로 넘어갔다. 처음에는 모두 꺼져있고 구간이 주어질 때 키고 끄고를 반복하여 구간 내 켜져있는 스위치의 개수를 출력하는 문제이다. 스위치를 두 번 키면 결국 같은 상태가 된다. 따라서 홀수일때만 노드의 값을 변경해주면 된다. 처음 그냥 구간내 개수로 변경하면 되겠지 했다가 다른 구간에서 변경이 되는 경우도 있으므로 구간 개수에서 현재 노드의 값을 빼줘야하는 것을 뒤늦게 알게 되었다. void update_lazy(int idx, int l, int r) { if (lazy[idx] != 0) { if (lazy[idx] % 2) seg[idx] = (r * 1LL - l + 1) - seg[idx]; if (l != r) { la.. 2020. 4. 2. 10999 구간 합 구하기 2 with Lazy Propagation 2차원 세그먼트 트리까지 공부를 하고 Lazy Propagation을 배우게 되었다. 직역하면 게으른 전파라는 소리이다. 이것을 쓰는 이유는 구간 전체를 변경할 때 빠르게 구하기 위해서이다. 기존 세그먼트 트리에서 Update를 할 때 한 점을 갱신한다. 왼쪽 오른쪽 구간을 나누고 구간 안에 속해있으면 탐색을 안 하기 위해서 세그먼트 트리를 쓰는 것인데 구간 전체를 변경하게 된다면 결국 각각의 점을 들어가서 변경을 해야 한다. 이러한 비효율적인 일을 막기 위해서 변경은 나중에 방문을 할 경우 한 번에 하고 변경되는 값을 따른 배열에 모아놓는 것이다. 자세한 구현법은 코드와 함께 정리하겠다. 1. 먼저 세그먼트 트리와 똑같은 크기의 Lazy 배열을 만든다. 2. 그리고 기본적인 세그먼트 트리와 똑같이 구현.. 2020. 4. 2. 11658번 구간 합 구하기 3 2차원 세그먼트 트리나 펜윅 트리를 이용한 문제이다. (x1, y1)부터 (x2, y2)까지의 합을 많은 수의 쿼리가 주어졌을 때 결과를 출력해야 한다. 펜윅 트리는 아직 안 배워서 2차원 세그먼트 트리를 이용해서 풀게 되었다. 처음 2차원 세그먼트 트리를 만들 때 어떻게 해야 할지 고민하다가 단순히 4 사분면처럼 쿼드 트리를 만들어서 구현을 해봤다. 시간 초과 소스코드 더보기 #include #define all(v) v.begin(), v.end() #define pb push_back #define fu(i,a,j) for(int i=a;i=j;i--) #define SYNC ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL) #define MOD .. 2020. 4. 2. 12899번 데이터 구조 세그먼트 트리를 응용한 문제이다. 이제 막 세그먼트 트리를 공부해서 처음엔 추가하는 것도 어려웠다. 추가하는 것은 set을 써도 가능하지만 세그먼트 트리를 공부하기 위한 것이니까 안 하고 고민을 해봤다. 그냥 세그먼트 트리에서 미리 다 만들어져 있다고 가정하고 일반적으로 Update 하듯이 값을 수정해주면 되었다. 그리고 값을 수정한 뒤 X번째로 작은 수를 찾아야 하는데 이 방법을 몰라서 세그먼트 트리를 다시 공부하였다. 결국 방법은 트리 구조에서 마지막번째 레벨의 노드가 1~2000000까지 있게 만들었으므로 K번째 노드가 수 K를 나타내는 것으로 나타낼 수 있다. 그래서 각 노드의 값을 그 수의 개수로 입력하고 세그먼트 트리로 개수들의 합을 저장한다. K 번째 수는 결국 왼쪽에 K개가 있으면 그 노드.. 2020. 4. 2. 이전 1 다음
