bzoj3295: [Cqoi2011]动态逆序对（cdq分治）

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #define maxn 200001
  7 using namespace std;
  8 
  9 typedef long long ll;
 10 ll ans[maxn],Ans;
 11 int n,m,tot,tsum[maxn],num[maxn],pos[maxn],sum[maxn],_num[maxn];
 12 bool bo[maxn];
 13 
 14 struct date{
 15     int bo,id,x,y;
 16 }qs[maxn],temp[maxn];
 17 
 18 int lowbit(int x){
 19     return x&(-x);
 20 }
 21 
 22 void insert(int x,int y){
 23     for (int i=x;i<=n;i+=lowbit(i)) sum[i]+=y;
 24 }
 25 
 26 int qsum(int x){
 27     int tmp=0; for (int i=x;i;i-=lowbit(i)) tmp+=sum[i]; 
 28     return tmp;
 29 }
 30 
 31 void tinsert(int x){
 32     for (int i=x;i<=n;i+=lowbit(i)) tsum[i]++;
 33 }
 34 
 35 int tqsum(int x){
 36     int tmp=0;
 37     for (int i=x;i>0;i-=lowbit(i)){
 38         tmp+=tsum[i];
 39     }
 40     return tmp;
 41 }
 42 
 43 bool comp(date x,date y){
 44     return x.x<y.x;
 45 }
 46 
 47 bool comp2(date x,date y){
 48     return x.id<y.id;
 49 }
 50 
 51 void cdq_solve(int l,int r){
 52     if (l==r) return;
 53     int mid=(l+r)/2,tmp=0; cdq_solve(l,mid),cdq_solve(mid+1,r);
 54     sort(qs+l,qs+mid+1,comp),sort(qs+mid+1,qs+r+1,comp);
 55     for (int i=l,j=mid+1;j<=r;){
 56         for (;i<=mid&&qs[i].bo==2;i++);
 57         for (;j<=r&&qs[j].bo==1;j++);
 58         if (j>r) break;
 59         if (qs[i].x<qs[j].x&&i<=mid) insert(qs[i].y,1),tmp=i++;
 60         else ans[qs[j].id]+=qsum(qs[j].y-1),j++;
 61     }
 62     for (int i=l;i<=tmp;i++) if (qs[i].bo==1) insert(qs[i].y,-1); 
 63 }
 64 
 65 int main(){
 66 //    freopen("dtnxd.in","r",stdin);
 67 //    freopen("dtnxd.out","w",stdout);
 68     int u,v;
 69     memset(sum,0,sizeof(sum));
 70     memset(tsum,0,sizeof(tsum)),Ans=0;
 71     memset(bo,0,sizeof(bo));
 72     memset(ans,0,sizeof(ans));
 73     scanf("%d%d",&n,&m),tot=0;
 74     for (int i=1;i<=n;i++) scanf("%d",&u),pos[u]=i,_num[i]=u;
 75     for (int i=m;i>=1;i--) scanf("%d",&num[i]),bo[pos[num[i]]]=1;
 76     for (int i=n;i>=1;i--){
 77         if (bo[i]==0){
 78             Ans+=tqsum(_num[i]-1);
 79             tinsert(_num[i]);
 80         }
 81     }
 82     for (int i=1;i<=n;i++){
 83         if (!bo[i]) u=_num[i],++tot,qs[tot].bo=1,qs[tot].x=u,qs[tot].y=i,qs[tot].id=tot;
 84     }
 85     for (int i=1;i<=m;i++){
 86         u=num[i],v=pos[u];
 87         qs[++tot].bo=1,qs[tot].x=u,qs[tot].y=v,qs[tot].id=tot;
 88         qs[++tot].bo=2,qs[tot].x=u,qs[tot].y=v,qs[tot].id=tot;
 89     }
 90 //    for (int i=1;i<=tot;i++) printf("%d %d %d %d
",qs[i].x,qs[i].y,qs[i].bo,qs[i].id);
 91     for (int i=1;i<=tot;i++){
 92         temp[i]=qs[i];
 93         qs[i].x=n+1-qs[i].x;
 94     }
 95     cdq_solve(1,tot);
 96     for (int i=1;i<=tot;i++){
 97         qs[i]=temp[i];
 98         qs[i].y=n+1-qs[i].y;
 99     }
100     cdq_solve(1,tot);
101     sort(qs+1,qs+tot+1,comp2);
102 //    for (int i=1;i<=tot;i++) printf("%d %lld
",i,ans[i]);
103     for (int i=1;i<=tot;i++) ans[i]+=ans[i-1];
104     for (int i=tot;i>0;i--) if (qs[i].bo==2) printf("%lld
",ans[i]+Ans);
105     return 0;
106 }

View Code

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3295

题目大意：见上一篇博客。

做法：上一篇博客中，我介绍了树套树的做法，现在我来讲讲cdq分治的做法。

求逆序对的常用做法除了用树状数组维护以外，还可以用归并排序求，其本质是cdq分治。

cdq分治做法：

题目中是删除一些数，我们可以离线，看作是往序列中不断地加入一些数每加入一个数字，我们考虑它对答案带来的影响，它对答案的影响就是ans+=目前的序列中排在它前面的比它大的数的个数+排在它后面的比它小的数的个数。简化之后就是给定若干个三元组（x，y，z），x就是题目中操作的顺序（稍微调整一下即可），y表示这个数的权值，z表示这个数的位置，这些三元组中有些是询问，有些是修改，对于询问，就是求修改中x比它的X小的、y比它的Y大的、z比它的小的个数+修改中x比它的X小的、y比它的小的、z比它的大的个数，对于这种三维偏序问题，我们考虑cdq分治，第一维分治外层，第二维排序，第三位树状数组维护即可。

cdq分治+树状数组