1280 나무심기

나무심기 (1280)

https://www.acmicpc.net/problem/1280 (BOJ)

안올리면, 나중에 수정도 안할거 같아서... 일단 올려본다.

smu님이 slack에서 언급해서 오랫만에 문제다운 문제를 풀어봤다. (한 이틀전쯤 푼 문제)

문제는 딱봐도 세그를 쓰게 생겼다.

근데, 난 아직도 세그에서 각 노드가 담는 정보(?)를 어떻게 할지 빠른 판단이 서질 않는다.

이번 문제도 한번에 해결하기 보다는 그냥 query를 2번 나눠서 날린다음에 답을 구하면 아주 쉬웠는데,

쓸데 없이 한번에 해결하려고 해서 ...;;

거기다가 오랫만에 세그를 짜다보니 update랑 query를 구분하지도 않았다 ㅠ

아무튼 뭐... 맞았으니까...;; ㅋㅋㅋㅋ

#include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; #define r2 (r<<1) #define m2 ((s+e)>>1) typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ll,int> pli; vector<pii> tree; struct Info{ ll s; int c; Info():s(0LL),c(0){} Info(ll s, int c):s(s),c(c){} Info operator+(Info rhs) { return Info(s+rhs.s, c+rhs.c); } void print() { printf("sum: %lld, cnt: %d", s,c); } }; struct Ret{ Info l, r; Ret():l(Info()),r(Info()){} Ret(Info l, Info r):l(l),r(r){} Ret operator+(Ret rhs) { return Ret(l+rhs.l, r+rhs.r); } void print() { printf("LEFT => "); l.print(); printf("\t RIGHT => "); r.print(); puts(""); } }; struct Seg{ int s,e; Info defau; vector<Info> info; vector<Ret> ret; Seg(int n):s(0),defau(0LL,0) { for(e=0; (1<<e)<n; e++); ret.clear(); ret.resize(1<<(e+1)); info.clear(); info.resize(1<<(e+1)); e=(1<<e)-1; } Ret query(int r, int s, int e, int i) { if(i<s) return Ret(defau,info[r]); else if(e<i) return Ret(info[r],defau); else if(s==e) { info[r] = Info(tree[i].first,1); return Ret(defau,defau); } else { Ret L=query(r2,s,m2,i), R=query(r2+1,m2+1,e,i); info[r]=info[r2]+info[r2+1]; return L+R; } } }; const ll mod = 1e9+7LL; int idx[200000]; int main() { int n; scanf("%d", &n); for(int i=0; i<n; i++) { int x; scanf("%d", &x); tree.push_back({x, i}); } sort(tree.begin(), tree.end()); //idx.resize(n); for(int i=0; i<n; i++) idx[tree[i].second]=i; Seg seg(n); seg.query(1,seg.s,seg.e,idx[0]); ll ans=1LL; for(int i=1; i<n; i++) { Ret ret = seg.query(1,seg.s,seg.e,idx[i]); //ret.print(); ll x = tree[idx[i]].first; ans = ans*((x*ret.l.c - ret.l.s)%mod+(ret.r.s - x*ret.r.c)%mod)%mod; //ans = (ans*( tree[idx[i]].first*(ret.l.c-ret.r.c) + ret.r.s-ret.l.s)%mod)%mod; } printf("%lld\n", ans); }

참고로 print()함수는 그냥 디버깅용으로 만들어둔거다.

내 코드는 세그트리가 풀 바이너리 트리가 아니면 문제가 발생한다. (코드보면 뭔말인지 알거임)

혹시라도 수정하려고 한다면 주의하길 바란다.

아래는 쓸데없는 부분 몇개를 깔끔하게 지운 코드

#include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; #define r2 (r<<1) #define m2 ((s+e)>>1) typedef long long ll; typedef pair<int,int> pii; vector<pii> tree; struct Info{ ll s; int c; Info():s(0LL),c(0){} Info(ll s, int c):s(s),c(c){} Info operator+(Info rhs) { return Info(s+rhs.s, c+rhs.c); } }; struct Ret{ Info l, r; Ret():l(Info()),r(Info()){} Ret(Info l, Info r):l(l),r(r){} Ret operator+(Ret &rhs) { return Ret(l+rhs.l, r+rhs.r); } }; struct Seg{ int s,e; Info defau; vector<Info> info; vector<Ret> ret; Seg(int n):s(0),defau(0LL,0) { for(e=0; (1<<e)<n; e++); ret.clear(); ret.resize(1<<(e+1)); info.clear(); info.resize(1<<(e+1)); e=(1<<e)-1; } Ret query(int r, int s, int e, int i) { if(i<s) return Ret(defau,info[r]); else if(e<i) return Ret(info[r],defau); else if(s==e) { info[r] = Info(tree[i].first,1); return Ret(defau,defau); } else { Ret L=query(r2,s,m2,i), R=query(r2+1,m2+1,e,i); info[r]=info[r2]+info[r2+1]; return L+R; } } }; const ll mod = 1e9+7LL; int idx[200000]; int main() { int n; scanf("%d", &n); for(int i=0; i<n; i++) { int x; scanf("%d", &x); tree.push_back({x, i}); } sort(tree.begin(), tree.end()); for(int i=0; i<n; i++) idx[tree[i].second]=i; Seg seg(n); seg.query(1,seg.s,seg.e,idx[0]); ll ans=1LL; for(int i=1; i<n; i++) { Ret ret = seg.query(1,seg.s,seg.e,idx[i]); ll x = tree[idx[i]].first; ans = ans*((x*ret.l.c - ret.l.s)%mod+(ret.r.s - x*ret.r.c)%mod)%mod; } printf("%lld\n", ans); }