題目大意：

給定一個(gè)數(shù)列，每次詢問(wèn)區(qū)間逆序?qū)?shù)，不強(qiáng)制在線。

題解：

如果不強(qiáng)制在線的話，我們可以離線下來(lái)搞一個(gè)莫隊(duì)，每次指針左右移動(dòng)的時(shí)候相當(dāng)于查當(dāng)前區(qū)間中有多少數(shù)比它大或者有多少數(shù)比它小，這個(gè)需要用樹(shù)狀數(shù)組維護(hù)，時(shí)間復(fù)雜度\(O(n\sqrt{n}logn)\)。

但是\(300ms\)跑不出來(lái)。。。

于是我們觀察指針左右移動(dòng)的時(shí)候我們都需要查詢些什么？

比如說(shuō)左端點(diǎn)向左移動(dòng)，我們相當(dāng)于是查詢\(l \sim r\)中有多少數(shù)比\(a[l-1]\)小。

然后搞成前綴和相減，弄成\(1\sim r\) 和\(1 \sim l-1\)，觀察到后面那個(gè)是\(1\sim l-1\)中有多少個(gè)數(shù)比\(a[l-1]\)小，這個(gè)東西只有一個(gè)變量，所以可以提前預(yù)處理出來(lái)。

那么我們只有前一種問(wèn)題了。

我們?cè)俅伟堰@些問(wèn)題離線，每個(gè)詢問(wèn)掛到\(r\)上，然后依次從\(1-n\)掃描，然后再進(jìn)行分塊，每次添加一個(gè)數(shù)可以\(\sqrt n\)的做，這樣查詢可以做到\(O(1)\)，于是我們的總復(fù)雜度是\(O(m\sqrt n+n\sqrt n)\)。

注意到我們的總詢問(wèn)有\(m\sqrt n\)個(gè)，\(32MB\)存不下。。

毒瘤出題人。

注意到每次指針移動(dòng)會(huì)是一段區(qū)間，所以每次存詢問(wèn)的時(shí)候直接把整段區(qū)間存下來(lái)就好了，所以空間就是\(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; }

轉(zhuǎn)載于:https://www.cnblogs.com/ZH-comld/p/10889603.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的[Ynoi2019模拟赛]Yuno loves sqrt technology II的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。