나무 심기 C++ - 백준 1280

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

세그 문제.

풀이 과정

전에 심었던 나무들의 좌표를 관리 해야 하기 때문에 세그를 사용해

전에 심었던 나무들의 좌표와 개수를 구해준다.

핵심 부분

현재 나무의 위치와 전에 심었던 나무들의 위치의 절댓값을 구하는 방법이

이 문제에서 가장 중요했다.

현재 나무의 위치를 $H$ 라 했을 때

전에 심었던 나무들의 위치 중 $H$ 보다 작은 것들의 개수를 $lc$

작은 것들의 좌표의 합을 $ls$라 할때

현재 나무의 위치와 전에 심었던 각각의 나무의 차는

$H\times lc\;-\;ls$ 로 표현될 수 있다.

$H$ 보다 큰 경우는 마이너스를 붙여주면 된다.

이 부분들을 구현한 코드는 다음과 같다.

#include <bits/stdc++.h>
#define SIZE 200001
#define MOD 1000000007
typedef long long ll;
using namespace std;

int n;
ll k;

struct Node{
    ll tree,cnt;
};

ll tree[SIZE*4];
ll cnt[SIZE*4];

void update(int X, int node, int S, int E){
    if(E<X || X<S) return;
    if(S==E){
        tree[node]=tree[node]+X;
        cnt[node]++;
        return;
    }
    int MID=(S+E)/2;
    update(X,2*node,S,MID);
    update(X,2*node+1,MID+1,E);
    tree[node]=tree[2*node]+tree[2*node+1];
    cnt[node]=cnt[2*node]+cnt[2*node+1];
}

Node query(int L, int R, int node, int S, int E){
    if(R<L || SIZE-1<R) return {0,0};
    if(R<S || E<L) return {0,0};
    if(L<=S && E<=R) return {tree[node],cnt[node]};
    int MID=(S+E)/2;
    Node left=query(L,R,2*node,S,MID);
    Node right=query(L,R,2*node+1,MID+1,E);
    return {left.tree+right.tree,left.cnt+right.cnt};
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> k;
    update(k,1,0,SIZE-1);
    ll res=k;
    cin >> k;
    update(k,1,0,SIZE-1);
    res=abs(k-res);
    for(int i=2;i<n;i++){
        cin >> k;
        update(k,1,0,SIZE-1);
        Node l=query(0,k-1,1,0,SIZE-1);
        Node r=query(k+1,SIZE-1,1,0,SIZE-1);
        res=(res*((r.tree-r.cnt*k)%MOD+(k*l.cnt-l.tree)%MOD)%MOD)%MOD;
    }
    cout << res;
    return 0;
}

p.s.

생각 보다 실수할 부분이 많았었다. 무엇보다 빠른 시간 내에 자력솔에

성공하여 기분이 매우 좋았다.