基础数据结构应用-楼兰图腾

题目-楼兰图腾

问题分析

统计三元组, $i<j<k$, 分别满足$f(j)>f(i)<f(k)$, $f(i)<f(j)>f(k)$

按照集合思想考虑, 将所有的$V$, 按照最下面的点进行分类, 假设最下面的点分为$y_1,y_2,y_3,...,y_k$, 假设当前点的纵坐标是$y_k$

需要统计左边$>y_k$的数量$a$和右边$>y_k$的数量$b$, 那么当前位置的方案数量是$a\times b$

现在问题变成了如何统计当前位置前面和后面大于$y_k$的数量
可以使用权值树状数组解决

算法步骤

• 定义数组$g(k)$, 表示$1\sim k-1$中有多少个$y$值是大于$y_k$的
• 从左向右计算$g$数组
• 再从右向左统计$k+1\sim n$中有多少个$y$的值是大于$y_k$的
• 乘法原理累计方案数, 并且将当前位置$y_k$加入到集合中
• 求^同理

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 2e5 + 10;

int n, w[N];
LL tr[N];
LL g[N], l[N];

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

void modify(int u, int val) {
   
    for (int i = u; i <= n; i += lowbit(i)) tr[i] += val;
}

LL get(int u) {
   
    LL ans = 0;
    for (int i = u; i; i -= lowbit(i)) ans += tr[i];
    return ans;
}

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

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> w[i];

    for (int i = 0; i < n; ++i) {
   
        int val = w[i];
        g[i] = get(n) - get(val);
        l[i] = get(val - 1);
        modify(val, 1);
    }

    memset(tr, 0, sizeof tr);

    LL g_ans = 0, l_ans = 0;
    for (int i = n - 1; i >= 0; --i) {
   
        int val = w[i];
        g_ans += (LL) g[i] * (get(n) - get(val));
        l_ans += (LL) l[i] * get(val - 1);
        modify(val, 1);
    }

    cout << g_ans << ' ' << l_ans << '\n';
    return 0;
}