[DS记录]P6579 [Ynoi2019] Happy Sugar Life

第十三分块。 **题意** ： 给出一个长为 $n$ 的序列 $A$ 。 每次询问给出 $l,r,x,y$ ，求将 $A[l,r]$ 保留 $[x,y]$ 内的值之后的顺序对个数。 允许离线， $n\leq 10^5,m\leq 2\times 10^5$ ，时限$\texttt{4s}$ ，空限$\texttt{128M}$。 - 对于 [$\texttt{NOI}$ 版](https://www.luogu.com.cn/problem/P6774)，时限$\texttt{5s}$ ，空限$\texttt{1G}$。 ------------ 这玩意不弱于区间逆序对，考虑根号做法。 对于某次询问，将贡献分为五类 ： 散块内部，两个散块之间，整块内部，整块之间，整块和散块之间。 枚举散块内部的所有元素，计算其与后方元素之间的贡献。这是查询“区间内 $[x,y]$ 内的数的个数” 类似二次离线莫队，将询问离线后用值域分块扫描线求解，复杂度为 $O\big((n+m)\sqrt{n}\big)$。 这解决了“整块和散块之间”，“两个散块之间”，“散块内部”三种贡献。 下面我们只需要考虑“整块内部”，“整块之间”这两种贡献。 对于块内，进行离散化，只有 $O(\sqrt{n}\times \sqrt{n})=O(n)$ 种本质不同的至于区间。 记 $s_{i,x,y}$ 表示块 $i$ 中 $[x,y]$ （$x,y$ 已离散化）中的顺序对数，可以类似二维前缀和递推求解。 查询时，为了避免二分，还要维护一个离散化映射表。 对于块间，先考虑 $x=1$ 的情况。 将元素从小到大排序，逐个加入。维护每个块内出现的数的个数，$w_{i,j}$ 为块 $i\sim j-1$ 与 $j$ 之间的顺序对。 插入 $A_k$ 时只需更新 $w_{\_,k}$ ，查询时答案是 $\sum_{i=l}^rw_{l,i}$。这样插入和查询就都能做到 $O(\sqrt{n})$。 考虑 $x>1$ 的情况。 首先用 $\leq y$ 的答案减去 $<x$ 的答案，然后只剩 $[x,y]\rightarrow [1,x)$ 的错误贡献。 枚举每个块，考虑其中 $[x,y]$ 内的数，询问是“查询块 $l\sim r$ 内有多少个 $\leq x$ 的数”。 记 $o_{i,j}$ 表示前 $i$ 个块中有多少个数 $\leq j$ ，预处理只有容易回答上述询问。 逐块处理以节省空间。 时间复杂度 $O((n+m)\sqrt{n})$ ，空间复杂度 $O(n+m)$。 常数较小，最大点 $\texttt{1.28s}$。 ```cpp #include<algorithm> #include<cstdio> #include<vector> #include<cmath> #define pb emplace_back #define ll long long #define MaxN 100500 #define MaxM 200500 using namespace std; int n; struct SumDS { int t[MaxN],blo[MaxN],BS; void add(int p){ int br=p/BS*BS+BS; for (int i=p;i<br;i++)t[i]++; for (int i=p/BS+1;i*BS<=n;i++)blo[i]++; } inline int qry(int p) {return blo[p/BS]+t[p];} }T; ll ans[MaxM]; struct Data2{int l,r,x,y,p;bool op;}b2[MaxM<<2]; vector<int> t1[MaxN],t2[MaxN]; int a[MaxN],tn,stk[MaxM<<1],top; #define adt(p,x) if (p<0)ans[-p]-=x;else ans[p]+=x; void calc() { for (int i=1;i<=n;i++){ for (int j=0;j<t2[i].size();j++)stk[++top]=t2[i][j]; int sav=top;top=0; for (int j=1;j<=sav;j++){ Data2 &now=b2[stk[j]]; if (now.x<=a[i]&&a[i]<=now.y){ int buf=now.op ? T.qry(a[i]-1)-T.qry(now.x-1): T.qry(now.y)-T.qry(a[i]); adt(now.p,buf); }if (i<now.r)stk[++top]=stk[j]; }T.add(a[i]); for (int j=0;j<t1[i].size();j++){ Data2 &now=b2[t1[i][j]]; int sav=now.op ? T.qry(now.x-1) : T.qry(now.y),ret=0; if (now.op){ for (int k=now.l;k<=now.r;k++) if (now.x<=a[k]&&a[k]<=now.y) ret+=T.qry(a[k]-1)-sav; }else for (int k=now.l;k<=now.r;k++) if (now.x<=a[k]&&a[k]<=now.y) ret+=sav-T.qry(a[k]); adt(now.p,ret); } } } void adl(int l,int r,int L,int x,int y,int p){ b2[++tn]=(Data2){l,r,x,y,p,1};t2[l].pb(tn); b2[++tn]=(Data2){l,r,x,y,-p,1};t1[L-1].pb(tn); } void adl2(int l,int r,int R,int x,int y,int p){ b2[++tn]=(Data2){l,r,x,y,p,0};t1[R].pb(tn); b2[++tn]=(Data2){l,r,x,y,-p,0};t2[l].pb(tn); } struct Data{int l,r,x,y;}b[MaxM]; int m,BS,sa[MaxN],sx[MaxN],tp[MaxN],tp2[505],*cb=tp2,s[505][505] ,o[MaxN],sav1[MaxM],sav2[MaxM]; void calc2() { for (int k=1;k*BS+BS<=n;k++){ int bl=k*BS,br=bl+BS; for (int i=bl;i<br;i++)sx[i]=a[i]; sort(sx+bl,sx+br);sx[bl-1]=0;sx[br]=n+1; for (int i=bl-1;i<br;i++) for (int j=sx[i];j<sx[i+1];j++) tp[j]=i-bl+1; for (int i=bl;i<br;i++) tp2[sa[i]=lower_bound(sx+bl,sx+br,a[i])-sx-bl+1]=i; for (int i=BS;i;i--) for (int j=i+1;j<=BS;j++) s[i][j]=s[i+1][j]+s[i][j-1]-s[i+1][j-1]+(tp2[i]<tp2[j]); for (int i=1;i<=m;i++){ if (b[i].l<bl&&br<=b[i].r){ ans[i]+=s[tp[b[i].x-1]+1][tp[b[i].y]]; int cnt=tp[b[i].y]-tp[b[i].x-1]; sav2[i]+=cnt; ans[i]-=1ll*cnt*o[b[i].x-1]; }if (b[i].l/BS+1==k)sav1[i]=o[b[i].x-1]; }for (int i=1;i<=n;i++)o[i]+=tp[i]; } for (int i=1;i<=m;i++) ans[i]+=1ll*sav1[i]*sav2[i]; } struct Data3{int l,r,p;}; vector<Data3> t[MaxN]; ll qry(int l,int r){ ll ret=0; for (int i=l+1;i<=r;i++)ret+=s[l][i]; return ret; } void calc3() { for (int i=1;i<=n;i++)tp[a[i]]=i; for (int i=0;i*BS<=n;i++) {cb[i]=0;for (int j=0;j*BS<=n;j++)s[i][j]=0;} for (int i=1;i<=m;i++){ int tl=b[i].l/BS+1,tr=b[i].r/BS-1; if (tl>tr)continue; t[b[i].x-1].pb((Data3){tl,tr,-i}); t[b[i].y].pb((Data3){tl,tr,i}); } for (int x=1;x<=n;x++){ int tb=tp[x]/BS;cb[tb]++; for (int i=tb-1,sum=0;i>=0;i--) {sum+=cb[i];s[i][tb]+=sum;} for (int i=0;i<t[x].size();i++) adt(t[x][i].p,qry(t[x][i].l,t[x][i].r)); } } int main() { scanf("%d%d",&n,&m); BS=sqrt(n)+1; T.BS=sqrt(n)+1; for (int i=1;i<=n;i++)scanf("%d",&a[i]); for (int i=1,l,r,x,y;i<=m;i++){ scanf("%d%d%d%d",&l,&r,&x,&y); if (l/BS==r/BS)adl(l,r,l,x,y,i); else { int br=l/BS*BS+BS,bl=r/BS*BS; adl2(l,br-1,bl-1,x,y,i); adl(bl,r,l,x,y,i); }b[i]=(Data){l,r,x,y}; }calc();calc2();calc3(); for (int i=1;i<=m;i++) printf("%lld\n",ans[i]); return 0; } ```