首页 > 试题广场 >

小美的序列问题

[编程题]小美的序列问题

热度指数：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}$ 。

输入描述:

第一行输入一个整数  代表数组中的元素个数。
第二行输入  个整数  代表数组中的元素。

输出描述:

输出一个整数，表示满足条件的三元组个数。

示例1

输入

5
1 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

输出

备注:

算法知识视频讲解

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)

C++

lilinsss

#include <iostream>

#include <vector>

using namespace std;

int main() {

int m ;

cin >> m;

int x , a = 0;

int re = 0 , count = 0;

vector<pair<int,int>> ve(m);

while(cin >> x && a < m){

count = 0;

for(int i = 0;i < a;i++){

if(ve[i].first > x){

++count;

re += ve[i].second;

}

ve[a] = {x,count};

a++;

}

cout << re << endl;

}

// 64 位输出请用 printf("%lld")

发表于 2025-09-11 04:28:36 回复(0)

Yu_Xuaan

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(),(x).end()
#define ceil(a,b) ((a)+(b)-1)/(b)

class Treearray
{
public:
    vector<int> t;
    int n;
    Treearray(int _n):n(_n){t.resize(n+5);}
    inline int lowbit(int x){return x&(-x);}
    void insert(int pos,int val){for(int i=pos;i<=n;i+=lowbit(i))t[i]+=val;}
    int query(int pos){int res=0;for(int i=pos;i;i-=lowbit(i))res+=t[i];return res;}
    void rangeinsert(int l,int r,int val){insert(l,val),insert(r+1,-val);}
};

void lsh(vector<int> &a)
{
//#define all(x) (x).begin(),(x).end()
    vector<int> b=a;
    sort(all(b));
    b.erase(unique(all(b)),b.end());
    for(auto &x:a)
        x=lower_bound(all(b),x)-b.begin()+1;
}

void solve()
{
	int n;
	cin>>n;
	vector<int> a(n);
	for(int i=0;i<n;i++) {
		int x;
		cin>>x;
		x += 1e9 + 5;
		a[i] = x;
	}
	lsh(a);

	n = a.size();

	// t0 统计 ai >  aj 			在[i, n]的数量
	// t1 统计 ai >= aj 			在[i, n]的数量
	// t2 统计 ai >  aj >= ak 	        在[i, n]的数量
	Treearray t0(n+10), t1(n+10), t2(n+10);

	int cnt = 0, sum = 0;
	for(int i=n-1;i>=0;i--) {
		int t = t0.query(a[i]);
		sum += t * (t - 1) / 2;
		t0.rangeinsert(a[i]+1, n+3, 1);

		int count = t1.query(a[i]);
		t1.rangeinsert(a[i], n+3, 1);

		cnt += t2.query(a[i]);
		t2.rangeinsert(a[i]+1, n+3, count);
	}

	// (ai > ak > aj)的数量总和 = (ai > ak && ai > aj)的数量总和 - (ai > aj >= ak)的数量总和
	cout << sum - cnt << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;
	// cin>>T;
	while(T--)
		solve();
	return 0;
}

发表于 2025-09-06 01:30:46 回复(0)

提交观点

问题信息

数组前缀和

难度：

3条回答 23收藏 553浏览

小美的序列问题

输入描述:

输出描述:

输入

输出

说明

输入

输出

备注:

问题信息

热门推荐

相关试题