首页 > 代码库 > BZOJ3295 [Cqoi2011]动态逆序对

BZOJ3295 [Cqoi2011]动态逆序对

Description

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

Input

输入第一行包含两个整数nm,即初始元素的个数和删除的元素个数。以下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,表示插入时间。
 
 
 1 //It is made by ljh2000
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <ctime>
 9 #include <vector>
10 #include <queue>
11 #include <map>
12 #include <set>
13 using namespace std;
14 typedef long long LL;
15 const int inf = (1<<30);
16 const int MAXN = 100011;
17 int n,m,c[MAXN],match[MAXN],ans[MAXN];
18 LL Ans;
19 struct node{
20     int x,y,t;
21     int flag;
22 }a[MAXN],b[MAXN];
23 inline bool cmpx(node q,node qq){ if(q.x==qq.x) return q.y<qq.y; return q.x<qq.x; }
24 inline bool cmpt(node q,node qq){ return q.t<qq.t; }
25 inline void add(int x,int val){ while(x<=n) c[x]+=val,x+=x&(-x); }
26 inline int query(int x){int tot=0; while(x>0) tot+=c[x],x-=x&(-x); return tot;  }
27 inline int getint()
28 {
29     int w=0,q=0; char c=getchar();
30     while((c<0 || c>9) && c!=-) c=getchar(); if(c==-) q=1,c=getchar(); 
31     while (c>=0 && c<=9) w=w*10+c-0, c=getchar(); return q ? -w : w;
32 }
33 
34 inline void CDQ(int l,int r){
35     if(l>=r) return ; int mid=(l+r)>>1,size=r-l+1,cnt=0;
36     for(int i=l;i<=mid;i++) b[++cnt]=a[i],b[cnt].flag=0; for(int i=mid+1;i<=r;i++) b[++cnt]=a[i],b[cnt].flag=1;
37     sort(b+1,b+cnt+1,cmpx); //for(int i=1;i<=n;i++) c[i]=0;
38     for(int i=1;i<=size;i++) {
39     if(b[i].flag==0) add(b[i].y,1);
40     else ans[b[i].t]+=query(n)-query(b[i].y);
41     }
42     for(int i=1;i<=size;i++) if(b[i].flag==0) add(b[i].y,-1);
43     for(int i=size;i>=1;i--) {
44     if(b[i].flag==0) add(b[i].y,1);
45     else ans[b[i].t]+=query(b[i].y);
46     }
47     for(int i=1;i<=size;i++) if(b[i].flag==0) add(b[i].y,-1);
48     CDQ(l,mid); if(mid<r) CDQ(mid+1,r);
49 }
50 
51 inline void work(){
52     n=getint(); m=getint(); for(int i=1;i<=n;i++) { a[i].x=i; a[i].y=getint(); match[a[i].y]=i; } int cc=n,x;
53     for(int i=1;i<=m;i++) { x=getint(); a[match[x]].t=cc--; }  for(int i=1;i<=n;i++) if(a[i].t==0) a[i].t=cc--;
54     sort(a+1,a+n+1,cmpt); CDQ(1,n);
55     for(int i=1;i<=n;i++) Ans+=ans[i];
56     for(int i=n;i>n-m;i--) {
57     printf("%lld\n",Ans);
58     Ans-=ans[i];
59     }
60 }
61 
62 int main()
63 {
64     work();
65     return 0;
66 }

 

BZOJ3295 [Cqoi2011]动态逆序对