티스토리 뷰
문제
어떤 수가 주어지면, 그 전까지 주어진 수들까지의 절댓값 차들을 다 더한 값들을 다 곱해라.
풀이
절댓값이 아니라 그냥 이면 계속 더한값들을 저장하면서 계산하는 식으로 진행하면 된다. O(N)
하지만 절댓값이므로, 이렇게 구해주면 안되고, 주어진 수보다 큰값과 작은 값들의 합을 나누어서 진행해야한다.
상인과 비슷한 테크닉으로 하면 된다.
20만이 최대이므로 좌표압축할 필요도 없다
세그먼트 트리로 관리하면 된다.
앙 개꿀띠
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #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); } | cs |
'백준' 카테고리의 다른 글
[ BOJ 2143 ] 두배열의 합 (0) | 2018.07.23 |
---|---|
[ BOJ 10545 ] 뚜기뚜기메뚜기 (0) | 2018.07.23 |
[ BOJ 10571 ] 다이아몬드 (0) | 2018.07.23 |
[ BOJ 2508 ] 사탕 박사 고창영 (0) | 2018.07.23 |
[ BOJ 1895 ] 필터 (0) | 2018.07.23 |
댓글
최근에 올라온 글
공지사항
- Total
- Today
- Yesterday
최근에 달린 댓글
링크
TAG
- 수(상)
- 수학
- Machine Learning
- cs231n assignment1
- 해석학 Ch5
- 연습문제
- 해석학 Chapter 5
- Backprop
- 해석학II
- Deep learning
- PMA
- 선형대수학
- 17411
- 미분
- 세그먼트 트리
- PMA Ch5
- LInear SVM
- joi
- 백준
- 백준 17411
- Trace tirck
- PMA 연습문제
- 해석학
- Trace trick
- Differentation
- mathematics
- icpc.me/17411
- Derivate
- 로피탈
- JOI 2021
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함