P1637 三元上升子序列 - 洛谷

谨遵某位佬的嘱托，难题 4min 没思路就去看题解，所以果断放弃

真不是我懒

发现都是线段树或者树状数组的题解，但是这两个数据结构我都不会，所以只能从头开始学

基本思路

因为是三元上升子序列，所以我们可以尝试枚举中间元素

找到中间元素——我们记为 **A[i]**，统计在其左边小于 A[i] 的元素个数 front[i] 和右边大于 A[i] 的元素个数 **back[i]**，那么，以 A[i] 为中间元素的三元上升子序列的个数为 fronti] * backi]

找到 front[] 和 back[]

显然，可以在找到 A[i] 之后对左右元素进行枚举，但是这样显然是超时的，我们得像个办法找到这两个数组

难绷的是，写到这里的时候发现看不懂题解于是写了个暴力枚举，结果竟然过了

听同学的，决定使用vector写个伪平衡树来统计这两个数组

伪平衡树

以 front[] 为例

我们构造一个有序数组v1，有序存放已经询问过的A[i]中的元素，这样下次使用二分查找确定A[i]位置是，其下标就是左侧小于A[i]的数的个数，即front[i]

给出实现代码

v1.push_back(a[1]);

   for (int i = 2; i <= n; i++) {
       auto it = lower_bound(v1.begin(), v1.end(), a[i]);  // 找到第一个>=a[i]的位置
       front[i] = it - v1.begin();
       v1.insert(it, a[i]);
   }

这样正向遍历一遍，我们就能得到需要的front[]数组

反向同理

v2.push_back(a[n]);
   for (int i = n - 1; i >= 1; i--) {
       auto it = upper_bound(v2.begin(), v2.end(), a[i]);  // 找到第一个>a[i]的位置
       back[i] = v2.end() - it;
       v2.insert(it, a[i]);
   }

最终答案

#include <algorithm>
#include <iostream>
#include <vector>
#define int long long
using namespace std;

int n;
int a[30005];
int front[30005], back[30005];

vector<int> v1;
vector<int> v2;
signed main() {
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    v1.push_back(a[1]);

    for (int i = 2; i <= n; i++) {
        auto it = lower_bound(v1.begin(), v1.end(), a[i]);  // 找到第一个>=a[i]的位置
        front[i] = it - v1.begin();
        v1.insert(it, a[i]);
    }

    v2.push_back(a[n]);
    for (int i = n - 1; i >= 1; i--) {
        auto it = upper_bound(v2.begin(), v2.end(), a[i]);  // 找到第一个>a[i]的位置
        back[i] = v2.end() - it;
        v2.insert(it, a[i]);
    }

    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += front[i] * back[i];
    }

    cout << sum;
    return 0;
}