思路

步骤一：第一棵树状数组，先把“两种情况的总和”都算出来

• 对每个位置 $i$，设

  • $cnt_i$ 表示从 $i$ 开始向右数，所有满足 $a_k < a_i$ 的元素个数，其中 $k > i$。

• 则以 $i$ 为左端点，右侧所有值 $<a_i$ 的二元组 $(j,k)$（$j<k$）总数为

  • $\binom{cnt_i}{2}$

• 把它对所有 $i$ 求和，得到

  • $A=\sum\limits_i \binom{cnt_i}{2}$

• 注意 $A$ 同时包含了两类二元对：

  • $a_i>a_k>a_j$（右边递增，目标所需）
  • $a_i>a_j\ge a_k$（右边非增，包括 $a_j>a_k$ 和 $a_j=a_k$）

实现：从右到左，用一棵按值域的树状数组计数，查询到秩 $r_i-1$ 即可得到 $cnt_i$，累加 $\binom{cnt_i}{2}$，然后将 $r_i$ 加一。

步骤二：用后两棵树状数组，单独统计“右边非增”的总和

• 按“中点” $j$ 来统计所有 $a_i>a_j\ge a_k$ 的三元组数：

  • 令

    • $pre_j$ 表示在索引 $j$ 左侧，所有满足 $a_i > a_j$ 的元素个数，其中 $i < j$。
    • $suf_j$ 表示在索引 $j$ 右侧，所有满足 $a_k \le a_j$ 的元素个数，其中 $k > j$。

  • 则以 $j$ 为中点的“右边非增”数量为

    • $pre_j\cdot suf_j$

• 把它对所有 $j$ 求和，得到

  • $B=\sum\limits_j pre_j\cdot suf_j$

• 这里用 $\le$ 是为了把 $a_j=a_k$ 的对也一并统计进去，配合上一步中的 $A$，恰好把“相等”的对也扣干净。

实现：

• 第二遍从左到右，用树状数组统计左侧 $\le a_j$ 的数量，得到 $pre_j$。
• 第三遍从右到左，用树状数组统计右侧 $\le a_j$ 的数量，得到 $suf_j$，并累加 $B+=pre_j\cdot suf_j$。

步骤三：相减得到答案

• 由于 $A$ 恰好等于“右侧两数均 $<a_i$ 的对数”（包含 $a_i>a_k>a_j$ 与 $a_i>a_j\ge a_k$ 两类），而 $B$ 精准统计了“右边非增”（含等号）的总量，所以

  • $Ans=A-B=\sum\limits_{i<j<k}[a_i>a_k>a_j]$

C++

#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
	int n;
	vector<long long> bit;
	Fenwick() : n(0) {}
	Fenwick(int n_) { init(n_); }
	void init(int n_) { n = n_; bit.assign(n + 1, 0); }
	void add(int i, long long v) {
		for (; i <= n; i += i & -i) bit[i] += v;
	}
	long long sum(int i) const {
		long long r = 0;
		for (; i > 0; i -= i & -i) r += bit[i];
		return r;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	if (!(cin >> n)) return 0;
	vector<long long> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i];

	// 值域压缩
	vector<long long> vals = a;
	sort(vals.begin(), vals.end());
	vals.erase(unique(vals.begin(), vals.end()), vals.end());
	auto rk = [&](long long x) {
		return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) + 1;
	};
	int m = (int)vals.size();
	vector<int> r(n);
	for (int i = 0; i < n; ++i) r[i] = rk(a[i]);

	// 1) 计算第一部分：对每个 i，右侧严格小于 a[i] 的元素数 cnt
	//    累加 C(cnt, 2)
	Fenwick bit1(m);
	long long ans = 0;
	for (int i = n - 1; i >= 0; --i) {
		int ri = r[i];
		long long cnt = bit1.sum(ri - 1); // 右侧严格小于 a[i]
		ans += cnt * (cnt - 1) / 2;
		bit1.add(ri, 1);
	}

	// 2) 预处理 pre[i]：左侧严格大于 a[i] 的个数
	vector<long long> pre(n);
	Fenwick bit2(m);
	for (int i = 0; i < n; ++i) {
		int ri = r[i];
		// 左侧元素总数为 i，<= a[i] 的个数为 bit2.sum(ri)
		pre[i] = i - bit2.sum(ri); // 严格大于 a[i]
		bit2.add(ri, 1);
	}

	// 3) 预处理 suf[i]：右侧小于等于 a[i] 的个数
	Fenwick bit3(m);
	for (int i = n - 1; i >= 0; --i) {
		int ri = r[i];
		long long suf = bit3.sum(ri); // 右侧 <= a[i]
		ans -= pre[i] * suf;
		bit3.add(ri, 1);
	}

	cout << ans << "\n";
	return 0;
}

Python

import sys
from bisect import bisect_left

class Fenwick:
    def __init__(self, n=0):
        self.n = n
        self.bit = [0]*(n+1)
    def add(self, i, v):
        while i <= self.n:
            self.bit[i] += v
            i += i & -i
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    a = [int(next(it)) for _ in range(n)]

    # 值域压缩
    vals = sorted(set(a))
    m = len(vals)
    def rk(x): return bisect_left(vals, x) + 1
    r = [rk(x) for x in a]

    # 1) 累加每个 i 的 C(cnt, 2)，其中 cnt 是右侧严格小于 a[i] 的数量
    bit1 = Fenwick(m)
    ans = 0
    for i in range(n-1, -1, -1):
        ri = r[i]
        cnt = bit1.sum(ri - 1)  # 右侧严格小于
        ans += cnt * (cnt - 1) // 2
        bit1.add(ri, 1)

    # 2) pre[i]：左侧严格大于 a[i] 的个数
    pre = [0]*n
    bit2 = Fenwick(m)
    for i in range(0, n):
        ri = r[i]
        pre[i] = i - bit2.sum(ri)  # 左侧总数 i 减去 <= a[i]
        bit2.add(ri, 1)

    # 3) suf[i]：右侧小于等于 a[i] 的个数，并做扣除
    bit3 = Fenwick(m)
    for i in range(n-1, -1, -1):
        ri = r[i]
        suf = bit3.sum(ri)  # 右侧 <= a[i]
        ans -= pre[i] * suf
        bit3.add(ri, 1)

    print(ans)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
	static class FastScanner {
		private final InputStream in;
		private final byte[] buffer = new byte[1 << 16];
		private int ptr = 0, len = 0;
		FastScanner(InputStream is) { in = is; }
		private int read() throws IOException {
			if (ptr >= len) {
				len = in.read(buffer);
				ptr = 0;
				if (len <= 0) return -1;
			}
			return buffer[ptr++];
		}
		long nextLong() throws IOException {
			int c; do { c = read(); } while (c <= 32 && c != -1);
			long sgn = 1;
			if (c == '-') { sgn = -1; c = read(); }
			long x = 0;
			while (c > 32) { x = x * 10 + (c - '0'); c = read(); }
			return x * sgn;
		}
		int nextInt() throws IOException { return (int) nextLong(); }
	}

	static class Fenwick {
		int n;
		long[] bit;
		Fenwick(int n) { this.n = n; this.bit = new long[n + 1]; }
		void add(int i, long v) {
			for (; i <= n; i += i & -i) bit[i] += v;
		}
		long sum(int i) {
			long r = 0;
			for (; i > 0; i -= i & -i) r += bit[i];
			return r;
		}
	}

	public static void main(String[] args) throws Exception {
		FastScanner fs = new FastScanner(System.in);
		int n = fs.nextInt();
		long[] a = new long[n];
		for (int i = 0; i < n; i++) a[i] = fs.nextLong();

		// 值域压缩
		long[] vals = Arrays.stream(a).distinct().sorted().toArray();
		int m = vals.length;
		HashMap<Long, Integer> rank = new HashMap<>(m * 2);
		for (int i = 0; i < m; i++) rank.put(vals[i], i + 1);
		int[] r = new int[n];
		for (int i = 0; i < n; i++) r[i] = rank.get(a[i]);

		// 1) 对每个 i 累加 C(cnt,2)，cnt 为右侧严格小于 a[i] 的元素个数
		Fenwick bit1 = new Fenwick(m);
		long ans = 0;
		for (int i = n - 1; i >= 0; --i) {
			int ri = r[i];
			long cnt = bit1.sum(ri - 1);
			ans += cnt * (cnt - 1) / 2;
			bit1.add(ri, 1);
		}

		// 2) pre[i]：左侧严格大于 a[i] 的个数
		long[] pre = new long[n];
		Fenwick bit2 = new Fenwick(m);
		for (int i = 0; i < n; ++i) {
			int ri = r[i];
			pre[i] = i - bit2.sum(ri);
			bit2.add(ri, 1);
		}

		// 3) suf[i]：右侧小于等于 a[i] 的个数，并扣除
		Fenwick bit3 = new Fenwick(m);
		for (int i = n - 1; i >= 0; --i) {
			int ri = r[i];
			long suf = bit3.sum(ri);
			ans -= pre[i] * suf;
			bit3.add(ri, 1);
		}

		System.out.println(ans);
	}
}

题目内容

对于给定的由$n$个整数组成的数组{$a_1,a_2,...,a_n$}，计算其中有多少个三元组$(i,j,k)$满足$1≤i<j<k≦n$且$a_i>a_k>a_j$。例如，在数组{$4,1,2,3$}中三元组$(1,2,3),(1,2,4),(1,3,4)$都是满足条件的三元组。更具体地，计算:

$\sum_{1≤i＜j＜k≤n}[a_i＞a_k＞a_j]$

请编写一个函数，计算并返回满足条件的三元组的数量。

[名词解释] 本题公式中的中括号代表艾弗森括号，具体地，

$[P]=1$ 如果 $P$ 为真

$[P]=0$ 如果 $P$ 为假

输入描述

第一行输入一个整数$n(1≦n≦2×10^5)$代表数组中的元素个数。

第二行输入$n$个整数$a_1,a_2,...,a_n(-10^9≦a_i≦10^9)$代表数组中的元素。

输出描述

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

样例1

输入

5
1 5 4 2 3

输出

2

说明

在这个样例中，满足条件的三元组有：

• $i=2、j=4$且$k=5$构成的三元组{$5,2,3$}
• $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