P10149 [Ynoi1999] XM66F 做题记录

小清新题。

题目描述

给定序列 $a_1,\dots,a_n$ ，$m$ 次询问，每次询问给出 $l,r$ ，问有多少组 $(i,j,k)$ 满足 $l\le i<j<k\le 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\le i\lt j\le 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');
}