개요
-
입력
첫째 줄에 나무의 개수 N (2 ≤ N ≤ 200,000)이 주어진다. 둘째 줄부터 N개의 줄에 1번 나무의 좌표부터 차례대로 주어진다. 각각의 좌표는 200,000보다 작은 자연수 또는 0이다. -
출력
문제의 정답을 1,000,000,007로 나눈 나머지를 출력한다.
접근방식
-
하나하나 다 빼서 곱해보기엔 범위가 커서 시간초과가 나므로
세그먼트 트리를 이용해야 하나 어떻게 접근해야 할지 감도 안 잡혔다. -
찾아보니 기본적으로 두 가지 세그먼트 트리를 사용한다.
구간의 나무 갯수를 저장하는 세그먼트 트리
구간의 나무 좌표의 합을 저장하는 세그먼트 트리 -
여기서 중요한건 나무를 심었을 때,
해당 좌표 왼쪽에 위치하는 나무들의 거리차와
해당 좌표 오른쪽에 위치하는 나무들의 거리차를 더한 값이 나무 심는 비용이다. -
해당 좌표의 왼쪽에 위치하는 나무들과의 거리차를 구하는 방식은
해당 좌표보다 왼쪽에 위치하는 나무들의 갯수 * 해당 좌표값 - 해당 좌표보다 왼쪽에 위치하는 나무들의 좌표합이다.
예를 들면)
이런식으로 1 2 3 좌표에 나무가 박혔고, 4좌표에 새로 박혔을 때,
총 나무의 거리합은 1,2,3 좌표에 나무가 있으므로
(4-1) + (4-2) + (4-3) 해서 4*3 - (1+2+3) 이런식이다 -
나무의 좌표가 중복으로 들어올 수 있다.
따라서 나무의 오른쪽에 나무들이 있을 수 있으므로
오른쪽 나무들과의 거리도 체크를 해야하는데,
오른쪽 나무들과의 거리는 왼쪽과 방식이 똑같다.
왼쪽과는 반대로 오른쪽에 위치한 오른쪽에 위치한 나무들의 합 -나무들의 갯수 * 해당 좌표값 이다.
예시로 보면)
(7-4) + (6-4) + (5-4) = (7+6+5) - 4*3
이런 식이다. -
이걸 알고 구현하려했지만 여러가지 간과한 문제들이 있었다.
예를 들어 원래 세그먼트트리에서 입력값을 받으면 습관적으로 firstLeafNodeIdx값을 미리 할당하고 입력값 받는 인덱스 i에 따라
segSumTree[firstLeaftNodeIdx+i] 에 저장을 하는식으로 풀었으나,
이 문제에선 이미 심은 좌표에 나무를 또 심을 수가 있다.
따라서 인덱스를 1씩 증가시켜가면서 해당 인덱스에 값을 저장하는 방식을 사용할 수 없다.
두가지 해결방식이 있는데
-
인덱스와 좌표를 매핑 시켜놓고 좌표 입력받을 시, 좌표 있는지 탐색후 해당 인덱스로 이동해서 처리
-
세그먼트 트리의 리프노드의 갯수를 좌표 최대값인 20만개로 설정 후, 좌표값 자체를 리프노드의 인덱스로 삼아 처리하기.
두번째 방식이 편해서 두번째 방식을 택했다.
-
처음으로 20만을 넘어가는 2의 제곱수는 2^18인 262144이므로 FirstLeafNodeIdx의 값은 262144이고,
세그먼트 트리의 최대 사이즈는 2^19인 524288이다.//범위가 20만이므로 20만보다 큰 2^18이 리프노드의 갯수이므로 2 ^19로 잡음 //나무의 좌표 구간 합 저장용 세그먼트 트리 long long segSumTree[524288]; //나무의 갯수 구간 합 저장용 세그먼트 트리 long long segCntTree[524288]; int N, firstLeafNodeIdx= 524288 / 2; -
좌표 값을 받을때 해당 좌표 인덱스부터 조상노드들까지 갱신시켜주는 함수를 따로 빼서 불러왔다.
void SetAnscestorNode(int n, int k) { int tmpIdx = firstLeafNodeIdx + n; //같은 자리에 나무가 심어질 수 있으므로 += 연산자 사용 segCntTree[tmpIdx]++; segSumTree[tmpIdx] += k; while (tmpIdx > 1) { tmpIdx /= 2; segCntTree[tmpIdx] = segCntTree[tmpIdx * 2] + segCntTree[tmpIdx * 2 + 1]; segSumTree[tmpIdx] = segSumTree[tmpIdx * 2] + segSumTree[tmpIdx * 2 + 1]; } }해당 좌표를 다시 입력받을 시,
segCntTree는 1만큼 더 더해주고 ,
segSumTree는 해당 좌표 인덱스의 값에 그 좌표값만큼 다시 더해줬다. -
입력값으로 받아온 각 tmp좌표에 대해
왼쪽 나무와의 거리 left를//0~i로 범위를 설정했었는데 tmp값이 이전에 나온값이 나올수도있으므로 범위도 0~tmp로 조정해야함 long long left = 1LL*(tmp) * FindCntValueInTargetRange(0, tmp, 1, 0, firstLeafNodeIdx ) - FindSumValueInTargetRange(0, tmp, 1, 0, firstLeafNodeIdx);이렇게 값*왼쪽 나무 갯수 - 왼쪽나무의 좌표합으로 구해줬고,
오른쪽 나무들과의 거리 right을//범위를 tmp+1부터 N-1까지 했었는데 리프노드 갯수 20만개로 하기로 해서 tmp+1에서 20만으로 long long right = FindSumValueInTargetRange(tmp+1, 200'000, 1, 0, firstLeafNodeIdx) - 1LL*FindCntValueInTargetRange(tmp+1, 200'000, 1, 0, firstLeafNodeIdx ) * (tmp);오른쪽 나무의 좌표합 - 값* 오른쪽나무 갯수로 구해줬다.
전체코드
#include<iostream>
using namespace std;
//범위가 20만이므로 20만보다 큰 2^18이 리프노드의 갯수이므로 2 ^19로 잡음
//나무의 좌표 구간 합 저장용 세그먼트 트리
long long segSumTree[524288];
//나무의 갯수 구간 합 저장용 세그먼트
int segCntTree[524288];
int N, firstLeafNodeIdx= 524288 / 2;
//모듈러
const int Modular = 1'000'000'007;
int FindCntValueInTargetRange(int targetL, int targetR, int nodeNum, int curL, int curR) {
if (targetR < curL || curR < targetL) return 0;
if (targetL <= curL && curR <= targetR) return segCntTree[nodeNum];
int mid = (curL + curR) / 2;
return FindCntValueInTargetRange(targetL, targetR, nodeNum*2, curL, mid) +
FindCntValueInTargetRange(targetL, targetR, nodeNum*2+1, mid + 1, curR);
}
long long FindSumValueInTargetRange(int targetL, int targetR, int nodeNum, int curL, int curR) {
if (curR < targetL || targetR < curL) return 0;
if (targetL <= curL && curR <= targetR) return segSumTree[nodeNum];
int mid = (curL + curR) / 2;
return FindSumValueInTargetRange(targetL, targetR, nodeNum*2, curL, mid) +
FindSumValueInTargetRange(targetL, targetR, nodeNum*2+1, mid + 1, curR);
}
void SetAnscestorNode(int n, int k) {
int tmpIdx = firstLeafNodeIdx + n;
//같은 자리에 나무가 심어질 수 있으므로 += 연산자 사용
segCntTree[tmpIdx]++;
segSumTree[tmpIdx] += k;
while (tmpIdx > 1) {
tmpIdx /= 2;
segCntTree[tmpIdx] = segCntTree[tmpIdx * 2] + segCntTree[tmpIdx * 2 + 1];
segSumTree[tmpIdx] = segSumTree[tmpIdx * 2] + segSumTree[tmpIdx * 2 + 1];
}
}
//원래는 리프노드 개수를 N에 비례해서 맞췄는데 이건 리프노드가 저장하는 값이 해당 좌표이다,\
이전 좌표에 나무를 또 박을 수 있어서 리프노드 인덱스와 값을 좌표로 둘다 설정해야하는데\
N에 비례해서 해버리면 N이 5인데 좌표가 20만일때 처리가 불가능하다.
void Input() {
int tmp = 0;
//Ans값을 0으로 초기화해버리니 답이 걍 계속 0나옴
int Ans = 1;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> tmp;
//0번째 값은 비용계산 안하고 세그먼트트리에만 집어넣기
if (i == 0) {
SetAnscestorNode(tmp, tmp);
continue;
}
//0~i로 범위를 설정했었는데 tmp값이 이전에 나온값이 나올수도있으므로 범위도 0~tmp로 조정해야함
long long left = 1LL*(tmp) * FindCntValueInTargetRange(0, tmp, 1, 0, firstLeafNodeIdx )
- FindSumValueInTargetRange(0, tmp, 1, 0, firstLeafNodeIdx);
//범위를 tmp+1부터 N-1까지 했었는데 리프노드 갯수 20만개로 하기로 해서 tmp+1에서 20만으로
long long right = FindSumValueInTargetRange(tmp+1, 200'000, 1, 0, firstLeafNodeIdx)
- 1LL*FindCntValueInTargetRange(tmp+1, 200'000, 1, 0, firstLeafNodeIdx ) * (tmp);
Ans = (right+left) % Modular * Ans % Modular;
// (i,tmp)로 인덱스순서대로 지정해줬는데 생각해보니 이전값이 나올수도있으므로 걍 tmp로 해야함
SetAnscestorNode(tmp, tmp);
}
cout << Ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
Input();
}문풀후생
두가지 실수로 인해 시간이 좀 많이 걸린 문제였다.
첫번째는 그냥 세그먼트트리 풀던 습관대로
시작할 때 갯수 저장하는 segCntTree를 1로 초기화를 해버린 것이였다.
SetAncestorNode함수를 호출할 때마다 이미 1로 초기화된 값들이 다 더해져서 말도 안되게 계속 큰 값이 나왔었다.
두번째로는 구간의 갯수를 구하는 FindCntValueInTargetRange함수 반환형을 int형으로 구현했더니 틀렸습니다가 뜨고 자료형을 long long으로 바꾸니 맞았다고 떠서 이해가 전혀 안 갔다.
최대 조건일때 생각해도 어차피 1씩 들어가서 값이 커봐야 20만 좀 넘는 값이 들어갈텐 데 21억을 넘는다는게 말이 안되서 머리 싸매고 고민하다가 순간 이 함수 반환형이 문제가 아닌거 아닌가 생각이 들었다.
밑을 보니 역시나
long long left = (tmp) * FindCntValueInTargetRange(0, tmp, 1, 0, firstLeafNodeIdx )
- FindSumValueInTargetRange(0, tmp, 1, 0, firstLeafNodeIdx);tmp도 int형이고, FinndCntValueInTargetRange도 int형이다.
left값과 right값 정할때 tmp값과 FindCntValueInTargetRange함수를 곱해주고 있었고, 둘다 int값이므로 여기서 int값을 벗어나는 의도치 않은 결과가 나는게 분명했다.
따라서 long long자료형을 곱해줌으로써 해결하였다.
long long left = 1LL*(tmp) * FindCntValueInTargetRange(0, tmp, 1, 0, firstLeafNodeIdx )
- FindSumValueInTargetRange(0, tmp, 1, 0, firstLeafNodeIdx);