P10149 [Ynoi1999] XM66F 做题记录

小清新题。

题目描述

给定序列 $a_{1}, \dots, a_{n}$ ， $m$ 次询问，每次询问给出 $l, r$ ，问有多少组 $(i, j, k)$ 满足 $l \leq i < j < k \leq r, a_{i} = a_{k} > a_{j}$ 。

思路

记 $w_{x}$ 为 $\sum_{i = 1}^{x} [a_{i} < a_{x}]$ ，即 $1 \sim x$ 中小于 $a_{x}$ 的数的个数。从左往右依次将数加入值域树状数组即可在 $O (n \log n)$ 的时间复杂度内计算 $w$ 。

不难发现，需要求的答案为 $\sum_{l \leq i < j \leq r, a_{i} = a_{j}} w_{j} - w_{i}$ 。考虑使用莫队计算，则需快速移动左右端点。记 $t_{i}$ 为当前区间内值 $i$ 的出现次数， $f_{i}$ 为值 $i$ 出现位置对应的 $w$ 的和，若加入一个数 $a_{i}$ ，其对答案的贡献为 $| t_{a_{i}} w_{i} - f_{a_{i}} |$ 。删除数的时候同理。这样，我们做到了 $O (1)$ 移动左右端点，时间复杂度为 $O (n \sqrt{n})$ 。

Code

constexpr int N=5e5+5,B=710;using ll=long long;
namespace BIT
{
    int c[N],n;
    inline void init(int _n){n=_n;}
    inline int lowbit(int x){return x&(-x);}
    inline void update(int x){while(x<=n)c[x]++,x+=lowbit(x);}
    inline int query(int x){int res=0;while(x)res+=c[x],x-=lowbit(x);return res;}
}
int a[N],w[N],bel[N],t[N];ll ans[N],ts[N],now=0;struct Q{int l,r,id;}q[N];
inline void addr(int x){now+=1ll*t[a[x]]*w[x]-ts[a[x]];t[a[x]]++;ts[a[x]]+=w[x];}
inline void addl(int x){now+=ts[a[x]]-1ll*t[a[x]]*w[x];t[a[x]]++;ts[a[x]]+=w[x];}
inline void delr(int x){t[a[x]]--;ts[a[x]]-=w[x];now-=1ll*t[a[x]]*w[x]-ts[a[x]];}
inline void dell(int x){t[a[x]]--;ts[a[x]]-=w[x];now-=ts[a[x]]-1ll*t[a[x]]*w[x];}
inline void work()
{
    using namespace IO;
    int n,m,l=1,r=0;qread(n),qread(m);BIT::init(n);
    for(int i=1;i<=n;i++) qread(a[i]),w[i]=BIT::query(a[i]-1),BIT::update(a[i]);
    for(int i=1;i<=n;i++) bel[i]=(i-1)/B+1;
    for(int i=1;i<=m;i++) qread(q[i].l),qread(q[i].r),q[i].id=i;
    sort(q+1,q+m+1,[](const Q&x,const Q&y){return bel[x.l]<bel[y.l]||(bel[x.l]==bel[y.l]&&((bel[x.l]&1)?(x.r<y.r):(x.r>y.r)));});
    for(int i=1;i<=m;i++)
    {
        while(r<q[i].r) addr(++r);
        while(l>q[i].l) addl(--l);
        while(r>q[i].r) delr(r--);
        while(l<q[i].l) dell(l++);
        ans[q[i].id]=now;
    }
    for(int i=1;i<=m;i++) qwrite(ans[i]),pc('\n');
}
CPP