[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를 사용한다. 

 

 

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104

#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; }