二次离线与值域分块

· · 题解

二次离线莫队，是一种可以做到 O(n\sqrt m+nk) 时间，O(n) 空间的莫队算法。

一般需要一个数字对于一个区间的贡献具有结合律且问题不强制在线。

设 ans(x,[l,r]) 表示第 x 个数字对区间 [l,r] 的贡献，则 ans(x,[l,r])=a_x\times(1+\sum_{l\le i\le r}[a_i<a_x])+\sum_{l\le i\le r}[a_i>a_x]\times a_x 发现两部分都具有结合律，均可以简化为单点修改，区间查询的问题，用树状数组维护莫队可以做到 O(n\sqrt m\log_2n)，显然过不去。

我们只需要计算 ans(l,[l,r]) 与 ans(r,[l,r])（自己对自己不会产生贡献，所以 ans(l,[l,r])=ans(l,[l+1,r])）。

差分一下：ans(l,[l,r])=ans(l,[1,r])-ans(l,[1,l-1])=ans(l,[1,r])-ans(l,[1,l])，ans(r,[l,r])=ans(r,[1,r])-ans(r,[1,l-1])，其中 ans(l,[1,l]) 可以预处理另一部分可以在第二遍扫描时统一计算。

发现另一部分的查询次数是 O(n\sqrt m) 的，所以需要采用 O(1) 查询的数据结构，可以使用值域分块，可以做到 O(\sqrt C) 修改，O(1) 查询。

总时间复杂度：O(n(\sqrt m+\sqrt C))，空间复杂度：O(n+m+C)。

开 O2 只需 1.65s，真的不卡常！

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e5+5,C=2e5+5,K=305;
inline void File(){
#ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
#endif
}
namespace fast_io{
    char ib[N+5],ob[N+85],stk[85];
    int it,ed,c,ot,t;
#define _gc (it==ed&&(ed=(it=0)+fread(ib,1,N,stdin),it==ed))?EOF:ib[it++]
    inline void read(int &x){
        for(c=_gc;c<48;c=_gc);
        for(x=0;c>47;c=_gc)x=x*10+(48^c);
    }
    inline void flush(){
        fwrite(ob,1,ot,stdout),ot=0;
    }
    inline void write(ll x,char c='\n'){
        t=0;while(x)stk[++t]=48^(x%10),x/=10;
        while(t)ob[ot++]=stk[t--];
        ob[ot++]=c;if(ot>N)flush();
    }
};using fast_io::read;
using fast_io::write;
int n,m,ql[N],qr[N],qt;
int a[N],ct[C],Ct[K],mp[C],mt,p[N];
ll ans[N],fc[N],sm[C],Sm[C];
struct adt{int l,r,id,tp;};
vector<adt>G[N];
inline void add(int x){
    int i,d=a[x]+1;
    for(i=d;(i>>9)==(d>>9);++i)++ct[i];
    for(i=(d>>9)+1;i<=256;++i)++Ct[i];d-=2;
    for(i=d;(i>>9)==(d>>9);--i)sm[i]+=a[x];
    for(i=(d>>9)-1;i>=0;--i)Sm[i]+=a[x];
}
inline ll get(int d){
    return Sm[d>>9]+sm[d]+ll(Ct[d>>9]+ct[d])*d;
}
signed main(){
    File();
    read(n),read(m),qt=1+n/(1+sqrt(m));
    int i,j,L,l,R,r;
    for(i=1;i<=n;++i)
        read(a[i]),fc[i]=get(a[i]),add(i);
    memset(Sm,0,sizeof(Sm));
    memset(Ct,0,sizeof(Ct));
    memset(sm,0,sizeof(sm));
    memset(ct,0,sizeof(ct));
    for(i=1;i<=m;++i)
        read(ql[i]),read(qr[i]),p[i]=i;
    stable_sort(p+1,p+m+1,[&](int x,int y){
        return (ql[x]/qt==ql[y]/qt)?((ql[x]/qt)&1)?
        qr[x]<qr[y]:qr[x]>qr[y]:ql[x]<ql[y];
    });
    l=1,r=0;
    for(i=1;i<=m;++i){
        L=ql[p[i]],R=qr[p[i]];
        if(l>L){
            if(r)G[r].push_back({L,l-1,p[i],1});
            while(l>L)--l,ans[p[i]]-=fc[l]-a[l];
        }if(r<R){
            if(l>1)G[l-1].push_back({r+1,R,p[i],-1});
            while(r<R)++r,ans[p[i]]+=fc[r]+a[r];
        }
//      printf("l:%d r:%d ans[i]:%d\n",l,r,ans[i]);
        if(l<L){
            if(r)G[r].push_back({l,L-1,p[i],-1});
            while(l<L)ans[p[i]]+=fc[l]-a[l],++l;
        }if(r>R){
            if(l>1)G[l-1].push_back({R+1,r,p[i],1});
            while(r>R)ans[p[i]]-=fc[r]+a[r],--r;
        }
//      printf("l:%d r:%d ans[i]:%d\n",l,r,ans[i]);
//      puts("");
    }
    for(i=1;i<=n;++i){
        add(i);
//      printf("get2:%d\n",get(2));
        for(adt at:G[i])
            for(j=at.l;j<=at.r;++j)
                ans[at.id]+=get(a[j])*at.tp;
    }
//  for(i=1;i<=m;++i)printf("%d ",ans[i]);puts("");
    for(i=1;i<=m;++i)ans[p[i]]+=ans[p[i-1]];
    for(i=1;i<=m;++i)printf("%lld\n",ans[i]);
//      write(ans[i]);
    fast_io::flush();return 0;
}