解题思路详解：三元上升子序列

这道题要求统计序列中所有满足 i < j < k 且 a[i] < a[j] < a[k] 的三元组个数。
直接三重循环会超时，我们需要一种以中间元素为桥梁的统计方法：

对于每个位置 j，如果我能知道：

• 左边有多少个数比 a[j] 小 → 记作 L[j]
• 右边有多少个数比 a[j] 大 → 记作 R[j]

那么以 j 为中间元素的三元组个数就是 L[j] * R[j]。
最终答案就是所有 j 的 L[j] * R[j] 之和。

这个转化将问题拆成了两个独立的前缀/后缀统计问题，可以用树状数组（Fenwick Tree）高效解决。

---

代码逐步分析

1. 离散化：把数值压缩到 1~n 的范围

for (int i = 1; i <= n; i++) {
    scanf("%d", &p[i].first);
    p[i].second = i;          // 记录原始下标
}
sort(p + 1, p + n + 1);      // 按数值排序
for (int i = 1; i <= n; i++) {
    if (p[i].first != p[i - 1].first)
        a[p[i].second] = i;   // 新值赋予新排名
    else
        a[p[i].second] = a[p[i - 1].second]; // 相等值赋予相同排名
}

• 排序后，p[i].first 是第 i 小的元素值，p[i].second 是它原来的下标。
• 如果当前元素与上一个元素值不同，就给它分配新的离散值 i；如果相同，就沿用上一个元素的离散值。
• 最终 a[原始下标] 存的是该元素的离散化排名，值域为 1 ~ n，且相等的元素排名相同。

为什么这样离散化？
因为我们要统计“严格小于”和“严格大于”，相等元素不能算进去。离散化时让相等元素排名相同，后面查询时用 a[i]-1 或 n-a[i] 就能自动排除相等的情况。

---

2. 统计左边比 a[j] 小的个数 L[j]

for (int i = 1; i <= n; i++) {
    t1[i] = query(a[i] - 1);   // 查询当前已插入的、排名 < a[i] 的元素个数
    update(a[i]);              // 将当前元素插入树状数组
}

• 树状数组 c 的下标是离散化后的排名，c[x] 表示排名为 x 的元素已经出现了几次。
• 从左到右遍历，每到一个位置 i，query(a[i] - 1) 返回的就是左边排名严格小于 a[i] 的元素个数，这正是我们需要的 L[i]。
• 然后 update(a[i]) 把当前元素加入，供后面的位置查询。

关键细节：query(a[i] - 1) 中的 -1 保证了严格小于，因为排名等于 a[i] 的元素不会被计入。

---

3. 统计右边比 a[j] 大的个数 R[j]

memset(c, 0, sizeof(c));      // 清空树状数组，准备从右向左统计
for (int i = n; i >= 1; i--) {
    t2[i] = query(n - a[i]);  // 查询右边比 a[i] 大的元素个数
    update(n - a[i] + 1);     // 将当前元素以“反转排名”插入
}

这里用了一个巧妙的值域反转技巧：

• 原本排名 x 越大代表数值越大。我们想统计“比 a[i] 大”的元素，即排名在 a[i]+1 到 n 之间的元素。
• 如果定义一个新排名 rev = n - x + 1，那么：
  • 原来最大的 x = n → rev = 1
  • 原来最小的 x = 1 → rev = n
• 这样，“比 a[i] 大”的原始排名 a[i]+1 ... n 就对应了新排名的 1 ... n-a[i]。
• 因此，query(n - a[i]) 恰好查询了新排名 ≤ n-a[i] 的元素个数，也就是原始排名 > a[i] 的元素个数，即右边比 a[i] 大的元素个数。

为什么从右向左遍历？
因为我们要统计的是右边的元素，所以必须保证查询时树状数组里只包含当前元素右侧已处理过的元素。从右向左遍历，每到一个位置先查询（此时树状数组里是它右边的元素），再插入自己。

update(n - a[i] + 1) 中的 +1：
因为新排名 rev = n - a[i] + 1，插入时就要更新这个新排名对应的位置。

---

4. 合并答案

for (int i = 1; i <= n; i++)
    ans += t1[i] * t2[i];

每个位置 i 作为中间元素，贡献为 L[i] * R[i]，累加即得总三元组个数。
由于 n ≤ 30000，乘积可能达到 n^2 级别，所以 ans 使用 long long。

---

关键概念总结

概念	作用
离散化	将数值范围压缩到 1~n，使树状数组下标可控；相等元素同排名，保证严格大小比较
树状数组	快速维护前缀和，支持单点更新、区间查询，时间复杂度 O(log n)
值域反转	将“统计大于某个值的个数”转化为“统计小于某个值的个数”，统一使用前缀查询
以中间元素为桥梁	将三元组问题拆成两个独立的二维统计问题，避免 O(n^2) 的组合

---

复杂度分析

• 离散化排序：O(n log n)
• 两次树状数组遍历：O(n log n)
• 总时间复杂度：O(n log n)，空间复杂度 O(n)

对于 n=30000 的数据，这个效率绰绰有余。

---

边界情况与易错点

1. 相等元素
   离散化时让相等元素排名相同，查询时用 a[i]-1 和 n-a[i] 自然排除了相等元素，保证了严格上升。
   如果错误地给相等元素分配不同排名，就会把相等元素也算进去，导致错误。

2. 树状数组下标从 1 开始
   离散化后排名最小是 1，所以 update 和 query 的参数必须 ≥1。
   代码中 query(a[i] - 1) 当 a[i]=1 时传入 0，query(0) 直接返回 0，这是安全的。

3. 值域反转的映射
   n - a[i] 的范围是 0 ~ n-1，query(0) 同样安全。
   update(n - a[i] + 1) 保证插入的下标在 1~n 之间。

4. 答案溢出
   极端情况下每个位置左边有约 n/2 个小的，右边有约 n/2 个大的，总三元组个数约为 O(n^3)，n=30000 时远超 int 范围，必须用 long long。

#include <bits/stdc++.h>
#define N 30005
#define ll long long

using namespace std;

pair<int, int> p[N];
int n, a[N], c[N];
ll ans, t1[N], t2[N];

int lowbit(int x)
{
    return x & -x;
}

void update(int x)
{
    for (int i = x; i <= n; i += lowbit(i))
        c[i]++;
}

int query(int x)
{
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        res += c[i];
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &p[i].first);
        p[i].second = i;
    }
    sort(p + 1, p + n + 1);
    // 离散化
    for (int i = 1; i <= n; i++)
    {
        if (p[i].first != p[i - 1].first)
            a[p[i].second] = i;
        else
            a[p[i].second] = a[p[i - 1].second];
    }
    for (int i = 1; i <= n; i++)
    {
        t1[i] = query(a[i] - 1);
        update(a[i]);
    }
    memset(c, 0, sizeof(c));
    for (int i = n; i >= 1; i--)
    {
        t2[i] = query(n - a[i]);
        update(n - a[i] + 1);
    }
    for (int i = 1; i <= n; i++)
        ans += t1[i] * t2[i];
    printf("%lld\n", ans);
    return 0;
}