[算法进阶]dp+树状数组题目

题目

三元上升

题目意思

找出i<j<k全部a_i<a_j<a_k的数量

分析

  我们遍历顺序是从左往右，人工跑一遍样例

5
1 2 2 3 4

  发现：(1 2 3)和(1 2 4)这两个thair是有重叠(1 2)。我们可以想到 dp 来处理重叠子问题， (1 2 3)和(1 2 4) 都是由 (1 2)这个部分推导过来。
现在我们只要知道以下两个就可以解题了

1. 序列长度为1且末尾比当前数字小的总个数
2. 序列长度为2且末尾比当前数字小的总个数

怎么求这个呢？
我们能想到构建一个两个树状数组来维护两个桶分别代表上面两个，因为遍历顺序总是从左往右，所以我们只要每次查询完当前的数字x的thair 再把这个数字添加到桶里就行了，查询也是直接查询 1~x 的区间总和。

代码

点击查看代码

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 100005;struct BIT
{int n;vector<int> tr;BIT(int _n) : n(_n), tr(_n + 1) {}int lowbit(int x){return x & -x;}void add(int x, int v){for (int i = x; i <= n; i += lowbit(i)){tr[i] += v;}}int query(int x){int res = 0;for (int i = x; i; i -= lowbit(i)){res += tr[i];}return res;}
};signed main()
{IOS;int n;cin >> n;BIT tr1(N);BIT tr2(N);int cnt_all = 0;for (int i = 1; i <= n; i++){int x;cin >> x;int cnt1 = tr1.query(x - 1);int cnt2 = tr2.query(x - 1);cnt_all += cnt2;tr1.add(x, 1);tr2.add(x, cnt1);}cout << cnt_all << '\n';return 0;
}