[1280번] 나무 심기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 세그먼트 트리 :: http://www.crocus.co.kr/648

추천 문제 :: [2548번] 대표 자연수 :: http://www.crocus.co.kr/961

위의 추천 문제를 꼭 풀어보고 이 문제를 접해보길 바라는 마음으로 시작하려 한다.

이 문제는 세그트리 혹은 펜윅트리로 해결이 가능한 문제이다.

이 문제를 풀어보다가 오신분들이라면 문제는 충분히 이해했으리라 가정하고 설명하려 한다.

핵심은 이 부분이다.

long long left = cntQuery(tree, 1, 0, limit, 0, arr[i]) * arr[i] - sumQuery(tree, 1, 0, limit, 0, arr[i]);

long long right = sumQuery(tree, 1, 0, limit, arr[i] + 1, limit) - cntQuery(tree, 1, 0, limit, arr[i] + 1, limit)*arr[i];

 

자신의 위치에서 왼쪽과 오른쪽 차이의 절댓값 합을 구해주면 되는 문제인데, 절댓값을 계속해서 구해나갈 순 없는 상황이다.

따라서 이 문제는 구간에 대해 미리 갱신을 해 둘 필요가 있고, 결국 세그트리로 접근을 할 수 있는 문제이다.

위의 left를 보자.

cntQuery는 0부터 현재 자신의 위치 사이에 나타난 수를 의미하고, sumQuery는 0부터 현재 자신의 위치 사이에 나타난 수들의 합을 의미한다.

따라서 cntQuery * arr[i] - sumQuery를 하게되면 자신*cnt - 이전 누적합 이라는 식이 성립이 되고,

right에서는

sumQuery - cntQuery * arr[i]를 하면 자신 바로 다음부터 누적합 - 자신*cnt가 되어 정답을 구할 수 있게 된다.

말이 조금 어색하지만, 코드를 보면 조금 더 쉽게 해결 할 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
 
using namespace std;
 
typedef long long ll;
const int MOD = 1e9 + 7;
 
void update(vector<pair<ll, ll> > &tree, int node, int start, int end, int idx)
{
    if (!(start <= idx && idx <= end))
        return;
 
    tree[node].first += 1;
    tree[node].second += idx;
 
    if (start == end)
        return;
 
    int mid = (start + end) / 2;
    update(tree, node * 2, start, mid, idx);
    update(tree, node * 2 + 1, mid + 1, end, idx);
}
 
long long sumQuery(vector<pair<ll, ll> > &tree, int node, int start, int end, int left, int right)
{
    if (start > right || end < left)
        return 0;
 
    if (left <= start && end <= right)
        return tree[node].second;
 
    int mid = (start + end) / 2;
    return sumQuery(tree, node * 2, start, mid, left, right) + sumQuery(tree, node * 2 + 1, mid + 1, end, left, right);
}
 
long long cntQuery(vector<pair<ll, ll> > &tree, int node, int start, int end, int left, int right)
{
    if (start > right || end < left)
        return 0;
 
    if (left <= start && end <= right)
        return tree[node].first;
 
    int mid = (start + end) / 2;
    return cntQuery(tree, node * 2, start, mid, left, right) + cntQuery(tree, node * 2 + 1, mid + 1, end, left, right);
 
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    vector<int> arr(n + 1);
 
    long long ans = 1;
    int limit = -1;
 
    vector<int> vc;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
        limit = max(limit, arr[i]);
        vc.push_back(limit);
    }
 
    int h = (int)ceil(log2(200000));
    int tree_size = (1 << (1 + h));
    vector<pair<ll, ll>> tree(tree_size);
 
    for (int i = 0; i < n; i++)
    {
        update(tree, 1, 0, limit, arr[i]);
        
        long long left = cntQuery(tree, 1, 0, limit, 0, arr[i]) * arr[i] - sumQuery(tree, 1, 0, limit, 0, arr[i]);
        long long right = sumQuery(tree, 1, 0, limit, arr[i] + 1, limit) - cntQuery(tree, 1, 0, limit, arr[i] + 1, limit)*arr[i];
 
 
        long long get = (left % MOD + right % MOD) % MOD;
 
        if(i)
            ans = (ans * get) % MOD;
    }
 
    cout << ans % MOD << endl;
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>