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，那么这就是一个逆序对。于是这题就变成裸的三维偏序了。

//It is made by wfj_2048~ #include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <vector> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define inf (1<<30) #define il inline #define RG register #define ll long long #define lb(x) (x & -x) #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std; struct node{ int x,y,t; }q[100010],qu[100010]; ll c[100010],ans[100010],Ans; int match[100010],n,m; il int gi(){ RG int x=0,q=0; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar(); if (ch=='-') q=1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q ? -x : x; } 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); } il void add(RG int x,RG int v){ for (RG int i=x;i<=n;i+=lb(i)) c[i]+=(ll)v; return; } il ll query(RG int x){ RG ll res=0; for (RG int i=x;i;i-=lb(i)) res+=c[i]; return res; } il void solve(RG int l,RG int r){ if (l>=r) return; RG int mid=(l+r)>>1,t1=l-1,t2=mid; 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); for (RG int i=l;i<=r;++i) if (q[i].t<=mid) add(q[i].y,-1); 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); for (RG int i=r;i>=l;--i) if (q[i].t<=mid) add(q[i].y,-1); for (RG int i=l;i<=r;++i) if (q[i].t<=mid) qu[++t1]=q[i]; else qu[++t2]=q[i]; for (RG int i=l;i<=r;++i) q[i]=qu[i]; solve(l,mid),solve(mid+1,r); return; } il void work(){ 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; 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--; sort(q+1,q+n+1,cmp); solve(1,n); for (RG int i=1;i<=n;++i) Ans+=ans[i]; for (RG int i=n;i>n-m;--i){ printf("%lld\n",Ans); Ans-=ans[i]; } return; } int main(){ File("dynamic"); work(); return 0; }