티스토리 뷰
반응형
선행 : 모스 알고리즘
모스 알고리즘으로 해결 가능하다.
[Li, Ri] 쿼리 구간에 대해
COUNT[x] = (A[j]==x) 인 j 의 갯수
위와 같은 정보를 저장하자.
그러면 모스 알고리즘이 돌아가면서 COUNT[x] 값이 갱신될 때, 정답도 같이 갱신해주면 된다.
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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | // code by RiKang, weeklyps.com #include<stdio.h> #include<algorithm> #include<queue> #define PII pair<int,int> #define PIII pair<PII,int> using namespace::std; const int N = 100005, M = 1000005, SQRT_N = 300; PII query[N]; PIII order[N]; int cnt[M]; long long a[N]; int n,q; long long an; long long ans[M]; int removed[M]; void add(int idx){ long long ks = cnt[a[idx]], s = a[idx]; an-= ks*ks*s; cnt[a[idx]]++; ks++; an+= ks*ks*s; } void erase(int idx){ long long ks = cnt[a[idx]], s = a[idx]; an-= ks*ks*s; cnt[a[idx]]--; ks--; an+= ks*ks*s; } void go_query(PII prev, PII now){ int l1 = prev.first; int r1 = prev.second; int l2 = now.first; int r2 = now.second; for(int i = l1-1; i>=l2; i--) add(i); // l1 > l2 인 경우, 구간이 늘어났으므로 노드 추가 for(int i = r1+1; i<=r2; i++) add(i); // r1 < l2 인 경우, 구간이 늘어났으므로 노드 추가 for(int i = l1; i<l2; i++) erase(i); // l1 < l2 인 경우, 구간이 줄었으므로 노드 삭제 for(int i = r1; i>r2; i--) erase(i); // r1 < l2 인 경우, 구간이 늘어났으므로 노드 삭제 } int main(){ scanf("%d %d",&n,&q); for(int i=1; i<=n; i++){ scanf("%lld",&a[i]); } for(int i=1; i<=q; i++){ scanf("%d %d",&query[i].first, &query[i].second); order[i].first = PII(query[i].first/SQRT_N, query[i].second); order[i].second = i; } sort(order+1, order+q+1); // order[0]=(0,0) 점임을 이용하기 때문에 a는 1-indexed여야 함. for(int i=1; i<=q; i++){ go_query(query[order[i-1].second], query[order[i].second]); ans[order[i].second] = an; } for(int i=1; i<=q; i++) printf("%lld\n",ans[i]); return 0; } | cs |
반응형
'문제 풀이' 카테고리의 다른 글
최장 증가 부분 수열 ( LIS ) (0) | 2017.11.15 |
---|---|
0/1 냅색 ( 0/1 knapsack problem ) (0) | 2017.11.15 |
[BOJ 13548] 수열과 쿼리 6 (0) | 2017.11.11 |
[BOJ 13518] 트리와 쿼리 9 (0) | 2017.11.03 |
[CF 371 D] Animals and Puzzle (0) | 2017.10.31 |