四元组计数 1<=i<j<p<q<=n && ai<ap<aj<aq 1<=n<=5000 (用c++)

四元组计数是指在一个给定的整数数组`a`中，计算满足条件`1 <= i < j < p < q <= n`以及`ai < ap < aj < aq`的四元组(i, j, p, q)的数量。这个任务通常涉及到对数组元素进行排序，并利用两个指针技巧（如双指针法）来快速找到符合条件的组合。

在C++中，可以先对数组`a`进行排序，然后使用两个指针`i`和`j`从头开始遍历，同时维护一个指向当前最大值的指针`p = j`。对于每个`j`，我们可以在`p`位置之后继续寻找更大的值`aq`。具体步骤如下：

#include <iostream>
#include <vector>
#include <algorithm>

int count_quadruples(std::vector<int>& a, int n) {
    std::sort(a.begin(), a.end()); // 对数组进行排序

    int result = 0;
    for (int i = 0; i < n - 2; ++i) { // 忽略超过范围的索引
        if (a[i] >= a[n - 1]) break; // 当前元素大于最后一个，无需继续搜索
        
        int p = i + 1; // p初始化为i+1
        for (int j = p; j < n - 1; ++j) {
            while (j < n - 1 && a[j] < a[p]) ++p; // 跳过小于a[p]的元素
            
            if (a[j] > a[p]) { // 找到一个大于a[p]的元素
                int q = j + 1; // 初始化q为j+1
                for (; q < n; ++q) {
                    if (a[q] > a[p]) { // 如果找到一个更大的元素
                        result += q - p; // 更新结果
                        break; // 结束内层循环
                    }
                }
            }
        }
    }

    return result;
}

int main() {
    std::vector<int> arr = {1, 4, 2, 6, 3};
    int n = arr.size();
    int count = count_quadruples(arr, n);
    std::cout << "满足条件的四元组数量: " << count << std::endl;