bzoj3295 [Cqoi2011]动态逆序对

Description

对于序列A，它的逆序对数定义为满足i<j，且A_i>A_j的数对(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分治或树状数组套主席树。

这题用来考试，一堆50分暴力，一人写出正解但是没开long long。。

考虑把删除变成插入，那么每次插入是按照时间排序的。那么只要满足i<j，ai>aj，ti<tj，那么这就是一个逆序对。于是这题就变成裸的三维偏序了。

还有一种做法：使用带修改的主席树。每次删除就是直接删除，查询就查出当前数前面比它大的数和当前树后面比它小的数。注意空间优化。

CDQ分治：

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <cmath>
 9 #include <queue>
10 #include <stack>
11 #include <map>
12 #include <set>
13 #define inf (1<<30)
14 #define il inline
15 #define RG register
16 #define ll long long
17 #define lb(x) (x & -x)
18 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
19 
20 using namespace std;
21 
22 struct node{ int x,y,t; }q[100010],qu[100010];
23 
24 ll c[100010],ans[100010],Ans;
25 int match[100010],n,m;
26 
27 il int gi(){
28     RG int x=0,q=0; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
29     if (ch=='-') q=1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q ? -x : x;
30 }
31 
32 il int cmp(const node &a,const node &b){ return a.x<b.x || (a.x==b.x && a.y<b.y) || (a.x==b.x && a.y==b.y && a.t<b.t); }
33 
34 il void add(RG int x,RG int v){ for (RG int i=x;i<=n;i+=lb(i)) c[i]+=(ll)v; return; }
35 
36 il ll query(RG int x){ RG ll res=0; for (RG int i=x;i;i-=lb(i)) res+=c[i]; return res; }
37 
38 il void solve(RG int l,RG int r){
39     if (l>=r) return; RG int mid=(l+r)>>1,t1=l-1,t2=mid;
40     for (RG int i=l;i<=r;++i) if (q[i].t<=mid) add(q[i].y,1); else ans[q[i].t]+=query(n)-query(q[i].y);
41     for (RG int i=l;i<=r;++i) if (q[i].t<=mid) add(q[i].y,-1);
42     for (RG int i=r;i>=l;--i) if (q[i].t<=mid) add(q[i].y,1); else ans[q[i].t]+=query(q[i].y);
43     for (RG int i=r;i>=l;--i) if (q[i].t<=mid) add(q[i].y,-1);
44     for (RG int i=l;i<=r;++i) if (q[i].t<=mid) qu[++t1]=q[i]; else qu[++t2]=q[i];
45     for (RG int i=l;i<=r;++i) q[i]=qu[i]; solve(l,mid),solve(mid+1,r); return;
46 }
47 
48 il void work(){
49     n=gi(),m=gi(); for (RG int i=1;i<=n;++i) q[i].x=i,q[i].y=gi(),match[q[i].y]=i; RG int ti=n,v;
50     for (RG int i=1;i<=m;++i) v=gi(),q[match[v]].t=ti--; for (RG int i=1;i<=n;++i) if (!q[i].t) q[i].t=ti--;
51     sort(q+1,q+n+1,cmp); solve(1,n); for (RG int i=1;i<=n;++i) Ans+=ans[i];
52     for (RG int i=n;i>n-m;--i){ printf("%lld
",Ans); Ans-=ans[i]; } return;
53 }
54 
55 int main(){
56     File("dynamic");
57     work();
58     return 0;
59 }

树状数组+主席树：

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <complex>
 5 #include <cstring>
 6 #include <cstdlib>
 7 #include <cstdio>
 8 #include <vector>
 9 #include <cmath>
10 #include <queue>
11 #include <stack>
12 #include <map>
13 #include <set>
14 #define N (100010)
15 #define il inline
16 #define RG register
17 #define ll long long
18 #define lb(x) (x & -x)
19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
20 
21 using namespace std;
22 
23 int sum[200*N],ls[200*N],rs[200*N],rt[N],a[N],vis[N],n,m,sz;
24 ll ans;
25 
26 il int gi(){
27     RG int x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
28     if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;
29 }
30 
31 il void update(RG int x,RG int &y,RG int l,RG int r,RG int v,RG int fg){
32     if (!y) y=++sz; //节省空间！！！
33     sum[y]=sum[x]+fg,ls[y]=ls[x],rs[y]=rs[x];
34     if (l==r) return; RG int mid=(l+r)>>1;
35     v<=mid ? update(ls[x],ls[y],l,mid,v,fg) : update(rs[x],rs[y],mid+1,r,v,fg);
36 }
37 
38 il int query1(RG int x,RG int l,RG int r,RG int v){
39     if (l==r) return 0; RG int mid=(l+r)>>1;
40     return v<=mid ? query1(ls[x],l,mid,v)+sum[rs[x]] : query1(rs[x],mid+1,r,v);
41 }
42 
43 il int query2(RG int x,RG int l,RG int r,RG int v){
44     if (l==r) return 0; RG int mid=(l+r)>>1;
45     return v<=mid ? query2(ls[x],l,mid,v) : query2(rs[x],mid+1,r,v)+sum[ls[x]];
46 }
47 
48 il void work(){
49     n=gi(),m=gi();
50     for (RG int i=1;i<=n;++i){
51     a[i]=gi(),vis[a[i]]=i;
52     for (RG int x=i;x<=n;x+=lb(x)) update(rt[x],rt[x],1,n,a[i],1);
53     }
54     for (RG int i=2;i<=n;++i)
55     for (RG int x=i-1;x;x-=lb(x)) ans+=query1(rt[x],1,n,a[i]);
56     for (RG int i=1;i<=m;++i){
57     printf("%lld
",ans); RG int k=vis[gi()];
58     for (RG int x=k-1;x;x-=lb(x)) ans-=query1(rt[x],1,n,a[k]);
59     for (RG int x=k;x;x-=lb(x)) ans+=query2(rt[x],1,n,a[k]);
60     for (RG int x=n;x;x-=lb(x)) ans-=query2(rt[x],1,n,a[k]);
61     for (RG int x=k;x<=n;x+=lb(x)) update(rt[x],rt[x],1,n,a[k],-1);
62     }
63     return;
64 }
65 
66 int main(){
67     File("dynamic");
68     work();
69     return 0;
70 }