[BOJ] 1280. 나무심기

*세그먼트 트리를 사용한다. 

*현재 나무의 좌표가 [pos]라고 가정한다. 

pos가 나온 시점보다 앞에 심어진 나무 중 pos보다 좌표의 크기가 큰 좌표의 합 = sumUpper

개수 = a

 

pos가 나온 시점보다 앞에 심어진 나무 중 pos보다 좌표의 크기가 작은 좌표의 합 = sumLower

개수 = b

 

3

2

0

4

1

이렇게 다섯 개의 나무가 심어질 것이다. 

 

3의 관점에서 sumUpper = 0/ sumLower = 0 / a = 0 / b = 0 => cost = 0

2의 관점에서 sumUpper = 3 / sumLower = 0 / a = 1 / b = 0 =>

좌표 사이의 거리를 구하는 것이기 때문에 sumUpper - pos*a를 해줘야 한다. (각 좌표에서 기준 좌표를 빼주는 것과 같다) 

=> cost = 1

...

4의 관점에서 sumUpper = 9/ sumLower = 0/ a = 3 / b = 1 => 6 + 1 (기준 좌표가 더 큰 값이기 때문에 pos * b - sumLower)

=> cost = 7

 

*이 문제를 틀리는 가장 큰 이유는 mod를 잘못 나눠줘서 그런 것 같다. 

mod를 각 노드의 값을 저장할 때나, 계산할 때 하게 되면 값의 왜곡이 발생한다. 

mod = 1,000,000,007 일때 노드의 값이 1,000,000,008이면 1만 저장하게 되는 것이다.

그렇기 때문에 최종값 (total) 을 계산할 때만 mod를 사용한다. 

 

 

 

#include <iostream> #include <vector> #include <cmath> #define MOD 1000000007 #define MAXX 200006 using namespace std; /* BOJ 1280. https://www.acmicpc.net/problem/1280 */ typedef long long ll; ll tree[MAXX], cnt[MAXX]; // int init(vector<int>&tree, vector<int>&pos, int node, int start, int end) { // if (start == end) return tree[node] = 0; // else { // tree[node] = init(tree, pos, node*2, start, (start+end)/2) + init(tree, pos, node*2+1, (start+end)/2+1, end); // // if (start < end) { // // tree[node] = abs(pos[start] - pos[end]); // // } // } // } void update(int idx, int diff) { while (idx < MAXX) { tree[idx] = (tree[idx] + diff); idx += (idx & -idx); } } void updateCnt(int idx, int diff) { while (idx < MAXX) { cnt[idx] += diff; idx += (idx & -idx); } } ll sum(int idx) { ll ret = 0; while(idx > 0) { ret = (ret + tree[idx]); idx -= (idx & -idx); } return ret; } ll sumCnt(int idx) { ll ret = 0; while(idx > 0) { ret += cnt[idx]; idx -= (idx & -idx); } return ret; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int pos; cin >> pos; update(pos+1, pos); updateCnt(pos+1, 1); if (n == 1) { cout << 0 << '\n'; return 0; } //현재 좌표가 pos라면 //나보다 크거나 같은 좌표의 개수 a //나보다 크거가 같은 좌표들의 합 sumUpper //sumUpper - pos*a (각 좌표에 대해 현재 좌표크기를 빼줘야 한다. ) //나보다 작거나 같은 좌표의 개수 b //나보다 작거나 같은 좌표들의 합 sumLower //pos*b - sumLower (각 좌표에 대해 현재 좌표크기를 빼줘야 한다. ) int total = 1; for (int i = 2; i <= n; i++) { cin >> pos; //나무들의 좌표와 나보다 큰, 작은 나무들의 개수를 저장해야 한다. pos++; //0을 피하기 위해 (sum에서 idx > 0 이다.) update(pos, pos-1); updateCnt(pos, 1); ll a = sumCnt(MAXX)-sumCnt(pos); ll sumUpper = sum(MAXX) - sum(pos); ll b = sumCnt(pos-1); ll sumLower = sum(pos-1); ll calcUpper = (sumUpper - ((pos-1)*a)); ll calcLower = (((pos-1)*b)- sumLower); total = (total%MOD * ((calcUpper + calcLower)%MOD))%MOD; } cout << total << '\n'; return 0; }