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 4
  1
  5
  3
  4
  2
  5
  1
  4
  2
  

【样例输出】

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*100],rs[N*100],sum[N*100],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)>>1;
    if(t<=mid) update(l,mid,ls[x],t,v);
    else update(mid+1,r,rs[x],t,v);
}
void modify(int x,int y,int v)
{
    for(;x<=n;x+=lowbit(x)) 
    update(1,n,rt[x],y,v);
}
LL query(int l,int r,int x,int L,int R)
{
    if(!x) return 0;
    if(L<=l&&r<=R) return sum[x];
    int mid=(l+r)>>1;LL ret=0;
    if(L<=mid) ret+=query(l,mid,ls[x],L,R);
    if(R>mid) ret+=query(mid+1,r,rs[x],L,R);
    return ret;
}
LL ask(int l,int r,int L,int R)
{
    LL ret=0;
    for(int i=l-1;i;i-=lowbit(i)) ret-=query(1,n,rt[i],L,R);
    for(int i=r;i;i-=lowbit(i)) ret+=query(1,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=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        pos[a[i]]=i;
        modify(i,a[i],1);
    }
    LL ans=0;
    for(int i=1;i<=n;++i) ans+=ask(1,i-1,a[i]+1,n)+ask(i+1,n,1,a[i]-1);
    ans>>=1;
    for(int v;m--;)
    {
        printf("%lld
",ans);
        scanf("%d",&v);
        v=pos[v];
        ans-=ask(1,v-1,a[v]+1,n)+ask(v+1,n,1,a[v]-1);
        modify(v,a[v],-1);
    }
    return 0;
}