BZOJ 3295: [Cqoi2011]动态逆序对

时间：2022-09-11 15:24:08

3295: [Cqoi2011]动态逆序对

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 3865  Solved: 1298
[Submit][Status][Discuss]

Description

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

Input

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

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

HINT

N<=100000 M<=50000

Source

树状数组套线段树

删除某个数，只要统计它之前还存在的比它大的数的个数，和之后还存在的比它小的数的个数

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

#define R register

using namespace std;

int read(){

    R int x=;bool f=;

    R char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=;ch=getchar();}

    while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

    return f?x:-x;

}

const int N=1e5+;

const int M=N*;

int A[],B[];

int n,m,sz,num[N],pos[N],a1[N],a2[N],root[N],c[N];

int ls[M],rs[M],sum[M];

ll ans;

inline int lowbit(int x){

    return x&-x;

}

void updata(int p,int v){

    for(int i=p;i<=n;i+=lowbit(i)) c[i]+=v;

}

int query(int p){

    int res=;

    for(int i=p;i;i-=lowbit(i)) res+=c[i];

    return res;

}

void update(int &y,int l,int r,int x){

    if(!y) y=++sz;

    sum[y]++;

    if(l==r)return;

    int mid=(l+r)>>;

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

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

}

int askmore(int x,int y,int num){

    A[]=B[]=;int tmp=;x--;

    for(int i=x;i;i-=lowbit(i)) A[++A[]]=root[i];

    for(int i=y;i;i-=lowbit(i)) B[++B[]]=root[i];

    int l=,r=n;

    while(l!=r){

        int mid=l+r>>;

        if(num<=mid){

            for(int i=;i<=A[];i++) tmp-=sum[rs[A[i]]];

            for(int i=;i<=B[];i++) tmp+=sum[rs[B[i]]];

            for(int i=;i<=A[];i++) A[i]=ls[A[i]];

            for(int i=;i<=B[];i++) B[i]=ls[B[i]];

            r=mid;

        }

        else{

            for(int i=;i<=A[];i++) A[i]=rs[A[i]];

            for(int i=;i<=B[];i++) B[i]=rs[B[i]];

            l=mid+;

        }

    }

    return tmp;

}

int askless(int x,int y,int num){

    A[]=B[]=;int tmp=;x--;

    for(int i=x;i;i-=lowbit(i)) A[++A[]]=root[i];

    for(int i=y;i;i-=lowbit(i)) B[++B[]]=root[i];

    int l=,r=n;

    while(l!=r){

        int mid=l+r>>;

        if(num>mid){

            for(int i=;i<=A[];i++) tmp-=sum[ls[A[i]]];

            for(int i=;i<=B[];i++) tmp+=sum[ls[B[i]]];

            for(int i=;i<=A[];i++) A[i]=rs[A[i]];

            for(int i=;i<=B[];i++) B[i]=rs[B[i]];

            l=mid+;

        }

        else{

            for(int i=;i<=A[];i++) A[i]=ls[A[i]];

            for(int i=;i<=B[];i++) B[i]=ls[B[i]];

            r=mid;

        }

    }

    return tmp;

}

int main(){

    n=read();m=read();

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

        num[i]=read();pos[num[i]]=i;

        a1[i]=query(n)-query(num[i]);

        ans+=a1[i];

        updata(num[i],);

    }

    memset(c,,sizeof c);

    for(int i=n;i;i--){

        a2[i]=query(num[i]-);

        updata(num[i],);

    }

    for(int i=,x;i<=m;i++){

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

        x=read();x=pos[x];

        ans-=(a1[x]+a2[x]-askmore(,x-,num[x])-askless(x+,n,num[x]));

        for(int j=x;j<=n;j+=lowbit(j)) update(root[j],,n,num[x]);

    }

    return ;

}

相关文章