[백준BOJ] 1280 나무 심기

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

1280번: 나무 심기

---

문제해설

"펜윅 트리" 를 사용하여 풀었습니다.  입력이 들어왔을때 두가지의 경우를 나누었습니다.

현재 input 이 x 라고 하였을때

 

case1 : x 보다 좌표값이 큰 나무들

case2 : x 보다 좌표값이 작은 나무들

 

<  case1  >

x보다 작은 값들과의 합은

(x - a) + (x - b) + (x - c) = 3*x - (a + b + c)

즉, (입력보다 작은 점들의 갯수) * (입력좌표) - ( 입력보다 작은 점들의 합 )

으로 나타낼 수 있습니다.

 

< case2 >

x보다 큰 값들의 합은

(a - x) + (b - x) + (c - x) = (a + b + c) - 3*x

즉,(입력보다 큰 점들의 합) - (입력보다 큰 점들의 갯수) * (입력좌표)

로 나탈낼 수 있습니다.

 

두가지의 경우를 나누어서

펜윅트를 사용해서

입력좌표보다 큰 값들의 총 갯수, 총 합

입력좌표보다 작은 값들의 총 갯수, 총 갯수

를 구한뒤 문제를 풀 수 있습니다.

(다만 주의할점은,  중간 계산 과정에서 long long 범위에 담기지 않을 수 있음으로, mod 연산을 중간 과정에서도 해줘야합니다 )

 

---

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <set>
using namespace std;
 
#define MAX_N 200000
#define DIV 1000000007
typedef long long ll;
ll tree_dist[MAX_N+1];
int tree_cnt[MAX_N+1];
int N;
 
void update_dist(int target, int value) {
     while (target <= MAX_N) {
          tree_dist[target] += value;
          target += (target & -target);
     }
}
 
void update_cnt(int target, int value) {
     while (target <= MAX_N) {
          tree_cnt[target] += value;
          target += (target & -target);
 
     }
}
 
ll query_dist(int target) {
     ll ret = 0;
     while (target >= 1) {
          ret += tree_dist[target];
          target -= (target & -target);
     }
     return ret;
}
int query_cnt(int target) {
     int ret = 0;
     while (target >= 1) {
          ret += tree_cnt[target];
          target -= (target & -target);
     }
     return ret;
}
 
int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int N; cin >> N;
     ll ret = 1;
     for (int i = 1; i <= N; i++) {
          ll tmp = 0;
          int data; cin >> data; data++;
          if (i == 1) {
               update_cnt(data, 1);
               update_dist(data, data);
          }
          else {
               tmp = (tmp + (query_cnt(data - 1) * data) - (query_dist(data - 1))) % DIV;
               tmp = (tmp + (query_dist(MAX_N) - query_dist(data)) - (query_cnt(MAX_N) - query_cnt(data)) * data) % DIV;;
               update_cnt(data, 1);
               update_dist(data, data);
               ret = (ret * tmp) % DIV;
          }
       
     }
     cout << ret % DIV << "\n";
 
}

 

---

위에서 설명한 mod연산을 중간 과정에서 해주지않아서, 한참을 헤맸습니다..ㅠ