P1637 三元上升子序列

题目链接：https://www.luogu.com.cn/problem/P1637

思路

Lcnt[i]表示位置i，左边有多少个小于arr[i]
Rcnt[i]表示位置i，右边有多少个大于arr[i]
所以左右可以分别进行搞一次权值线段树，线段树存的是[l,r]之间的元素当前出现的总次数。
因为arr[i]是longlong范围，所以需要进行离散化一下.

代码

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
using namespace std;
typedef long long ll;
const int maxn = 3e4+10;
using namespace std;

int N;
int Lcnt[maxn],Rcnt[maxn];
ll arr[maxn];
int pos[maxn],tail;
struct node{
    int l,r,cnt;
}tr[maxn*4];
struct node2
{
    ll v,id;
    bool operator< (const node2 & o) const{
        return v<o.v;
    }
}cpy[maxn];

void pushup(int u){
    tr[u].cnt = tr[u*2].cnt + tr[u*2+1].cnt;
}
void build(int l,int r,int u = 1){
    tr[u] = {l,r,0};
    if(l == r) return ;
    int mid = (l+r)>>1;
    build(l,mid,u*2);
    build(mid+1,r,u*2+1);
    pushup(u);
}
void modify(int idx,int v,int u = 1){
    if(tr[u].l == idx && tr[u].r == idx) tr[u].cnt += 1;
    else{
        int mid = (tr[u].l + tr[u].r)>>1;
        if(idx<=mid) modify(idx,v,u*2);
        else modify(idx,v,u*2+1);
        pushup(u);
    }
}
int query(int l,int r,int u = 1){
    if(l <= tr[u].l && tr[u].r <= r) return tr[u].cnt;
    else{
        int mid = (tr[u].l + tr[u].r)>>1;
        int sum = 0;
        if(l<=mid) sum += query(l,r,u*2);
        if(r>mid) sum += query(l,r,u*2+1);
        return sum;
    }
}

void Lisa(){ //离散化，类似于桶排序，离散化之后，愿下标i对于pos[i]
    sort(cpy+1,cpy+N+1);
    for(int i = 1;i<=N;i++){
        if(cpy[i].v != cpy[i-1].v) pos[cpy[i].id] = ++tail;
        else pos[cpy[i].id] = tail;
    }
}


int main(){
    // debug;
    ios;
    cin>>N;
    for(int i = 1;i<=N;i++) {
        cin>>arr[i];
        cpy[i] = {arr[i],i};
    }
    Lisa();
    build(1,tail);
    for(int i = 1;i<=N;i++){ //从左到右
        if(1<=pos[i]-1) Lcnt[i] = query(1,pos[i]-1);
        modify(pos[i],1);
    }
    build(1,tail);
    for(int i = N;i>=1;i--){//从右到左
        if(pos[i]+1 <= tail) Rcnt[i] = query(pos[i]+1,tail);
        modify(pos[i],1);
    }
    ll res = 0;
    for(int i = 1;i<=N;i++){
        res += (ll)Lcnt[i] * Rcnt[i];
    }
    cout<<res<<endl;

    return 0;
}