https://www.lydsy.com/JudgeOnline/problem.php?id=3295

這個妹妹我曾見過的~~~

之前應該在校內oj寫了，似乎還寫過題解？發現沒寫博客就重新水一遍代碼水一篇博客好了。

把找逆序對的過程想成一個一個往里塞數字然后找每個數字可以組成的逆序對，把最后要去掉的幾個也想成往里塞，所以加一個時間維度用cdq求三維偏序。

1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 #define LL long long 9 #define pa pair<int,int> 10 const int maxn=100010; 11 const LL minf=(LL)5e17; 12 int n,m; 13 struct nod{ 14 int t,id,v;LL ans; 15 }a[maxn]; 16 int b[maxn]={},vis[maxn]={}; 17 LL t[maxn]={}; int sta[maxn]={},tai=0; 18 priority_queue< pa , vector< pa > , greater< pa > >q[2]; 19 20 inline void addt(int x,int v){ while(x<=n){ t[x]+=v; x+=(x&-x); } } 21 inline LL gett(int x){ LL tsn=0; while(x){ tsn+=t[x]; x-=(x&-x); } return tsn; } 22 bool mcmp1(nod aa,nod bb){ 23 if(aa.id!=bb.id)return aa.id<bb.id; 24 return aa.t<bb.t; 25 } 26 bool mcmp2(nod aa,nod bb){ 27 if(aa.t!=bb.t)return aa.t<bb.t; 28 return aa.id<bb.id; 29 } 30 void doit(int l,int r){ 31 if(l==r)return; 32 int mid=(l+r)/2; 33 doit(l,mid); doit(mid+1,r); 34 //x被查找y查找 35 for(int i=l;i<=mid;i++)q[0].push(make_pair(a[i].t,i)); 36 for(int i=mid+1;i<=r;i++)q[1].push(make_pair(a[i].t,i)); 37 tai=0; 38 while(!q[1].empty()){ 39 pa y=q[1].top(); q[1].pop(); 40 if(q[0].empty()){a[y.second].ans+=gett(n)-gett(a[y.second].v);continue;} pa x=q[0].top(); 41 while(x.first<=y.first){ 42 addt(a[x.second].v,1); sta[++tai]=a[x.second].v; 43 q[0].pop(); if(q[0].empty())break; x=q[0].top(); 44 }a[y.second].ans+=gett(n)-gett(a[y.second].v); 45 } 46 while(!q[0].empty())q[0].pop(); 47 for(int i=1;i<=tai;i++)addt(sta[i],-1); 48 49 for(int i=l;i<=mid;i++)q[0].push(make_pair(a[i].t,i)); 50 for(int i=mid+1;i<=r;i++)q[1].push(make_pair(a[i].t,i)); 51 tai=0; 52 while(!q[0].empty()){ 53 pa y=q[0].top(); q[0].pop(); 54 if(q[1].empty()){a[y.second].ans+=gett(a[y.second].v-1);continue;} pa x=q[1].top(); 55 while(x.first<=y.first){ 56 addt(a[x.second].v,1); sta[++tai]=a[x.second].v; 57 q[1].pop(); if(q[1].empty())break; x=q[1].top(); 58 }a[y.second].ans+=gett(a[y.second].v-1); 59 } 60 while(!q[1].empty())q[1].pop(); 61 for(int i=1;i<=tai;i++)addt(sta[i],-1); 62 } 63 int main(){ 64 scanf("%d%d",&n,&m); 65 for(int i=1;i<=n;i++){scanf("%d",&a[i].v);a[i].id=i;a[i].t=i;vis[a[i].v]=i;} 66 for(int i=1;i<=m;i++){scanf("%d",&b[i]);a[vis[b[i]]].t=n+m+1-i;} 67 sort(a+1,a+1+n,mcmp1); doit(1,n); 68 sort(a+1,a+1+n,mcmp2); 69 for(int i=2;i<=n;i++)a[i].ans+=a[i-1].ans; 70 for(int i=1;i<=m;i++)printf("%lld\n",a[n-i+1].ans); 71 return 0; 72 } View Code

?

轉載于:https://www.cnblogs.com/137shoebills/p/9060496.html

總結

以上是生活随笔為你收集整理的BZOJ 3295: [Cqoi2011]动态逆序对 cdq分治的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。