COGS 1715. [CQOI2011]动态逆序对

★★★ 输入文件：inverse.in 输出文件：inverse.out 简单对比
时间限制：2 s 内存限制：128 MB

【题目描述】

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

【输入格式】

输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。

【输出格式】

输出包含m行，依次为删除每个元素之前，逆序对的个数。

【样例输入】

【样例输出】

5

  2

  2

  1

  样例解释

  (1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

【提示】

N<=100000 M<=50000

【来源】

【题目来源】

耒阳大世界（衡阳八中） OJ 3295

树状数组+主席树

根cdq分治的速度差远了

屠龙宝刀点击就送

#include <algorithm>

#include <cstdio>

#define N 100005

typedef long long LL;

int n,m,a[N],pos[N],size,rt[N],ls[N*],rs[N*],sum[N*],tot;

inline int lowbit(int x) {return x&(-x);}

void update(int l,int r,int &x,int t,int v)

{

    if(!x) x=++tot;

    sum[x]+=v;

    if(l==r) return;

    int mid=(l+r)>>;

    if(t<=mid) update(l,mid,ls[x],t,v);

    else update(mid+,r,rs[x],t,v);

}

void modify(int x,int y,int v)

{

    for(;x<=n;x+=lowbit(x))

    update(,n,rt[x],y,v);

}

LL query(int l,int r,int x,int L,int R)

{

    if(!x) return ;

    if(L<=l&&r<=R) return sum[x];

    int mid=(l+r)>>;LL ret=;

    if(L<=mid) ret+=query(l,mid,ls[x],L,R);

    if(R>mid) ret+=query(mid+,r,rs[x],L,R);

    return ret;

}

LL ask(int l,int r,int L,int R)

{

    LL ret=;

    for(int i=l-;i;i-=lowbit(i)) ret-=query(,n,rt[i],L,R);

    for(int i=r;i;i-=lowbit(i)) ret+=query(,n,rt[i],L,R);

    return ret;

}

int main()

{

    freopen("inverse.in","r",stdin);

    freopen("inverse.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;++i)

    {

        scanf("%d",&a[i]);

        pos[a[i]]=i;

        modify(i,a[i],);

    }

    LL ans=;

    for(int i=;i<=n;++i) ans+=ask(,i-,a[i]+,n)+ask(i+,n,,a[i]-);

    ans>>=;

    for(int v;m--;)

    {

        printf("%lld\n",ans);

        scanf("%d",&v);

        v=pos[v];

        ans-=ask(,v-,a[v]+,n)+ask(v+,n,,a[v]-);

        modify(v,a[v],-);

    }

    return ;

}

巴特西