题解：AT_abc436_f [ABC436F] Starry Landscape Photo

Mzh2012 · 2025-12-16 20:39:23 · 题解

题目意思

我们枚举亮度 b_i，对于每个点记录左边小于 b_i 的数量 y，和右边小于 b_i 的数量 x，显然答案就是 (x+1)(y+1) 个。然后处理左边小于的和右边小于的可以用树状数组来维护，时间复杂度为 O(n \log n)。

代码

#include<bits/stdc++.h>

using namespace std;

#define int long long
const int N = 5e5+5;
int n,b[N];
int tr[N];

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

void add(int x,int c){
    while(x<=n){
        tr[x]+=c;
        x+=lowbit(x);
    }
}

int query(int x){
    int cnt = 0;
    while(x){
        cnt+=tr[x];
        x-=lowbit(x);
    }
    return cnt;
}
int L[N],R[N];
signed main(){
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>b[i];
    for(int i = 1;i<=n;i++){
        L[i] = query(b[i]-1);
        add(b[i],1);
    }
    memset(tr,0,sizeof(tr));
    for(int i = n;i>=1;i--){
        R[i] = query(b[i]-1);
        add(b[i],1);
    }
    int cnt = 0;
    for(int i = 1;i<=n;i++) cnt+=(L[i]+1)*(R[i]+1);
    cout<<cnt;
    return 0;
}