笔试时间：2025年9月20日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

宇宙勇者得到了一条特殊的能量项链，能够给他提供战斗所需的能量，帮助他打倒更多的怪兽。这个项链的前面镶嵌了 n 颗宇宙宝石，每一颗宇宙宝石都有特定的能量值。

科学院测算了这条能量项链，得出它的 n 颗宇宙宝石的能量值分别为 a₁, a₂, ..., aₙ。聪明的科学家们还研究出了能量项链的规则：如果存在一个三元组 (i,j,k) 同时满足下面两个条件：

1. 1 ≤ i < j < k ≤ n
2. aᵢ < aⱼ < aₖ

那么这个三元组对应的三颗宝石就能组成法阵，为勇者提供战斗 1 分钟的能量。

请帮勇者计算一下这条能量项链能为他提供战斗多少分钟的能量。

输入描述

第一行有一个整数 n (1 ≤ n ≤ 10⁵)。

随后有 n 个整数 a₁, a₂, ..., aₙ (1 ≤ aᵢ ≤ 10⁵)，代表能量项链上第 i 颗宇宙宝石的能量。

注意：宇宙宝石只是在能量项链的前面镶嵌，并非一个环形，即 a₁ 和 aₙ 不相邻。

输出描述

输出一个整数，代表题目所求答案。

样例输入

4

22 11 66 99

样例输出

2

样例说明： 存在 2 个三元组 (2,3,4) 和 (1,3,4) 满足题意。

参考题解

解题思路：

1. 统计所有满足条件的三元组 (i,j,k)，其中 i<j<k 且 aᵢ<aⱼ<aₖ
2. 对于每个中间位置 j，计算： 在 j 左边有多少个数比 aⱼ 小（记为 leftSmaller[j]）在 j 右边有多少个数比 aⱼ 大（记为 rightLarger[j]）
3. 以 j 为中间值的有效三元组数量就是 leftSmaller[j] × rightLarger[j]
4. 使用树状数组（Fenwick Tree）高效计算

C++：

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

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    const int MAX_VAL = 100001;
    vector<int> leftSmaller(n, 0);
    FenwickTree bit1(MAX_VAL);
    
    for (int i = 0; i < n; i++) {
        leftSmaller[i] = bit1.query(a[i] - 1);
        bit1.update(a[i], 1);
    }
    
    vector<int> rightLarger(n, 0);
    FenwickTree bit2(MAX_VAL);
    
    for (int i = n - 1; i >= 0; i--) {
        rightLarger[i] = bit2.query(MAX_VAL - 1) - bit2.query(a[i]);
        bit2.update(a[i], 1);
    }
    
    long long totalEnergy = 0;
    for (int i = 0; i < n; i++) {
        totalEnergy += (long long)leftSmaller[i] * rightLarger[i];
    }
    
    cout << totalEnergy << endl;
    return 0;
}

Java：

import java.util.*;

public class Main {
    static class FenwickTree {
        int[] tree;
        int n;
        
        public FenwickTree(int size) {
            n = size;
            tree = new int[size + 1];
        }
        
        public void update(int idx, int delta) {
            while (idx <= n) {
                tree[idx] += delta;
                idx += idx & -idx;
            }
        }
        
        public int query(int idx) {
            int sum = 0;
            while (idx > 0) {
                sum += tree[idx];
                idx -= idx & -idx;
            }
            return sum;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        final int MAX_VAL = 100001;
        int[] leftSmaller = new int[n];
        FenwickTree bit1 = new FenwickTree(MAX_VAL);
        
        for (int i = 0; i < n; i++) {
            leftSmaller[i] = bit1.query(a[i] - 1);
            bit1.update(a[i], 1);
        }
        
        int[] rightLarger = new int[n];
        FenwickTree bit2 = new FenwickTree(MAX_VAL);
        
        for (int i = n - 1; i >= 0; i--) {
            rightLarger[i]