[ BOJ 1280 ] 나무 심기

http://icpc.me/1280

문제

어떤 수가 주어지면, 그 전까지 주어진 수들까지의 절댓값 차들을 다 더한 값들을 다 곱해라.

풀이

절댓값이 아니라 그냥 이면 계속 더한값들을 저장하면서 계산하는 식으로 진행하면 된다. O(N)

하지만 절댓값이므로, 이렇게 구해주면 안되고, 주어진 수보다 큰값과 작은 값들의 합을 나누어서 진행해야한다.

상인과 비슷한 테크닉으로 하면 된다.

20만이 최대이므로 좌표압축할 필요도 없다

세그먼트 트리로 관리하면 된다.

앙 개꿀띠

코드

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll,int> pii;
pii seg[4*N];
void update(int val)
{
    int upd=val;
    for(seg[val+=N].first+=upd,seg[val].second++;val>1;val>>=1) seg[val>>1].first=seg[val].first+seg[val^1].first,seg[val>>1].second=seg[val].second+seg[val^1].second;
}
pii query(int l,int r)
{
    ll sm=0; int cnt=0;
    for(l+=N,r+=N;l<r;l>>=1,r>>=1)
    {
        if(l&1) sm+=seg[l].first,cnt+=seg[l++].second;
        if(~r&1) sm+=seg[r].first,cnt+=seg[r--].second;
    }
    if(l==r) sm+=seg[l].first,cnt+=seg[l].second;
    return {sm,cnt};
}
int main()
{
    ll ans=1;
    int n,t; scanf("%d %d",&n,&t);
    update(t);
    for(int i=1;i<n;i++)
    {
        scanf("%d",&t);
        pii l=query(0,t);
        pii r=query(t+1,200000);
        ll calc=(ll)t*(ll)l.second-l.first;
        calc%=MOD;
        calc+=(r.first-(ll)t*(ll)r.second);
        calc%=MOD;
        ans*=calc;
        //printf("%lld %d %lld %d\n",l.first,l.second,r.first,r.second);
        update(t);
        ans%=MOD;
        //printf("%lld\n",ans);
    }
    return !printf("%lld",ans);
}