PS/Segment Tree(2)
-
BOJ 17353 : 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별
https://www.acmicpc.net/problem/17353 17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순 www.acmicpc.net 재밌는 문제이다. 우리는 느낌상 레이지 세그를 생각할 수 있지만, 더하는 값이 등차수열이기에 어떻게 해야할지 고민해봐야 한다. 이때, 우리는 인접한 두 배열 원소의 차이를 세그트리 원소로 하여 생각해보면, 결국 등차수열로 더하는게 어떤 구간 전체에 1을 더하는 것이랑 동치가 된다. 이때 두 원소의 차이를 저장하는 세그먼트 트리이기 때문에 구간의 마지막 원소를..
2021.08.17 -
BOJ 11505 : 구간 곱 구하기
우리는 세그먼트 트리를 이용하여 쉽게 구할 수 있다. 구간 합 세그트리를 구현 할 줄 안다면 쉽게 구현이 가능하다. #include #define sanic ios_base::sync_with_stdio(0); #define MEM 4000004 using namespace std; typedef long long ll; const ll MOD = 1e9+7; ll n,m,k; ll tree[MEM], a[MEM]; ll init(int idx, int l, int r){ if(l==r) return tree[idx] = a[l]; int mid=(l+r)/2; return tree[idx] = ((init(idx*2, l, mid)%MOD)*(init(idx*2+1, mid+1, r)%MOD))%MOD..
2020.05.31