BZOJ3295：[CQOI2011]动态逆序对——题解

http://www.lydsy.com/JudgeOnline/problem.php?id=3295

Description

对于序列A，它的逆序对数定义为满足i<j，且A_i>A_j的数对(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

——————————————————————————————

这题不开longlong成功见祖宗……

乍一看我们想不到CDQ，但是显然删除操作不好整，我们将删除变成插入，插入的时间点为t，插入的位置为p，插入的值为n。

则三元组(t,p,n)它的逆序对需要满足t0<t,p0<p,n0>n或者t0<t,p0>p,n0<n。

这不就成三维偏序了吗？解完之后求一遍前缀和即是答案。

#include<cstdio>

#include<queue>

#include<cctype>

#include<cstring>

#include<vector>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=;

inline int read(){

    int X=,w=; char ch=;

    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}

    while(isdigit(ch)) X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct del{

    int t;

    int p;

    int n;

}q[N],tmp[N];

ll m,n,ans[N],pos[N],tree[N];

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

void add(int x,int y){//将a[x]+y

    for(int i=x;i<=n;i+=lowbit(i))tree[i]+=y;

    return;

}

ll query(int x){//1-x区间和

    ll res=;

    for(int i=x;i>;i-=lowbit(i))res+=tree[i];

    return res;

}

void cdq(int l,int r){

    if(l>=r)return;

    int mid=(l+r)>>;

    cdq(l,mid);cdq(mid+,r);

    for(int i=l,j=l,p=mid+;i<=r;i++){

    if(j<=mid&&(p>r||q[j].n>q[p].n))tmp[i]=q[j++];

    else tmp[i]=q[p++];

    }

    for(int i=l;i<=r;i++){

    q[i]=tmp[i];

    if(q[i].t<=mid)add(q[i].p,);

    else ans[q[i].t]+=query(q[i].p);

    }

    for(int i=l;i<=r;i++)if(q[i].t<=mid)add(q[i].p,-);

    for(int i=r;i>=l;i--){

    if(q[i].t<=mid)add(q[i].p,);

    else ans[q[i].t]+=query(n)-query(q[i].p);

    }

    for(int i=l;i<=r;i++)if(q[i].t<=mid)add(q[i].p,-);

    return;

}

bool vis[N];

int main(){

    n=read();

    m=read();

    for(int i=;i<=n;i++)pos[read()]=i;

    for(int i=n;i>=n-m+;i--){

    q[i].t=i;

    q[i].n=read();

    q[i].p=pos[q[i].n];

    vis[q[i].n]=;

    }

    int cnt=n-m;

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

    if(!vis[i]){

        q[cnt].t=cnt;

        q[cnt].n=i;

        q[cnt--].p=pos[i];

    }

    }

    cdq(,n);

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

    for(int i=n;i>=n-m+;i--)printf("%lld\n",ans[i]);

    return ;

}

秒客网