首页 > 试题广场 >

小美的序列问题

[编程题]小美的序列问题
  • 热度指数：449 时间限制：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

备注:

算法知识视频讲解
开通博客
头像 Silencer76
发表于 2025-08-25 21:58:09
题目链接 小美的序列问题 题目描述 给定一个由 个整数组成的数组 ，计算其中有多少个三元组 满足 且 。 输入: 第一行输入一个整数 ()，代表数组中的元素个数。 第二行输入 个整数 ()。 输出: 输出一个整数，表示满足条件的三元组个数。 解题思路 本题是一道复杂的计数问题，由 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

数组 前缀和
难度：
1条回答 96浏览

热门推荐

相关试题

小美的序列问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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