Bộ ba tăng

Points: 4 (partial)

Time limit: 1.0s

Java 8 2.0s

Python 3 5.0s

Memory limit: 98M

Author:

TICHPX

Problem type

Allowed languages

Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, ~~GAS32~~, GO, Haskell, Itercal, Java, kotlin, ~~LEAN~~, LISP, LUA, MONOVB, ~~Nasm~~, ~~OCAML~~, Pascal, Perl, php, PIKE, ~~prolog~~, Pypy, Python, ~~Ruby 2~~, RUST, Scala, SCM, SED, ~~SWIFT~~, TCL, ~~TUR~~, ~~V8JS~~, VB, ZIG

Bài toán nhập vào dãy số nguyên $a_{1}, a_{2}, . . . a_{n}$ đếm tất cả các bộ 3 số tăng dần trong dãy. Tức là đếm số bộ $(a_{i}, a_{j}, a_{k})$ với $1 \leq i < j < k \leq n$ mà $a_{i} < a_{j} < a_{k}$

Input

Dòng đầu chứa số nguyên dương n là cỡ của phép thế $(1 <= n <= 10^{5})$

Dòng thứ 2 gồm n số tự nhiên có giá trị không vượt quá $10^{5}$

Output

Một số nguyên dương duy nhất là số bộ ba tăng của dãy.

Ví dụ

Input

Copy

9
4 7 2 8 4 8 3 1 2

Output

Copy

Giải thích: có 3 bộ ba phần tử tăng ngặt là $(a_{1}, a_{2}, a_{4}); (a_{1}, a_{2}, a_{6}); (a_{3}, a_{5}, a_{6})$

tichpx

Comments

0

Ryze commented on Sept. 3, 2024, 2:55 p.m.

Cây BIT, dùng 2 vòng for cập nhật!

1

enoughtodie99 commented on Oct. 11, 2020, 3:15 p.m.

6

0 1 2 3 4 5

thì ra bao nhiêu thầy nhỉ

1

TICHPX commented on Oct. 12, 2020, 10:22 a.m.

Chắc phải 20, mình làm đề cho số nguyên dương mà test lại có số 0 nên sai test chắc mình phải sửa lại

1

enoughtodie99 commented on Oct. 12, 2020, 12:56 p.m.

vâng haha e in ra min có 0

2

TICHPX commented on Oct. 12, 2020, 1:07 p.m. ← edited →

OK, I've already updated test data for this problem

1

TICHPX commented on May 3, 2020, 3:27 a.m.

Bài này dùng cây IT