BZOJ3295 [Cqoi2011]动态逆序对

时间：2023-03-09 02:19:03
BZOJ3295 [Cqoi2011]动态逆序对

本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。

本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！

Description

对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

Input

输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。

Output

输出包含m行，依次为删除每个元素之前，逆序对的个数。

Sample Input

5 4
1
5
3
4
2
5
1
4
2

Sample Output

5
2
2
1

样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

HINT

N<=100000 M<=50000

正解：CDQ分治
解题报告：
　　CDQ分治裸题。其实也是树套树裸题，那么拿来当CDQ练手吧。
　　考虑把删除变成倒着插入，那么我给每个坐标一个权值t，表示插入时间。那么第一个删除的t坐标当然是n，表示最后一个插入。然后为了方便，我们把未被删除的结点的t坐标从左往右设为1、2、3...
　　考虑问题转换成了求对于(t0,x0,y0)满足t<t0,x<x0,y>y0的(t,x,y)的个数，这样就变成了三维偏序的裸题了。细节上有必要再说一下：
　　首先CDQ分治之前按t排序，保证t已经有序，在每次分治内部，按x排序，正着扫整个区间的时候，对于[mid+1,r]的区间就在树状数组上查询大于他的y的值的数量；倒着扫，对于[mid+1,r]的区间就在树状数组上查询小于他的y的值的数量。因为左边的所有元素对于右边的所有元素而言，是可以肯定t要小一些的，所以CDQ分治就可以巧妙地解决三维偏序的问题。之后在递归处理左边右边就可以了，同样的做法。
　　ps：我开始T了两发，犯的是写CDQ分治的常见错误，就是在分治里面清空了数组，事实上只要清除刚才打上去的标记就可以了，无需清空。
 //It is made by ljh2000

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <ctime>

 #include <vector>

 #include <queue>

 #include <map>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int inf = (<<);

 const int MAXN = ;

 int n,m,c[MAXN],match[MAXN],ans[MAXN];

 LL Ans;

 struct node{

     int x,y,t;

     int flag;

 }a[MAXN],b[MAXN];

 inline bool cmpx(node q,node qq){ if(q.x==qq.x) return q.y<qq.y; return q.x<qq.x; }

 inline bool cmpt(node q,node qq){ return q.t<qq.t; }

 inline void add(int x,int val){ while(x<=n) c[x]+=val,x+=x&(-x); }

 inline int query(int x){int tot=; while(x>) tot+=c[x],x-=x&(-x); return tot;  }

 inline int getint()

 {

     int w=,q=; char c=getchar();

     while((c<'' || c>'') && c!='-') c=getchar(); if(c=='-') q=,c=getchar();

     while (c>='' && c<='') w=w*+c-'', c=getchar(); return q ? -w : w;

 }

 inline void CDQ(int l,int r){

     if(l>=r) return ; int mid=(l+r)>>,size=r-l+,cnt=;

     for(int i=l;i<=mid;i++) b[++cnt]=a[i],b[cnt].flag=; for(int i=mid+;i<=r;i++) b[++cnt]=a[i],b[cnt].flag=;

     sort(b+,b+cnt+,cmpx); //for(int i=1;i<=n;i++) c[i]=0;

     for(int i=;i<=size;i++) {

     if(b[i].flag==) add(b[i].y,);

     else ans[b[i].t]+=query(n)-query(b[i].y);

     }

     for(int i=;i<=size;i++) if(b[i].flag==) add(b[i].y,-);

     for(int i=size;i>=;i--) {

     if(b[i].flag==) add(b[i].y,);

     else ans[b[i].t]+=query(b[i].y);

     }

     for(int i=;i<=size;i++) if(b[i].flag==) add(b[i].y,-);

     CDQ(l,mid); if(mid<r) CDQ(mid+,r);

 }

 inline void work(){

     n=getint(); m=getint(); for(int i=;i<=n;i++) { a[i].x=i; a[i].y=getint(); match[a[i].y]=i; } int cc=n,x;

     for(int i=;i<=m;i++) { x=getint(); a[match[x]].t=cc--; }  for(int i=;i<=n;i++) if(a[i].t==) a[i].t=cc--;

     sort(a+,a+n+,cmpt); CDQ(,n);

     for(int i=;i<=n;i++) Ans+=ans[i];

     for(int i=n;i>n-m;i--) {

     printf("%lld\n",Ans);

     Ans-=ans[i];

     }

 }

 int main()

 {

     work();

     return ;

 }

相关文章