백준 1280번 나무심기

문제링크: https://www.acmicpc.net/problem/1280

사용한 알고리즘: 펜윅트리


나무를 심을 때 마다 발생하는 비용을 곱한 합을 출력하는 문제였습니다.
문제풀이는 다음과 같습니다.
(1) 나무들의 심는 위치들을 펜윅트리로 구현합니다.
(2) i번째에 나무를 심을 때, (왼쪽나무개수Xi) - (왼쪽 나무(i보다 작은)들의 비용합) 과 (오른쪽 나무(i보다 큰)들의 비용합) - (오른쪽나무개수Xi) 를 더해 이를 구하고자 하는 값에 곱해줍니다.
(3) Moudlo 1000000007 을 주었으므로 이를 신경써주며 위 과정을 통해 답을 얻습니다.

2<=N 이라는 조건을 주었으므로 N=1인 경우는 생각할 필요가 없었습니다.

혹시 펜윅트리에대한 자세한 내용이 궁금한 분들은 아래 링크에 잘 정리되어 잇으니 참고해주세요.
https://www.acmicpc.net/blog/view/21

	#include <bits/stdc++.h>
	using namespace std;
	#define ll long long
	const int MOD = 1000000007;
	const int MAX = 222222;
	int N;
	ll ans, number[MAX+1], value[MAX+1];
	int Li(int x){
	return x&(-x);
	}
	ll sum(int i){
	ll temp = 0;
	while(i>0){
	temp += value[i];
	i -= Li(i);
	}
	return temp;
	}
	int Nsum(int i){
	int nnn = 0;
	while(i>0){
	nnn += number[i];
	i -= Li(i);
	}
	return nnn;
	}
	void update(int i, int V){
	while(i<=MAX){
	value[i] += V;
	number[i] += 1;
	i += Li(i);
	}
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; ++i){
	int where;
	cin >> where;
	// 펙윅은 0 처리를 못하니 좌표를 그냥 +1 해주었습니다.
	where++;
	ll leftcnt = Nsum(where-1);
	ll rightcnt = Nsum(MAX)-Nsum(where);
	ll leftVal = sum(where-1);
	ll rightVal = sum(MAX)-sum(where);
	// 왼쪽 + 오른쪽
	ll temp = where*leftcnt - leftVal;
	temp%=MOD;
	temp += rightVal - where*rightcnt;
	temp%=MOD;
	ans *= temp;
	ans %= MOD;
	update(where,where);
	if(i==0) ans=1LL;
	}
	cout << ans%MOD << '\n';
	return 0;
	}

view raw BOJ 1280.cpp hosted with ❤ by GitHub