BZOJ3295: [Cqoi2011]动态逆序对（树状数组套主席树）

3295: [Cqoi2011]动态逆序对

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 7465 Solved: 2662
[Submit][Status][Discuss]

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)。

思路：先求出总的逆序对数，然后对于每次的删数，我就减去这个位置前面比它大的个数以及后面比它小的个数。

注意这里删去的是元素，不是给的下标，由于没看题，我WA了好多次。

当然，也不难想到用CDQ分治去做。我个人习惯写主席树。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

struct in{

    int l,r,sum;

}s[maxn*];

int a[maxn],rt[maxn],N,M,cnt; ll ans;

void add(int &Now,int L,int R,int pos,int v)

{

    if(!Now) Now=++cnt; s[Now].sum+=v;

    if(L==R) return ;int Mid=(L+R)>>;

    if(pos<=Mid) add(s[Now].l,L,Mid,pos,v);

    else add(s[Now].r,Mid+,R,pos,v);

}

void Add(int x,int pos,int v)

{

    while(x<=N){

        add(rt[x],,N,pos,v);

        x+=(-x)&x;

    }

}

int query(int Now,int L,int R,int l,int r)

{

    if(!Now) return ;

    if(l<=L&&r>=R) return s[Now].sum;

    int Mid=(L+R)>>,res=;

    if(l<=Mid) res+=query(s[Now].l,L,Mid,l,r);

    if(r>Mid) res+=query(s[Now].r,Mid+,R,l,r);

    return res;

}

int Query(int x,int L,int R)

{

    if(L>R) return ;

    int res=; while(x){

        res+=query(rt[x],,N,L,R);

        x-=(-x)&x;

    } return res;

}

int num[maxn],p[maxn];

void ADD(int x,int v){ while(x<=N){ num[x]+=v; x+=(-x)&x; }}

int Sum(int x){ int res=; while(x){ res+=num[x]; x-=(-x)&x;} return res;}

int main()

{

    scanf("%d%d",&N,&M);

    rep(i,,N){

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

        ans+=i--Sum(a[i]-);

        Add(i,a[i],); ADD(a[i],);

    }

    rep(i,,M){

        int pos; scanf("%d",&pos); pos=p[pos];

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

        ans-=Query(pos-,a[pos]+,N);

        ans-=(Sum(a[pos]-)-Query(pos-,,a[pos]-));

        Add(pos,a[pos],-);

        ADD(a[pos],-);

    }

    return ;

}

秒客网