주어진 배열에 대해 세 가지 요소의 조합을 내림차순으로 계산하십시오.

Question

프로그래밍에서 과거 경쟁으로 인한 한 가지 문제점을 해결하고 있으므로 도움이 필요합니다. 문제를 한 문장으로 설명합니다. 크기가 N 인 배열이 있는데, N은 10^5까지 올 수 있습니다. 그리고 두 번째 줄에는 정확히 N 개의 요소가 있습니다. 이제는 배열에서 세 요소를 선택하는 방법을 세어 순서대로 계산해야합니다. 여기에 예제가 있습니다

N = 4이고 배열은 190, 180, 170, 168처럼 보입니다.이 세 가지 요소를 선택하는 방법은 정확히 네 가지입니다. 1. (190, 180, 170) 2. (190,180,168) 3. (190, 170, 168) 및 (180, 170, 168)

세그먼트 트리로 해결해야한다고 생각하지만, 어떤 논쟁을 통해 내가 나무를 만들어야하는지 알지 못한다. 미리 감사드립니다.

Answer 1

1. 우리는 모든 숫자가 [0, n - 1] 범위 (그렇지, 우리가 할 수있는 '압축'그들)에 있다고 가정 할 수있다.

2. 트리플에서 중간 요소의 위치를 ​​수정합시다. 이제 우리는 왼쪽에서 더 큰 요소의 수를 세고 오른쪽에서 더 작은 요소의 수를 곱할 수 있습니다.

3. 인덱스가 작은 큰 요소의 수를 계산하는 방법은 무엇입니까? 우리는 점에서 업데이트 및 범위의 합을 필요

   tree = SegmentTree(0, n - 1) // for sum and add operations 
   for i = 0 ... n - 1 
       greaterLeft[i] = tree.getSum(a[i] + 1, n - 1) 
       tree.update(a[i], 1) 
   

4. 참고 : 여기를 설명하는 의사 코드이다. 2 진 인덱스 트리는 효율적으로 수행 할 수 있습니다 (세그먼트 트리보다 구현이 쉽습니다).