BZOJ_3295_[Cqoi2011]动态逆序对_CDQ分治+树状数组
Description
对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删
除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数
Input
输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。
以下n行每行包含一个1到n之间的正整数，即初始排列。
以下m行每行一个正整数，依次为每次删除的元素。
N<=100000 M<=50000
Output
输出包含m行，依次为删除每个元素之前，逆序对的个数。
Sample Input
5 4
1
5
3
4
2
5
1
4
2
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)。
设每个值v删除的时间为t，位置为p。
对于那些没有删除的值，可以当成删除时间为n+1。
于是我们要统计删除一个数后逆序对数量变少了多少。
即统计删除时间大于tx，位置小于px，值大于vx的y的个数。
和删除时间大于tx，位置大于px，值小于vx的y的个数。
按删除时间从大到小排序，然后CDQ分治内部按位置排序，分别统计这两部分。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100050
typedef long long ll;
int b[N],pos[N],n,m,c[N],is[N];
ll ans[N],lstans;
struct A {
int t,p,v;
}a[N],t[N];
bool cmp(const A &x,const A &y) {
return x.t>y.t;
}
void fix(int x,int v) {for(;x<=n;x+=x&(-x)) c[x]+=v;}
ll inq(int x) {ll re=0;for(;x;x-=x&(-x)) re+=c[x]; return re;}
void solve(int l,int r) {
if(l==r) return ;
int mid=(l+r)>>1;
solve(l,mid); solve(mid+1,r);
int i=l,j=l,k=mid+1;
while(j<=mid&&k<=r) {
if(a[j].p<a[k].p) fix(a[j].v,1),t[i++]=a[j++];
else ans[a[k].t]+=inq(n)-inq(a[k].v),t[i++]=a[k++];
}
while(j<=mid) fix(a[j].v,1),t[i++]=a[j++];
while(k<=r) ans[a[k].t]+=inq(n)-inq(a[k].v),t[i++]=a[k++];
for(i=l;i<=mid;i++) fix(a[i].v,-1); j=mid,k=r;
while(j>=l&&k>=mid+1) {
if(a[j].p>a[k].p) fix(a[j].v,1),j--;
else ans[a[k].t]+=inq(a[k].v-1),k--;
}
while(j>=l) fix(a[j].v,1),j--;
while(k>=mid+1) ans[a[k].t]+=inq(a[k].v-1),k--;
for(i=l;i<=mid;i++) fix(a[i].v,-1);
for(i=l;i<=r;i++) a[i]=t[i];
}
int main() {
scanf("%d%d",&n,&m);
int i,j;
for(i=1;i<=n;i++) scanf("%d",&b[i]),lstans+=i-1-inq(b[i]),pos[b[i]]=i,fix(b[i],1);
memset(c,0,sizeof(c));
for(i=1;i<=m;i++) {
scanf("%d",&a[i].v); a[i].p=pos[a[i].v]; a[i].t=i; is[a[i].v]=1;
}
for(j=m,i=1;i<=n;i++) {
if(!is[i]) a[++j]=(A){n+1,pos[i],i};
}
sort(a+1,a+n+1,cmp);
solve(1,n);
//for(i=1;i<=m;i++) printf("%lld\n",ans[i]);
for(i=1;i<=m;i++) printf("%lld\n",lstans),lstans-=ans[i];
}