【洛谷P5501】[LnOI2019]来者不拒，去者不追 | Mrsrz's blog

二次离线莫队

题目大意：

给定一个数列，每次询问区间 $[l,r]$。

对于区间里的每个数 $a_i$，如果区间里有 $k$ 个数比它小，则这个数的贡献就是 $(k+1)a_i$。

求区间里所有数的贡献之和。

题解：

二次离线莫队。

考虑莫队时，新加一个数会产生多少新的贡献。

设 $f(a,l,r)$ 表示区间 $[l,r]$ 中比 $a$ 小的数的个数，$g(a,l,r)$ 表示区间 $[l,r]$ 中比 $a$ 大的数的和。

那么 $[l,r]\rightarrow [l,r+1]$ 时，其新产生的贡献为 $a_{r+1}\times (f(a_{r+1},l,r)+1)+g(a_{r+1},l,r)$。

这个 $f$ 和 $g$ 都是满足差分性质的，即 $f(a,l,r)=f(a,1,r)-f(a,1,l-1);g(a,l,r)=g(a,1,r)-g(a,1,l-1)$。

这样就可以进行二次离线了。

用树状数组预处理出 $1\sim k$ 中比 $k$ 小的数的个数，和比 $k$ 大的数的和。

之后进行莫队时，我们需要一个 $O(1)$ 查询前/后缀和，$O(\sqrt n)$ 单点修改的数据结构，显然一个分块就好了。

总时间复杂度 $O(n\sqrt n)$。

Code：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define bel(x)((x-1)/317+1)
using namespace std;
typedef long long LL;
const int N=5e5+5,siz=800,blocks=bel(100000);
int pre[N],suf[N],a[N];
LL prec[N],sufc[N],B2[100005];
int B1[100005],n,m;
LL ans[N];
inline void add1(int i){for(;i<=100000;i+=i&-i)++B1[i];}
inline int ask1(int i){int x=0;for(;i;i&=i-1)x+=B1[i];return x;}
inline void add2(int i,int x){for(;i<=100000;i+=i&-i)B2[i]+=x;}
inline LL ask2(int i){LL x=0;for(;i;i&=i-1)x+=B2[i];return x;}
struct que{
    int l,r,id;
    inline bool operator<(const que&rhs)const{return(l/siz!=rhs.l/siz?l<rhs.l:r<rhs.r);}
}q[N];
struct vue{
    int l,r,id,fh;
};
vector<vue>L[N],R[N];
int bc[N],tc[320];LL bs[N],ts[320];
inline void update(int x){
    int bL=bel(x-1);
    for(int i=1;i<bL;++i)ts[i]+=x;
    for(int i=(bL-1)*317+1;i<x;++i)bs[i]+=x;
    bL=bel(x+1);
    for(int i=bL+1;i<=blocks;++i)++tc[i];
    for(int i=x+1;i<=bL*317&&i<=100000;++i)++bc[i];
}
inline int getcnt(int x){return bc[x]+tc[bel(x)];}
inline LL getmx(int x){return bs[x]+ts[bel(x)];}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    LL sm=0;
    for(int i=1;i<=n;++i){
        pre[i]=ask1(a[i]-1);
        add1(a[i]),add2(a[i],a[i]);
        sm+=a[i];
        prec[i]=sm-ask2(a[i])+a[i];
    }
    sm=0;
    memset(B1,0,sizeof B1);
    memset(B2,0,sizeof B2);
    for(int i=n;i;--i){
        suf[i]=ask1(a[i]-1);
        add1(a[i]),add2(a[i],a[i]);
        sm+=a[i];
        sufc[i]=sm-ask2(a[i])+a[i];
    }
    for(int i=1;i<=m;++i)
        cin>>q[i].l>>q[q[i].id=i].r;
    sort(q+1,q+m+1);
    for(int i=1,l=1,r=0;i<=m;++i){
        if(r<q[i].r)L[l].push_back((vue){r+1,q[i].r,q[i].id,1});
        if(r>q[i].r)L[l].push_back((vue){q[i].r+1,r,q[i].id,-1});
        r=q[i].r;
        if(l>q[i].l)R[r].push_back((vue){q[i].l,l-1,q[i].id,1});
        if(l<q[i].l)R[r].push_back((vue){l,q[i].l-1,q[i].id,-1});
        l=q[i].l;
    }
    for(int i=1;i<=n;++i){
        for(int x=0;x<L[i].size();++x){
            int l=L[i][x].l,r=L[i][x].r,id=L[i][x].id;
            LL s=0;
            for(int p=l;p<=r;++p)
                s+=(LL)a[p]*(pre[p]-getcnt(a[p]))+prec[p]-getmx(a[p]);
            ans[id]+=s*L[i][x].fh;
        }
        update(a[i]);
    }
    memset(tc,0,sizeof tc),memset(ts,0,sizeof ts);
    memset(bc,0,sizeof bc),memset(bs,0,sizeof bs);
    for(int i=n;i;--i){
        for(int x=0;x<R[i].size();++x){
            int l=R[i][x].l,r=R[i][x].r,id=R[i][x].id;
            LL s=0;
            for(int p=l;p<=r;++p)
                s+=(LL)a[p]*(suf[p]-getcnt(a[p]))+sufc[p]-getmx(a[p]);
            ans[id]+=s*R[i][x].fh;
        }
        update(a[i]);
    }
    for(int i=2;i<=m;++i)
        ans[q[i].id]+=ans[q[i-1].id];
    for(int i=1;i<=m;++i)
        cout<<ans[i]<<'\n';
    return 0;
}