[Ynoi2019模拟赛]Yuno loves sqrt technology II

题目大意：

给定一个数列，每次询问区间逆序对数，不强制在线。

题解：

如果不强制在线的话，我们可以离线下来搞一个莫队，每次指针左右移动的时候相当于查当前区间中有多少数比它大或者有多少数比它小，这个需要用树状数组维护，时间复杂度\(O(n\sqrt{n}logn)\)。

但是\(300ms\)跑不出来。。。

于是我们观察指针左右移动的时候我们都需要查询些什么？

比如说左端点向左移动，我们相当于是查询\(l \sim r\)中有多少数比\(a[l-1]\)小。

然后搞成前缀和相减，弄成\(1\sim r\) 和\(1 \sim l-1\)，观察到后面那个是\(1\sim l-1\)中有多少个数比\(a[l-1]\)小，这个东西只有一个变量，所以可以提前预处理出来。

那么我们只有前一种问题了。

我们再次把这些问题离线，每个询问挂到\(r\)上，然后依次从\(1-n\)扫描，然后再进行分块，每次添加一个数可以\(\sqrt n\)的做，这样查询可以做到\(O(1)\)，于是我们的总复杂度是\(O(m\sqrt n+n\sqrt n)\)。

注意到我们的总询问有\(m\sqrt n\)个，\(32MB\)存不下。。

毒瘤出题人。

注意到每次指针移动会是一段区间，所以每次存询问的时候直接把整段区间存下来就好了，所以空间就是\(O(m)\)的了。

#include<bits/stdc++.h> #define N 100009 using namespace std; typedef long long ll; int n,n1,q,be[N],c[N],bl[N],bel,a[N]; int sum1[N],sum0[N],san0[N],san1[N],pre0[N],pre1[N],ys[N]; ll ans[N]; inline ll rd(){ll x=0;char c=getchar();bool f=0;while(!isdigit(c)){if(c=='-')f=1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return f?-x:x; } struct node{int l,r,id;inline bool operator <(const node &b)const{if(be[l]!=be[b.l])return be[l]<be[b.l];return (be[l]&1)?r<b.r:r>b.r;} }b[N]; struct node2{int be,l,r,tag,opt; }; vector<node2>vec[N]; vector<node2>::iterator it; struct BIT{int tr[N];inline void add(int x,int y){while(x<=n)tr[x]+=y,x+=x&-x;}inline int query(int x){int ans=0;while(x)ans+=tr[x],x-=x&-x;return ans;}inline void clear(){memset(tr,0,sizeof(tr));} }tr; int main(){n=rd();q=rd();n1=sqrt(n);for(int i=1;i<=n;++i)a[i]=rd(),c[++c[0]]=a[i];sort(c+1,c+c[0]+1);c[0]=unique(c+1,c+c[0]+1)-c-1;for(int i=1;i<=n;++i)a[i]=lower_bound(c+1,c+c[0]+1,a[i])-c;for(int i=1;i<=n;++i){pre0[i]=tr.query(a[i]-1);tr.add(a[i],1);}tr.clear();for(int i=1;i<=n;++i){pre1[i]=tr.query(n-a[i]);tr.add(n-a[i]+1,1);}for(int i=1;i<=n;++i)be[i]=(i-1)/n1+1;for(int i=1;i<=q;++i){b[i].l=rd();b[i].r=rd();b[i].id=i;}sort(b+1,b+q+1);int l=1,r=1;for(int i=1;i<=q;++i){while(l>b[i].l){for(int j=b[i].l;j<l;++j){ans[i]-=pre0[j];}vec[r].push_back(node2{i,b[i].l,l-1,0,1});l=b[i].l;}while(r<b[i].r){for(int j=r+1;j<=b[i].r;++j){ans[i]+=pre1[j];}if(l!=1){vec[l-1].push_back(node2{i,r+1,b[i].r,1,-1});} r=b[i].r;}while(l<b[i].l){for(int j=l;j<b[i].l;++j){ans[i]+=pre0[j];}vec[r].push_back(node2{i,l,b[i].l-1,0,-1});l=b[i].l;} while(r>b[i].r){for(int j=b[i].r+1;j<=r;++j){ans[i]-=pre1[j];}vec[l-1].push_back(node2{i,b[i].r+1,r,1,1});r=b[i].r;}ys[b[i].id]=i;}int bel=sqrt(c[0]);for(int i=1;i<=c[0];++i)bl[i]=(i-1)/bel+1;for(int i=1;i<=n;++i){int now=bl[a[i]];for(int j=now;j<=bl[c[0]];++j)sum0[j]++;for(int j=a[i];j<=min(c[0],bel*now);++j)san0[j]++;now=bl[c[0]-a[i]+1];for(int j=now;j<=bl[c[0]];++j)sum1[j]++;for(int j=c[0]-a[i]+1;j<=min(c[0],bel*now);++j)san1[j]++;for(it=vec[i].begin();it!=vec[i].end();++it){node2 x=*it;if(!x.tag){int tmp=0;for(int j=x.l;j<=x.r;++j){int now=bl[a[j]];int xx=sum0[now-1];if(bl[a[j]-1]==bl[a[j]])xx+=san0[a[j]-1];tmp+=xx;ans[x.be]+=x.opt*xx;} }else{int tmp=0;for(int j=x.l;j<=x.r;++j){int now=bl[c[0]-a[j]+1];int xx=sum1[now-1];tmp+=xx;if(bl[c[0]-a[j]]==bl[c[0]-a[j]+1])xx+=san1[c[0]-a[j]];ans[x.be]+=x.opt*xx;}}}}for(int i=1;i<=q;++i)ans[i]+=ans[i-1];for(int i=1;i<=q;++i)printf("%lld\n",ans[ys[i]]);return 0; }

转载于:https://www.cnblogs.com/ZH-comld/p/10889603.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的[Ynoi2019模拟赛]Yuno loves sqrt technology II的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。