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

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];

}

秒客网