[luogu] P1637 三元上升子序列 树状数组

前言

真简单,数据结构真简单!!

传送门 :

思路

计算一个 三元上升序列 我们可以枚举 中间节点 然后通过乘法原理 记录 L e f t [ ] 和 R i g h t [ ] Left[] 和 Right[] Left[]和Right[]

当然数据范围是3e5+10 如果直接求会爆炸 所以我们还需要离散化

因为我们只需要 离散化 并且 枚举中间节点求出所有的 L e f t [ i ] ∗ R i g h t [ i ] Left[i]*Right[i] Left[i]∗Right[i]之和即是答案

CODE

#include 
using namespace std;
#define ll long long
#define endl '\n'
#define unmp unordered_map
#define x first
#define second
typedef pair PII;
const int N  = 3e4+10;
int n,m;
int c1[N],c2[N];
int l[N],r[N];
int A[N],_A[N];

inline int hash_(int val){
    return lower_bound(_A+1,_A+m+1,val) -_A;
}

inline int lowbit(int i){
    return i&(-i);
}

void add(int *C,int pos,int val){
    while(pos0 ){
        res+=C[pos];
        pos-=lowbit(pos);
    }
    return res;
}
void solve()
{
    cin>>n;
    for(int i=1;i>A[i];
        _A[i] = A[i];
    }
    sort(_A+1,_A+n+1);
    m = unique(_A+1,_A+n+1)-(_A+1);

    for(int i=1;i=1;i--){
        add(c2,hash_(A[i]),1);
        r[i] = n-i-(sum(c2,hash_(A[i]))-1);
    }

    ll ans = 0 ;
    for(int i=2;i