i<j<k 를 만족하는 원소 중에서 Ai>Aj>Ak를 만족하는 경우의 수를 세는 문제입니다.


가운데를 기준으로 생각할 때 (왼쪽에서는 자신보다 큰수의 개수) * ( 오른쪽에서 자신보다 작은 수의 개수) 를 n개의원소마다

구해서 더해준다면 답이 될것입니다.


따라서 우리는 먼저  n번 자신보다 왼쪽에있는 수중에 큰 수를 구해봅시다.


왼쪽에서부터 시작해서 세그먼트트리를 업데이트하면서 자신보다 큰수의 개수를  query 하면서 a 배열에 저장합니다.


seg배열을 리셋한 후 반대방향으로 자신보다 작은 수의 개수를 query 하면서 b배열에 저장합니다.


따라서 a[i]*b[i] 의 합이 답이 됩니다. 


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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
typedef long long ll;
using namespace std;
const int MAX_N = 101000;
int seg[MAX_N * 4];
 
int update(int pos, int val, int node, int x, int y) {
    if (pos < x || y < pos)    return seg[node];
    if (x == y)    return seg[node] += val;
    int mid = (x + y) >> 1;
    return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * 2 + 1, mid + 1, y);
}
int query(int lo, int hi, int node, int x, int y) {
    if (hi < x || y < lo)    return 0;
    if (lo <= x && y <= hi)    return seg[node];
    int mid = (x + y) >> 1;
    return  query(lo, hi, node * 2, x, mid) + query(lo, hi, node * 2 + 1, mid + 1, y);
}
 
int n;
vector<int> vt;
int a[MAX_N];
int b[MAX_N];
int main() {
    freopen("input.txt""r", stdin);
    scanf("%d"&n);
    int tmp;
    for (int i = 0; i < n; i++) {
        scanf("%d"&tmp);
        vt.push_back(tmp);
    }
    ll ans = 0;
    
    for (int i = 0; i < n; i++) {
        a[i] = query(vt[i]+1, n,11, MAX_N);
        update(vt[i], 111, MAX_N);
    }
    memset(seg, 0sizeof(seg));
    for (int i = n-1; i >=0; i--) {
        b[i] = query(0,vt[i]-111, MAX_N );
        update(vt[i], 1,11, MAX_N);
    }
    for (int i = 0; i < n; i++)
        ans += (ll)a[i] * (ll)b[i];
 
    printf("%lld", ans);
}
cs


'알고리즘' 카테고리의 다른 글

codeforces)447b  (0) 2017.12.21
알고리즘)(pow(A,B))mod C 를 logB 시간에 구하는 함수  (0) 2017.11.26
acm-cicpc 수학정복  (2) 2017.09.15
[BOJ1168] 조세퍼스 문제2  (0) 2017.01.22
[BOJ5012} 불만정렬  (0) 2017.01.22
[BOJ9426] 중앙값 측정  (0) 2017.01.19

+ Recent posts