P10589 楼兰图腾

题意概括

给定一个长度为 $n$ 的排列 $y_1, y_2, \cdots, y_n$，代表 $n$ 个点的纵坐标 $(1, y_1), (2, y_2), \cdots, (n, y_n)$。 需要计算两种图腾的数量：

1. V 图腾: 满足 $1 \le i < j < k \le n$ 且 $y_i > y_j, y_j < y_k$ 的三元组 $(i, j, k)$ 的数量。
2. ∧ 图腾: 满足 $1 \le i < j < k \le n$ 且 $y_i < y_j, y_j > y_k$ 的三元组 $(i, j, k)$ 的数量。

数据范围: $n \le 200000$。

解题思路

核心思想：降维与分步计算

直接枚举三元组 $(i, j, k)$ 是 $O(n^3)$ 的，无法接受。 一个关键的优化是固定中间点 $j$，分别计算其左侧和右侧的贡献。

对于每一个点 $j (1 \le j \le n)$：

• 它能构成的 V 图腾数量为: ( $j$ 左侧所有 $i<j$ 中，满足 $y_i > y_j$ 的数量) $\times$ ( $j$ 右侧所有 $k>j$ 中，满足 $y_k > y_j$ 的数量)。
• 它能构成的 ∧ 图腾数量为: ( $j$ 左侧所有 $i<j$ 中，满足 $y_i < y_j$ 的数量) $\times$ ( $j$ 右侧所有 $k>j$ 中，满足 $y_k < y_j$ 的数量)。

最后将所有点 $j$ 的贡献累加，就是最终答案。

这个方法将问题分解为：对于每个 $j$，如何快速统计其左（右）侧比 $y_j$ 大（小）的元素个数。如果我们从左到右处理每个点 $j$，那么当我们处理到 $j$ 时，其左侧的点 $i=1, \dots, j-1$ 都已经被访问过。问题就变成了：在一堆已经出现的数中，查询有多少个比给定值 $v=y_j$ 大/小。

这正是树状数组（Fenwick Tree, BIT） 的用武之地。

树状数组 (BIT) 底层原理

树状数组是一种能够在 $O(\log n)$ 时间内完成单点更新和前缀和查询的数据结构。

1. 基本模型: 想象有一个长度为 $n$ 的数组 A，我们想快速求出 A[1] + ... + A[x] (前缀和)。树状数组 bit 就是为了实现这个目标而设计的。在本题中，我们并不真的需要一个 A 数组，而是把它看作一个值的频率数组：A[v] 表示值为 v 的数是否出现过 (出现为1, 未出现为0)。

2. lowbit 操作: 这是树状数组的核心。lowbit(x) 函数返回 $x$ 在二进制表示下最低位的 1 以及它后面的 0 所代表的值。例如，$x=12$，二进制是 1100。最低位的 1 在第二位（从右数，第0位开始），所以 lowbit(12) 是 0100，即4。在C++中，可以通过位运算 x & -x 高效实现。

3. bit 数组的结构: bit 数组的每个位置 bit[x] 都有其特定的“管辖范围”。bit[x] 存储的是原始数组 A 中，下标在区间 $(x - \text{lowbit}(x), x]$ 内所有元素的和。

   • bit[1] 管辖 A[1]
   • bit[2] 管辖 A[1]...A[2]
   • bit[3] 管辖 A[3]
   • bit[4] 管辖 A[1]...A[4]
   • bit[5] 管辖 A[5]
   • bit[6] 管辖 A[5]...A[6]
   • bit[7] 管辖 A[7]
   • bit[8] 管辖 A[1]...A[8] 这种管辖关系形成了一种树状结构，这也是其名字的由来。

4. qry(x) - 前缀和查询: 如何计算 A[1] + ... + A[x]？我们可以通过 bit 数组的管辖范围拼接出这个前缀。

   $$\text{sum}(x) = \sum_{i=1}^{x} A[i] = \text{bit}[x] + \text{bit}[x - \text{lowbit}(x)] + \text{bit}[x - \text{lowbit}(x) - \text{lowbit}(x-\text{lowbit}(x))] + \dots $$

   我们从 x 开始，不断减去自身的 lowbit，将沿途的 bit 值累加，直到下标变为0。 例如 qry(7):

   • 初始 res = 0
   • x=7 (0111_2): res += bit[7], x = 7 - lowbit(7) = 6 (0110_2)。bit[7] 管辖 A[7]。
   • x=6 (0110_2): res += bit[6], x = 6 - lowbit(6) = 4 (0100_2)。bit[6] 管辖 A[5..6]。
   • x=4 (0100_2): res += bit[4], x = 4 - lowbit(4) = 0。bit[4] 管辖 A[1..4]。
   • 循环结束。最终 res = bit[7] + bit[6] + bit[4]，恰好覆盖了 A[1] 到 A[7] 的所有元素，且没有重叠。每次操作都至少消除一个 1，所以复杂度是 $O(\log n)$。

5. add(x, v) - 单点更新: 当 A[x] 的值增加了 v，我们需要更新所有管辖范围包含了 x 的 bit[i]。这些 i 恰好是 x 加上自身的 lowbit，再不断迭代上去。

   $$i = x, x + \text{lowbit}(x), \dots$$

   例如 add(3, v):

   • x=3 (0011_2): bit[3] += v。x = 3 + lowbit(3) = 4 (0100_2)。
   • x=4 (0100_2): bit[4] += v。x = 4 + lowbit(4) = 8 (1000_2)。
   • x=8 (1000_2): bit[8] += v。x = 8 + lowbit(8) = 16。
   • ... 直到 x > n。复杂度同样是 $O(\log n)$。

应用到本题

1. 计算左侧贡献: 我们从左到右遍历 $i=1 \dots n$。树状数组 bit 用来维护 $y_1 \dots y_{i-1}$ 这些值的出现频率。

   • 当处理到点 $i$ (值为 $v = y_i$) 时，bit 中记录了它左边所有值的分布。
   • 左侧比 $v$ 小的个数 ls[i] = $\sum_{k=1}^{v-1} (\text{值为k的数是否出现过})$。这正是前缀和查询 qry(v-1)。
   • 左侧总共有 $i-1$ 个数，所以比 $v$ 大的个数 lg[i] 就是 $(i-1) - \text{ls}[i]$。
   • 计算完后，执行 add(v, 1)，表示值 $v$ 现在也出现过了，为后续的计算更新 bit。

2. 计算右侧贡献并累加: 遍历完后，我们得到了所有 ls[i] 和 lg[i]。

   • 对于一个值 $v=y_i$，在 $1 \dots n$ 中，总共有 $v-1$ 个数比它小。既然左侧有 ls[i] 个，那么右侧就有 $(v-1) - \text{ls}[i]$ 个。
   • 同理，右侧比 $v$ 大的数有 $(n-v) - \text{lg}[i]$ 个。
   • 最后，再次遍历 $i=1 \dots n$，累加 av += lg[i] * ((n-v) - lg[i]) 和 ah += ls[i] * ((v-1) - ls[i]) 即可。

整个算法的核心就是用树状数组将 $O(n^2)$ 的统计过程优化到了 $O(n \log n)$。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAX = 200005;

int n;
int y[MAX];
int bit[MAX]; // 树状数组，bit[x] 管辖值域区间 (x-lowbit(x), x]
ll lg[MAX];   // 记录左侧比当前数大的个数
ll ls[MAX];   // 记录左侧比当前数小的个数

// 单点更新：在值 x 处增加 v，沿父节点链向上传播
void add(int x, int v) {
    for (; x <= n; x += x & -x) {
        bit[x] += v;
    }
}

// 前缀查询：查询值域 [1, x] 的总和，沿子节点链向下回溯
int qry(int x) {
    int res = 0;
    for (; x; x -= x & -x) {
        res += bit[x];
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> y[i];
    }
    
    // Pass 1: 从左到右扫描，利用树状数组计算每个 y[i] 左侧的情况
    for (int i = 1; i <= n; ++i) {
        int v = y[i];
        
        // 查询值域 [1, v-1] 的和，即左侧已出现数中小于 v 的个数
        ls[i] = qry(v - 1); 
        // 左侧已出现 i-1 个数，减去小于v的，就是大于等于v的
        // 因为是排列，不存在等于v的，所以就是大于v的个数
        lg[i] = (i - 1) - ls[i]; 
        
        // 将当前值 v 的出现次数+1，更新树状数组
        add(v, 1);
    }
    
    ll av = 0; // V-图腾计数
    ll ah = 0; // ∧-图腾计数

    // Pass 2: 计算最终结果
    // 对于每个点 i:
    // 右侧大于 y[i] 的个数 = (总共大于 y[i] 的数) - (左侧大于 y[i] 的数)
    // 右侧小于 y[i] 的个数 = (总共小于 y[i] 的数) - (左侧小于 y[i] 的数)
    for (int i = 1; i <= n; ++i) {
        int v = y[i];
        
        // 值域中比 v 大的数有 n-v 个
        ll rg = (ll)(n - v) - lg[i];
        // 值域中比 v 小的数有 v-1 个
        ll rs = (ll)(v - 1) - ls[i];
        
        // 累加每个点作为中间点时的贡献
        av += lg[i] * rg;
        ah += ls[i] * rs;
    }

    cout << av << " " << ah << "\n";

    return 0;
}