백준 1280 나무 심기 풀이

문제

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

&Title
1280번 - 나무 심기

&Question
1번부터 N번까지 번호가 매겨져 있는 N개의 나무가 있다. 
i번 나무는 좌표 X[i]에 심어질 것이다.동호는 나무를 1번 나무부터 
차례대로 좌표 X[i]에 심으려고 한다. 1번 나무를 심는 비용은 
없고, 각각의 나무를 심는데 드는 비용은 현재 심어져있는 모든 
나무 까지 거리의 합이다. 만약 3번 나무를 심는다면, 1번 
나무와의 거리 + 2번 나무와의 거리가 3번 나무를 심는데 
드는 비용이다.2번 나무부터 N번 나무까지를 심는 비용의 곱을 출력하는 
프로그램을 작성하시오. 

&Input
첫째 줄에 나무의 개수 N (2 ≤ N 
≤ 200,000)이 주어진다. 둘째 줄부터 N개의 줄에 1번 나무의 
좌표부터 차례대로 주어진다. 각각의 좌표는 200,000보다 작은 자연수 또는 
0이다. 

&Output
문제의 정답을 1,000,000,007로 나눈 나머지를 출력한다. 

&Example
-input
5
3
4
5
6
7

-output
180

요약

• 심었던 나무들에 대한 abs(기존 나무와의 위치 - 현재 심으려는 나무 자리)의 합을 구한다.
• 각 나무을 심을때 비용의 곱을 구해라

접근

• 거리를 합으로 하는 합 세그를 구현한다.

풀이

1. 처음에는 심었던 나무가 없으니 비용이 0으로 고정이다. 그냥 update 해준다.
2. 심을 나무 위치 기준으로 왼쪽, 오른쪽으로 세그합 쿼리를 날려준다.

    update(1, k, 0, MAXN);
    for (int i = 2; i <= n; ++i) {
        cin >> k;
        node left = query(1, 0, (k - 1 < 0 ? 0 : k - 1), 0, MAXN);
        node right = query(1, (k + 1 > MAXN ? MAXN : k + 1), MAXN, 0, MAXN);
        long  long q = ((long long)k * left.cnt - left.val + right.val - (long long)k * right.cnt)%MOD;
        res = (res * q) % MOD;
        update(1, k, 0, MAXN);
    }
   

3. 몇개의 나무의 합에 대한 쿼리인지 알 수 없기 때문에 struct를 통해 합한 나무 개수, 총합을 반환하여 아래와 같은 공식을 이용한다.(이러면 자연스럽게 같은 위치에 나무를 심는 경우도 처리 된다.)

    ((long long)k * left.cnt - left.val + right.val - (long long)k * right.cnt)%MOD;
   

4. 나머진 합세그를 구현해주면 된다!

틀렸던 이유

• 연산과정에 long long범위를 넘는걸 생각을 못했다. 아래 부분이다.. k랑 left.cnt가 둘다 int형이라 연산시 오버플로우가 나는 경우가 있다.. 이거 몰라서 엄청 삽질함

    long  long q = ((long long)k * left.cnt - left.val + right.val - (long long)k * right.cnt)%MOD;
  

소스

#include <iostream>
using namespace std;
const int MAXN = 200005;
const int MOD = 1000000007;

struct node {
	long long val;
	int cnt;

	node(long long _val = 0, int _cnt = 0) : val(_val), cnt(_cnt) {};

	node operator = (const node& a) {
		this->val = a.val;
		this->cnt = a.cnt;
		return *this;
	}

	node operator + (const node& a) {
		return node(this->val + a.val, this->cnt + a.cnt);
	}
};

int n;
node tree[MAXN * 4];

// 위치의 합, 합친개수 업데이트
node update(int index, int target, int start, int end) {
	if (target < start || target > end)
		return tree[index];
	if (start == end) {
		return tree[index] = tree[index] + node(target, 1);
	}
	else {
		int mid = (start + end) / 2;
		return tree[index] = update(index * 2, target, start, mid) +
			update(index * 2 + 1, target, mid + 1, end);
	}
}

// left~right 범위의 위치의 합, 합친개수를 반환함
node query(int index, int left, int right, int start, int end) {
	if (left > end || right < start)
		return node(0, 0);
	if (left <= start && end <= right)
		return tree[index];
	else {
		int mid = (start + end) / 2;
		return query(index * 2, left, right, start, mid) +
			query(index * 2 + 1, left, right, mid + 1, end);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	int k;
	long long res = 1;
	cin >> k;
	update(1, k, 0, MAXN);
	for (int i = 2; i <= n; ++i) {
		cin >> k;
		node left = query(1, 0, (k - 1 < 0 ? 0 : k - 1), 0, MAXN);
		node right = query(1, (k + 1 > MAXN ? MAXN : k + 1), MAXN, 0, MAXN);
		long  long q = ((long long)k * left.cnt - left.val + right.val - (long long)k * right.cnt)%MOD;
		res = (res * q) % MOD;
		update(1, k, 0, MAXN);
	}
	cout << res << endl;
	return 0;
}