题解思路

这是一道经典的递增三元组计数问题，需要统计所有满足位置关系 $i < j < k$ 且数值关系 $a_i < a_j < a_k$ 的三元组数量。

1. 问题分析与暴力解法

暴力方法：三重循环枚举所有可能的 $(i,j,k)$ 组合，时间复杂度为 $O(n^3)$，对于 $n=30000$ 的数据规模显然会超时。

优化思路：固定中间元素 $j$，分别统计左侧小于 $a_j$ 的元素数量和右侧大于 $a_j$ 的元素数量，然后相乘得到以 $j$ 为中心的三元组数量。

2. 树状数组优化算法

核心思想：

• 对于每个位置 $j$，计算 $left[j]$ = 位置 $j$ 左侧小于 $a_j$ 的元素数量
• 对于每个位置 $j$，计算 $right[j]$ = 位置 $j$ 右侧大于 $a_j$ 的元素数量
• 答案为 $\sum_{j=1}^{n} left[j] \times right[j]$

关键技术：

1. 坐标离散化：由于 $a_i$ 的值域很大（最大100000），直接使用会浪费空间。将所有不同的值映射到连续的整数区间。
2. 树状数组：支持单点更新和前缀和查询，时间复杂度均为 $O(\log n)$。

3. 算法步骤详解

步骤1：坐标离散化

原数组: [22, 11, 66, 99]
去重排序: [11, 22, 66, 99] 
映射关系: 11->1, 22->2, 66->3, 99->4
离散化后: [2, 1, 3, 4]

步骤2：计算左侧小于元素数量

• 从左到右遍历，对于当前元素 $a_j$，查询树状数组中小于 $a_j$ 的元素数量
• 然后将 $a_j$ 插入树状数组

步骤3：计算右侧大于元素数量

• 从右到左遍历，对于当前元素 $a_j$，用右侧总数减去小于等于 $a_j$ 的数量
• 然后将 $a_j$ 插入树状数组

4. 复杂度分析

• 时间复杂度：$O(n \log n)$

  • 离散化：$O(n \log n)$
  • 两次树状数组遍历：$O(n \log n)$

• 空间复杂度：$O(n)$

Java题解代码

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

public class Main {
    
    static class FenwickTree {
        private int[] tree;
        private int n;
        
        public FenwickTree(int size) {
            this.n = size;
            this.tree = new int[size + 1]; // 1-based indexing
        }
        
        // 单点更新：在位置 idx 上加上 delta
        public void update(int idx, int delta) {
            for (int i = idx; i <= n; i += i & (-i)) {
                tree[i] += delta;
            }
        }
        
        // 前缀和查询：查询 [1, idx] 的和
        public int query(int idx) {
            int sum = 0;
            for (int i = idx; i > 0; i -= i & (-i)) {
                sum += tree[i];
            }
            return sum;
        }
        
        // 区间查询：查询 [left, right] 的和
        public int rangeQuery(int left, int right) {
            if (left > right) return 0;
            return query(right) - query(left - 1);
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine().trim());
        int[] arr = new int[n];
        String[] tokens = br.readLine().trim().split("\\s+");
        
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(tokens[i]);
        }
        
        long result = countIncreasingTriplets(arr);
        System.out.println(result);
    }
    
    private static long countIncreasingTriplets(int[] arr) {
        int n = arr.length;
        
        // 步骤1：坐标离散化
        TreeSet<Integer> uniqueValues = new TreeSet<>();
        for (int value : arr) {
            uniqueValues.add(value);
        }
        
        List<Integer> sortedValues = new ArrayList<>(uniqueValues);
        Map<Integer, Integer> valueToRank = new HashMap<>();
        for (int i = 0; i < sortedValues.size(); i++) {
            valueToRank.put(sortedValues.get(i), i + 1); // 1-based ranking
        }
        
        int[] ranks = new int[n];
        for (int i = 0; i < n; i++) {
            ranks[i] = valueToRank.get(arr[i]);
        }
        
        int maxRank = sortedValues.size();
        
        // 步骤2：计算每个位置左侧小于当前元素的数量
        int[] leftSmaller = new int[n];
        FenwickTree leftTree = new FenwickTree(maxRank);
        
        for (int j = 0; j < n; j++) {
            int currentRank = ranks[j];
            leftSmaller[j] = leftTree.query(currentRank - 1); // 小于当前元素
            leftTree.update(currentRank, 1); // 将当前元素加入树状数组
        }
        
        // 步骤3：计算每个位置右侧大于当前元素的数量
        int[] rightGreater = new int[n];
        FenwickTree rightTree = new FenwickTree(maxRank);
        int rightCount = 0; // 右侧已处理的元素总数
        
        for (int j = n - 1; j >= 0; j--) {
            int currentRank = ranks[j];
            // 右侧大于当前元素的数量 = 右侧总数 - 右侧小于等于当前元素的数量
            rightGreater[j] = rightCount - rightTree.query(currentRank);
            rightTree.update(currentRank, 1);
            rightCount++;
        }
        
        // 步骤4：统计答案
        long totalTriplets = 0;
        for (int j = 0; j < n; j++) {
            totalTriplets += (long) leftSmaller[j] * rightGreater[j];
        }
        
        return totalTriplets;
    }
}

C++题解代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <ios>

using namespace std;

class FenwickTree {
private:
    vector<int> tree;
    int n;
    
public:
    FenwickTree(int size) : n(size), tree(size + 1, 0) {}
    
    void update(int idx, int delta) {
        for (int i = idx; i <= n; i += i & (-i)) {
            tree[i] += delta;
        }
    }
    
    int query(int idx) {
        int sum = 0;
        for (int i = idx; i > 0; i -= i & (-i)) {
            sum += tree[i];
        }
        return sum;
    }
};

class CosmicNecklaceSolver {
public:
    long long countIncreasingTriplets(const vector<int>& arr) {
        int n = arr.size();
        
        // 坐标离散化
        vector<int> uniqueVals = arr;
        sort(uniqueVals.begin(), uniqueVals.end());
        uniqueVals.erase(unique(uniqueVals.begin(), uniqueVals.end()), uniqueVals.end());
        
        unordered_map<int, int> valueToRank;
        for (int i = 0; i < uniqueVals.size(); i++) {
            valueToRank[uniqueVals[i]] = i + 1; // 1-based ranking
        }
        
        vector<int> ranks(n);
        for (int i = 0; i < n; i++) {
            ranks[i] = valueToRank[arr[i]];
        }
        
        int maxRank = uniqueVals.size();
        
        // 计算左侧小于当前元素的数量
        vector<int> leftSmaller(n);
        FenwickTree leftTree(maxRank);
        
        for (int j = 0; j < n; j++) {
            int currentRank = ranks[j];
            leftSmaller[j] = leftTree.query(currentRank - 1);
            leftTree.update(currentRank, 1);
        }
        
        // 计算右侧大于当前元素的数量
        vector<int> rightGreater(n);
        FenwickTree rightTree(maxRank);
        int rightCount = 0;
        
        for (int j = n - 1; j >= 0; j--) {
            int currentRank = ranks[j];
            rightGreater[j] = rightCount - rightTree.query(currentRank);
            rightTree.update(currentRank, 1);
            rightCount++;
        }
        
        // 统计答案
        long long totalTriplets = 0;
        for (int j = 0; j < n; j++) {
            totalTriplets += (long long)leftSmaller[j] * rightGreater[j];
        }
        
        return totalTriplets;
    }
    
    void solve() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        
        int n;
        cin >> n;
        
        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        
        long long result = countIncreasingTriplets(arr);
        cout << result << "\n";
    }
};

int main() {
    CosmicNecklaceSolver solver;
    solver.solve();
    return 0;
}