有关二次离线和 Yuno loves sqrt technology II

短命女 2021-10-15 09:29 90阅读 0赞

# 二次离线 #

## 前置技能 ##

*  莫队
 *  修改查询 \\(O(\\sqrt n )-O(1)\\) 平衡
    
    ## 概念 ##
 *  考虑朴素莫队离线询问，过程中维护信息从 \\(\[l,r\]\\) 扩展为 \\(\[l\\pm 1,r\\pm 1\]\\) ，本质上就是要询问共 \\(O(n\\sqrt m)\\) 次形如第 \\(r\\) 个元素与区间 \\(\[l,r-1\]\\) 产生的贡献。
 *  当然，如果这个贡献可以差分为 \\(\[1,r-1\]\\) 与 \\(r\\) 的贡献和 \\(\[1,l-1\]\\) 与 \\(r\\) 的贡献，那么就可以尝试使用二次离线了。
 *  具体的，我们发现形如 \\(\[1,r-1\]\\) 与 \\(r\\) 的贡献只有 \\(n\\) 个，可以直接尝试 \\(O(n\\sqrt n)\\) 或 \\(O(\\ poly(n)\\ \\log n)\\) 等复杂度处理，如果嫌麻烦，也可以放到下一段类似的处理。
 *  然后对于 \\(O(n\\sqrt m)\\) 次询问形如 \\(\[1,k\]\\) 与 \\(r\\) 的贡献，我们考虑扫描线，每次从 \\(\[1,k\]\\) 扩展为 \\(\[1,k+1\]\\) ，这样一共为 \\(n\\) 次修改，而在过程中我们要进行 \\(O(n\\sqrt m)\\) 询问。而我们可以调整我们维护数据结构的方式，使得每次扩展的复杂度为 \\(O( \\sqrt m)\\)，而询问的复杂度为 \\(O(1)\\)，从而达到平衡复杂度到 \\(O(n\\sqrt m)\\) 级别。
    
    ## 优势 ##
 *  莫队时从 \\(\[l,r\]\\) 扩展为 \\(\[l\\pm 1,r\\pm 1\]\\) 有的时候并不能做到 \\(O(1)\\)，这是因为扩展一次需要查询一次、修改一次，这样修改和查询的次数都为 \\(O(n\\sqrt m)\\)， 本身就不太好平衡。
 *  二次离线可以通过差分将莫队扩展区间变成总共 \\(O(n)\\) 次修改，\\(O(n\\sqrt m)\\) 次查询，就可以平衡了。
    
    ## 扩展 ##
 *  在时间复杂度为 \\(O(n \\sqrt m)\\) 的情况下，其空间复杂度也可以 \\(O(n+m)\\) 。
 *  首先要求 \\(\[1,r-1\]\\) 与 \\(r\\) 的贡献和 \\(\[1,l-1\]\\) 与 \\(r\\) 的贡献中 \\(\[1,r-1\]\\) 与 \\(r\\) 必须预处理，然后所有 \\(\[1,l-1\]\\) 与 \\(r\\) 的贡献对应到每次莫队区间扩展都对应着固定 \\(l\\)，\\(r\\) 是一个连续的区间，变成 \\(O(m)\\) 个区间，可以线性空间存储，扫描线时每次 \\(O(区间长度)\\) 询问即可，总共会询问 \\(O(n\\sqrt m)\\) 次，空间线性。
    
    ## 例题 ##
 *  洛谷P5047 Yuno loves sqrt technology II
 *  离线求区间逆序对，空间 \\(32MB\\)
 *  具体题解就不写了，具体可以参考代码。

#include<bits/stdc++.h> using namespace std; #define LL long long #define debug(x) cerr<<#x<<" = "<<x #define sp <<" " #define el <<endl #define fgx cerr<<" -------------------------------------------------------- "<<endl #define LL long long #define DB double #define LDB long double #define pii pair<int,int> #define mp make_pair #define pb push_back inline int read(){ int nm=0; bool fh=true; char cw=getchar(); for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-'); for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0'); return fh?nm:-nm; } #define M 100020 #define B 330 int n,m,c[M],H[M],be[M],L[620],R[620],tot,tt1,tt2,d1,d2; LL pr[M],sf[M],S[M],ans[M],cur,A[M],W[620]; pii T[M]; inline void add(int k,int dt){for(;k<=n;k+=(k&-k))c[k]+=dt;} inline int qry(int k,int res=0){for(;k;k-=(k&-k))res+=c[k];return res;} struct Q{ int id,ls,rs; inline void gtin(int ID){id=ID,ls=read(),rs=read();} inline bool operator <(const Q&ot)const{ if(be[ls]!=be[ot.ls]) return be[ls]<be[ot.ls]; if(be[ls]&1) return rs<ot.rs; return rs>ot.rs; } }q[M]; struct _Q{ int kt,ps,to,ls,rs; _Q(){} _Q(int _kt,int _ps,int _to,int _ls,int _rs){kt=_kt,ps=_ps,to=_to,ls=_ls,rs=_rs;} }pre[M],suf[M]; bool cmp_pre(_Q a,_Q b){return a.ps<b.ps;} bool cmp_suf(_Q a,_Q b){return a.ps>b.ps;} inline void ins(int x){for(int k=be[x];k<=tot;k++)++W[k];for(int k=x,TP=R[be[x]];k<=TP;++k)++A[k];} inline int calc(int x){return W[be[x]-1]+A[x];} int main(){ n=read(),m=read(); for(int i=1;i<=n;i++) H[i]=read(),T[i]=mp(H[i],i); sort(T+1,T+n+1); for(int i=1;i<=n;i++) H[T[i].second]=i; LL Now=0; for(L[tot=1]=1,R[tot]=B;R[tot]<n;++tot,L[tot]=R[tot-1]+1,R[tot]=R[tot-1]+B); R[tot]=n; for(int i=1;i<=n;i++) be[i]=(i-1)/B+1; for(int i=1;i<=n;i++) Now+=i-1-qry(H[i]),add(H[i],1),pr[i]=Now; for(int i=1;i<=n;i++) add(H[i],-1),sf[i]=Now,Now-=qry(H[i]); for(int i=1;i<=m;i++) q[i].gtin(i); sort(q+1,q+m+1); for(int l=1,r=1,i=1;i<=m;i++){ if(r<q[i].rs) S[i]+=pr[q[i].rs]-pr[r],pre[++tt1]=_Q(-1,l-1,i,r+1,q[i].rs),r=q[i].rs; if(l>q[i].ls) S[i]+=sf[q[i].ls]-sf[l],suf[++tt2]=_Q(-1,r+1,i,q[i].ls,l-1),l=q[i].ls; if(r>q[i].rs) S[i]-=pr[r]-pr[q[i].rs],pre[++tt1]=_Q(1,l-1,i,q[i].rs+1,r),r=q[i].rs; if(l<q[i].ls) S[i]-=sf[l]-sf[q[i].ls],suf[++tt2]=_Q(1,r+1,i,l,q[i].ls-1),l=q[i].ls; } sort(pre+1,pre+tt1+1,cmp_pre),sort(suf+1,suf+tt2+1,cmp_suf),d1=d2=1; while(d1<=tt1&&(!pre[d1].ps)) ++d1; while(d2<=tt2&&suf[d2].ps>n) ++d2; for(int i=1;i<=n&&d1<=tt1;i++) for(ins(H[i]);d1<=tt1&&pre[d1].ps==i;S[pre[d1].to]+=(LL)pre[d1].kt*(LL)(pre[d1].rs-pre[d1].ls+1)*(LL)i,++d1) for(int k=pre[d1].ls;k<=pre[d1].rs;++k) S[pre[d1].to]-=pre[d1].kt*calc(H[k]); memset(A,0,sizeof(A)),memset(W,0,sizeof(W)); for(int i=n;i>0&&d2<=tt2;--i) for(ins(H[i]);d2<=tt2&&suf[d2].ps==i;++d2) for(int k=suf[d2].ls;k<=suf[d2].rs;++k) S[suf[d2].to]+=suf[d2].kt*calc(H[k]); for(int i=1;i<=m;i++) cur+=S[i],ans[q[i].id]=cur; for(int i=1;i<=m;i++) printf("%lld\n",ans[i]); return 0; }

转载于:https://www.cnblogs.com/OYJason/p/11247141.html