首页 > 试题广场 >

小美的序列问题

[编程题]小美的序列问题
  • 热度指数：831 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}对于给定的由 n 个整数组成的数组 \{a_1,a_2,\dots,a_n\}，计算其中有多少个三元组 (i,j,k) 满足 1\leqq i < j < k \leqq n 且 a_i>a_k>a_j。例如，在数组\{4,1,2,3\} 中三元组 (1,2,3) ,(1,2,4),(1,3,4) 都是满足条件的三元组。更具体地，计算：

\displaystyle\sum\limits_{1\leqq i < j < k \leqq n}\left[a_i>a_k>a_j\right]

\hspace{15pt}请编写一个函数，计算并返回满足条件的三元组的数量。

【名词解释】
\hspace{15pt}本题公式中的中括号代表艾弗森括号，具体地，[P] = \begin{cases} 1 & \text{如果 } P \text{ 为真} \\ 0 & \text{如果 } P \text{ 为假} \end{cases}。

输入描述:
\hspace{15pt}第一行输入一个整数 n \left(1\leqq n \leqq 2\times 10^5\right) 代表数组中的元素个数。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n \left(-10^9\leqq a_i \leqq 10^9\right) 代表数组中的元素。


输出描述:
\hspace{15pt}输出一个整数，表示满足条件的三元组个数。
示例1

输入

5
1 5 4 2 3

输出

2

说明

\hspace{15pt}在这个样例中，满足条件的三元组有：
\hspace{23pt}\bullet\,i=2、j=4 且 k=5 构成的三元组 \{5,2,3\}；
\hspace{23pt}\bullet\,i=3、j=4 且 k=5 构成的三元组 \{4,2,3\}。
示例2

输入

20
-6 -9 -90 -73 89 -90 2 19 52 -16 -41 -22 85 24 -22 66 75 78 48 -36

输出

134

备注:

算法知识视频讲解
添加回答
Python 3
逸劳永逸头像 逸劳永逸
import sys

def solve() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        print(0)
        return

    it = iter(data)
    try:
        n = int(next(it))
    except StopIteration:
        print(0)
        return

    a = [0] * n
    for i in range(n):
        try:
            a[i] = int(next(it))
        except StopIteration:
            # Robustness: missing numbers -> treat as 0 (won't happen on valid OJ)
            a[i] = 0

    if n < 3:
        print(0)
        return

    # -------- Coordinate compression --------
    vals = sorted(set(a))
    m = len(vals)
    rank = {v: i + 1 for i, v in enumerate(vals)}
    r = [rank[v] for v in a]  # ranks in [1..m]

    # -------- Fenwick Tree as a plain list --------
    bit = [0] * (m + 1)

    def bit_add(pos: int, val: int):
        # 1-indexed BIT
        while pos <= m:
            bit[pos] += val
            pos += pos & -pos

    def bit_sum(pos: int) -> int:
        s = 0
        while pos > 0:
            s += bit[pos]
            pos -= pos & -pos
        return s

    # -------- Pass 1: right -> left --------
    # S1 = sum_i C( #right(<a_i), 2 )
    # We compute #right(<a_i) using one query + freq
    ans = 0
    right_le = [0] * n      # R_le(j) = #right(<= a_j)
    freq = [0] * (m + 1)    # counts of right elements at each rank (== a)

    for i in range(n - 1, -1, -1):
        ri = r[i]
        le = bit_sum(ri)        # #right(<= a_i)
        right_le[i] = le
        less = le - freq[ri]    # #right(< a_i) without a second query
        ans += less * (less - 1) // 2
        freq[ri] += 1
        bit_add(ri, 1)

    # -------- Pass 2: left -> right --------
    # Subtract "bad" triples: for each j, L_gt(j) * R_le(j)
    # L_gt(j) = j - #left(<= a_j)
    bit = [0] * (m + 1)  # reset BIT for left prefix counts
    for j in range(n):
        rj = r[j]
        left_le = bit_sum(rj)       # #left(<= a_j)
        left_greater = j - left_le  # #left(> a_j)
        ans -= left_greater * right_le[j]
        bit_add(rj, 1)

    print(ans)

if __name__ == "__main__":
    try:
        solve()
    except Exception:
        # Safety net for unexpected judge environments
        print(0)

发表于 2025-10-27 16:56:21 回复(0)
提交观点

问题信息

数组 前缀和
难度：
2条回答 551浏览

热门推荐

相关试题

小美的序列问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号