BOJ(백준) 1280번 나무 심기

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

1280번: 나무 심기

나무를 심을때 기존에 심었던 나무들 각각과의 거리가 비용이 되므로 기존에 심은 나무들 각각으로 인해 생기는 비용을 따로 계산하여 생각해보자

 

나무를 임의의 수인 a번째로 심었을 때 나무의 위치를 L(a)라고 하자

 

i번째 나무를 심을 때의 k번째 나무로 인해 생기는 비용을 생각해보면 다음과 같이 세 가지 경우가 존재한다. (k<i)

 

① L(k)>L(i)이면 비용은 L(k)-L(i) 증가

② L(k)<L(i)이면 비용은 L(i)-L(k) 증가

③ L(k)=L(i)이면 비용은 0 증가

 

①에 해당하는 값들의 인덱스를 각각 a1, a2, a3, ... , an

②에 해당하는 값들의 인덱스를 각각 b1, b2, b3, ... , bm 이라고 한다면 전체 비용의 계산식은 다음과 같다

(a1 + a2 + ... + an) - i * n + i * m - (b1 + b2 + ... + bm)

 

따라서 나무가 존재하는 인덱스의 합과 나무의 개수를 저장하는 구간 합 세그먼트 트리에 나무를 차례대로 업데이트 하면서 쿼리로 비용을 계산해준 뒤 곱하여 문제를 해결할 수 있다.

 

AC code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t1,N,mul=1,MOD=1e9+7;

template<typename T> struct segment_tree {
	
	T (*merge)(T, T);
	int s,e,N;
	vector<T> tree;
	
	segment_tree(vector<T> vec,int start,int end,T (*func)(T, T)) {
		s=start;
		e=end;
		N=e-s+1;
		merge=func;
		tree.resize(4*N+1);
		init(vec,1,start,end);
	}
	
	T query(int left,int right,T null) {
		return que(left,right,1,s,e,null);
	}
	
	void update(int idx,vector<T> val,T (*func)(T, vector<T>)) {
		upd(1,s,e,idx,val,func);
	}
	
	private:
	
	T init(vector<T> &vec,int node,int start,int end) {
		if(start==end) return tree[node]=vec[start];
		int mid=(start+end)/2;
		return tree[node]=merge(init(vec,node*2,start,mid),init(vec,node*2+1,mid+1,end));
	}
	
	T upd(int node,int start,int end,int idx,vector<T> &val,T (*func)(T, vector<T>)) {
		if(idx<start||idx>end) return tree[node];
		if(start==end) return tree[node]=func(tree[node],val);
		int mid=(start+end)/2;
		return tree[node]=merge(upd(node*2,start,mid,idx,val,func),upd(node*2+1,mid+1,end,idx,val,func));
	}
	
	T que(int left,int right,int node,int start,int end,T null) {
		if(right<start||left>end) return null;
		if(start>=left&&end<=right) return tree[node];
		int mid=(start+end)/2;
		return merge(que(left,right,node*2,start,mid,null),que(left,right,node*2+1,mid+1,end,null));
	}
};

struct node {
	ll val;
	ll idx;
};

node func1(node l,node r) {
	return {l.val+r.val,l.idx+r.idx};
}

node func2(node n,vector<node> v) {
	return {n.val+v[0].val,n.idx+v[0].idx};
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>N;
	vector<node> v(N+1);
	segment_tree<node> tree(vector<node>(200001,{0,0}),0,200000,&func1);
	for(int i=1;i<=N;i++) {
		cin>>t1;
		v[i]={1,t1};
	}
	tree.update(v[1].idx,{v[1]},&func2);
	for(int i=2;i<=N;i++) {
		ll sol=0;
		if(v[i].idx>0) {
			node tmp=tree.query(0,v[i].idx-1,{0,0});
			sol+=v[i].idx*tmp.val-tmp.idx;
		}
		if(v[i].idx<200000) {
			node tmp=tree.query(v[i].idx+1,200000,{0,0});
			sol+=tmp.idx-v[i].idx*tmp.val;
		}
		tree.update(v[i].idx,{v[i]},&func2);
		mul=(mul*(sol%MOD))%MOD;
	}
	cout<<mul;
}

 

일반화 세그먼트 트리 구현 - 1. 일반화 프로그래밍이란?

직접 구현한 일반화 세그먼트 트리로 문제를 풀어보았다.

 

문제를 풀면서 실수할만 하다고 생각하는 점들이 꽤 있었는데 다음과 같다.

 

① 같은 위치에 여러 나무를 심는 것이 가능하다.

② 나무 위치의 범위가 0이상 20만 미만이다.

③ 각 나무를 심을 때 비용값 자체는 long long 범위를 벗어나지 않지만 그대로 곱하면 오버플로우가 날 수 있으므로 나머지 연산을 한 뒤 비용들의 곱에 곱해줘야 된다.