AT_abc436_f

TP2010 · 2025-12-14 09:46:03 · 题解

前言

一道小清新的计数题。

前置知识：树状数组，扫描线。

分析

发现一种集合可以有多种方式来拍，思考如何才能不重不漏。

我的办法是把在值域上从小到大做扫描线，每个集合在其最大权值 val_{MAX} 处统计。

则此时亮度限制就是 val_{MAX}，考虑范围限制。

由于不能统计之前统计过的集合，我们只用考虑包含最大 val 元素位置 p 的 (l,r)，又因为在不同 (l,r)，也可能得到相同集合，所以我们统计的最本质的 (l,r) 的 l,r 处都是已经加入的元素，这些就足以得到所有情况，所以答案的统计直接是跟元素数量有关的。

为了得到包含 p 的 (l,r)，记 p 左边已加入的元素数量为 cntl_p，p 右边已加入的元素数量为 cntr_p，则 ans= \sum\limits_{p=1}^{n}cntl_p\times cntr_p。

树状数组维护 cntl,cntr 即可。

时间复杂度 O(n\log n)。

空间复杂度 O(n)。

:::info[Code]

#include <bits/stdc++.h>
using namespace std;

inline int read(){
    int d=0,f=0;char ch=getchar();
    while (!isdigit(ch)) f|=(ch=='-'),ch=getchar();
    while (isdigit(ch)) d=d*10+ch-'0',ch=getchar();
    return f?-d:d;
}

const int N=500005;
int n,b[N];
struct BIT{
    int c[N];
    inline void add(int x,int v){
        for (int i=x;i<=n;i+=i&-i) c[i]+=v;
    }
    inline int query(int x){
        int res=0;
        for (int i=x;i;i-=i&-i) res+=c[i];
        return res;
    }
    inline int query(int l,int r) {return query(r)-query(l-1);}
}tree;
int main(){
    n=read();
    for (int i=1;i<=n;i++) b[read()]=i;
    long long ans=0;
    for (int i=1;i<=n;i++){
        tree.add(b[i],1);
        ans+=1ll*tree.query(1,b[i])*tree.query(b[i],n);
    }
    printf("%lld\n",ans);
    return 0;
}

:::

求赞 QWQ。