题解 P5047 【[Ynoi2019模拟赛]Yuno loves sqrt technology II】

~~【模板】二次离线莫队~~ ## 本题题解 相信打过luogu月赛的人都会对 _第十四分块(前体)_ 那题印象深刻 因为这个科技可以搞定一些转移复杂度非常大的莫队问题 我们首先考虑一下用传统的莫队怎么解决这个问题 当你在(l,r)前面插入一个值v的时候相当于问你(l,r)当中有几个点的值小于v，而在(l,r)后边插入一个值v的时候相当于问你(l,r)当中有几个点的值大于v 那么我们可以采用一个树状数组来回答这个问题，复杂度显然$O(Nlogn\sqrt{M})$ 而且这个复杂度应该是不可优化的，因为我们做了$O(N\sqrt{M})$次修改和询问所以说我们使用树状数组来维护信息是个正确的决定 那么假如我们有一种黑科技可以让你做到仅仅有$O(n)$次插入操作而有$O(N\sqrt{M})$询问的话，我们就可以将维护数据信息的数据结构由树状数组换成分块,这样的话复杂度就被平衡到了$O(N(\sqrt{N}+\sqrt{M}))$ 而二次离线莫队就是这样一个科技 这个思想的精髓就是把询问$(l,r)$这个区间中有多少个数字比l大或者小的操作变成询问(1,l-1)这个区间中有多少个数字比v大或者小，然后询问(1,r)当中有多少个数字比v大或者小 那么此时我们将莫队的询问操作接着离线，我们就就可以跑一遍扫描线回答所有的询问了，显然这个过程仅仅需要$O(n)$次插入操作而询问次数依然是$O(N\sqrt{M})$次，用一个分块来维护此时我们的复杂度就是对的 注意一个小细节，你这样算出来的不是每个询问的答案，而是相邻两个询问之间答案的变化量，所以最后做一遍前缀和才是对的 但是问题来了似乎我们做扫描线的空间复杂度是$O(N\sqrt{M})$的，而且你的算法应该会因为cache miss的问题跑的飞慢无比…… 怎么卡空间呢？ 我们实际上要实现这4个操作 右端点左/右移一段距离，左端点左/右移一段距离 那么你手玩一下询问的过程会发现这样一个相当有趣的事实是你对着某一个前缀询问了某一段区间中的值,符号或者正或者负，这是其中一部分东西的贡献，可以在每一个节点下面push一个区间表示询问这段区间中的点来解决 另一部分的贡献则是区间中的点不停的询问自己这个点到自己前面那个前缀的答案，这个东西可以预处理一下，具体来讲和上面的贡献在一次扫描线当中做完,之后再做个前缀和,接下来我们再次扫一下排好序的询问序列，逐个询问考虑完这部分贡献就行了 当然你还是要注意常数的，比如说不要真的去写个vector，自己手写个邻接表又不会少几斤肉，最后不要忘记做个前缀和再输出答案 当然你还是要注意卡空间的，比如说能int就不要瞎开long long,同一个数组可以用来离散化之后接着用来当分块的数组，之类的 上代码~ ```C // luogu-judger-enable-o2 #include<cstdio> #include<algorithm> using namespace std;const int N=1e5+10;const int B=335;typedef long long ll; template <class T> void read(T &x){ char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } int a[N];int bi[N];int su[N];int n;int m;ll ans[N];ll f1[N];ll f2[N];int S; namespace lsh//离散化 { inline bool cmp(const int& x,const int& y){return a[x]<a[y];} inline void pre() { for(int i=1;i<=n;i++)bi[i]=i;sort(bi+1,bi+n+1,cmp);su[1]=1; for(int i=2;i<=n;i++)su[i]=(a[bi[i-1]]==a[bi[i]])?su[i-1]:su[i-1]+1; for(int i=1;i<=n;i++)a[bi[i]]=su[i];S=su[n]; for(int i=1;i<=n;i++)bi[i]=(i-1)/B+1;for(int i=1;i<=n;i++)su[i]=0; } } struct data//手写邻接表 { int l;int r;int t; friend bool operator <(data a,data b) {int t1=a.l/B;int t2=b.l/B;return (t1==t2)?((t1&1)?a.r<b.r:a.r>b.r):t1<t2;} }q[N],ve[N<<1];int al[N];int x[N<<1];int ct; inline void pb(const data& a,int p){if(p==0)return;ve[++ct]=a;x[ct]=al[p];al[p]=ct;} namespace blk//分块加 { int lb[N/B+3]; inline int gt(const int& x){return su[x]+lb[bi[x]];} inline void md(const int& x) { for(int i=x;bi[i]==bi[x];i++)su[i]++; for(int i=bi[x]+1;i<=bi[S];i++)lb[i]++; } } inline void deal(const data& va,const int& p)//处理一个询问 { int t=va.t>>2; switch(va.t&3) { case 0:{for(int i=va.l;i<=va.r;i++)ans[t]-=p-blk::gt(a[i]);break;} case 1:{for(int i=va.l;i<=va.r;i++)ans[t]+=p-blk::gt(a[i]);break;} case 2:{for(int i=va.l;i<=va.r;i++)ans[t]+=blk::gt(a[i]-1);break;} case 3:{for(int i=va.l;i<=va.r;i++)ans[t]-=blk::gt(a[i]-1);break;} } } int main() { read(n);read(m);for(int i=1;i<=n;i++)read(a[i]);lsh::pre(); for(int i=1;i<=m;i++)read(q[i].l),read(q[i].r),q[i].t=i;sort(q+1,q+m+1); int dl=q[1].l;int dr=q[1].r;pb((data){q[1].l,q[1].r,1<<2},q[1].l-1); for(int i=2;i<=m;i++)//二次离线 { if(q[i].l>dr||q[i].r<dl){pb((data){q[i].l,q[i].r,i<<2},q[i].l-1);dl=q[i].l;dr=q[i].r;continue;} if(q[i].r>dr)pb((data){dr+1,q[i].r,i<<2},dl-1);if(q[i].r<dr)pb((data){q[i].r+1,dr,i<<2|1},dl-1); if(q[i].l<dl)pb((data){q[i].l,dl-1,i<<2|2},q[i].r);if(q[i].l>dl)pb((data){dl,q[i].l-1,i<<2|3},q[i].r); dl=q[i].l;dr=q[i].r; } for(int i=1;i<=n;i++)//预处理一个点到它前面前缀的贡献 { f1[i]=(i-1)-blk::gt(a[i]);blk::md(a[i]);f2[i]=blk::gt(a[i]-1); for(int j=al[i];j;j=x[j])deal(ve[j],i); } for(int i=1;i<=n;i++)f1[i]+=f1[i-1];for(int i=1;i<=n;i++)f2[i]+=f2[i-1]; dl=q[1].l;dr=q[1].r;ans[1]+=f1[dr]-f1[dl-1]; for(int i=2;i<=m;i++)//第二部分的贡献 { if(q[i].l>dr||q[i].r<dl){ans[i]+=f1[q[i].r]-f1[q[i].l-1];dl=q[i].l;dr=q[i].r;continue;} if(q[i].r>dr)ans[i]+=f1[q[i].r]-f1[dr];if(q[i].r<dr)ans[i]-=f1[dr]-f1[q[i].r]; if(q[i].l<dl)ans[i]-=f2[dl-1]-f2[q[i].l-1];if(q[i].l>dl)ans[i]+=f2[q[i].l-1]-f2[dl-1]; dl=q[i].l;dr=q[i].r; }for(int i=1;i<=m;i++)if(q[i].l<=q[i-1].r&&q[i].r>=q[i-1].l)ans[i]+=ans[i-1]; for(int i=1;i<=m;i++)f1[q[i].t]=ans[i]; for(int i=1;i<=m;i++)printf("%lld\n",f1[i]);return 0;//拜拜程序~ } ```