洛谷 P3157 [CQOI2011]动态逆序对 解题报告

P3157 [CQOI2011]动态逆序对

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

说明

\(N\le 100000,M\le 50000\)

---

万年以前树套树怎么都是60pts，今天终于决定进行CDQ分治水过去。

每个元素安排三个属性为\(P_i,A_i,D_i\)分别代表在原序列的位置，元素值和被删时间。

然后我们统计一下\(P_i < P_j,A_i>A_j,D_i<D_j\)的个数。

然后我调了半个多小时...

终于弄明白\(P_i > P_j,A_i<A_j,D_i<D_j\)也要统计...

---

Code:

#include <cstdio>

#include <algorithm>

#define ll long long

const int N=1e5+10;

struct node{int a,b,p;}sq[N];

int n,m,s[N];

ll ans[N];

void add(int x,int d){while(x<=m)s[x]+=d,x+=x&-x;}

int ask(int x){int sum=0;while(x)sum+=s[x],x-=x&-x;return sum;}

bool cmp1(node n1,node n2){return n1.a>n2.a;}

bool cmp2(node n1,node n2){return n1.a<n2.a;}

void CDQ(int l,int r)

{

    if(l==r) return;

    int mid=l+r>>1;

    CDQ(l,mid),CDQ(mid+1,r);

    std::sort(sq+l,sq+r+1,cmp1);

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

    {

        if(sq[i].p<=mid) add(sq[i].b,1);

        else ans[sq[i].b]+=1ll*(ask(m)-ask(sq[i].b-1));

    }

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

    std::sort(sq+l,sq+r+1,cmp2);

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

    {

        if(sq[i].p>mid) add(sq[i].b,1);

        else ans[sq[i].b]+=1ll*(ask(m)-ask(sq[i].b-1));

    }

    for(int i=l;i<=r;i++) if(sq[i].p>mid) add(sq[i].b,-1);

}

int main()

{

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

    for(int a,i=1;i<=n;i++)

    {

        scanf("%d",&a);

        sq[a].a=i;

        sq[a].b=m;

        sq[a].p=a;

    }

    for(int a,i=1;i<=m;i++)

    {

        scanf("%d",&a);

        sq[a].b=i;

    }

    CDQ(1,n);

    ans[m]>>=1;

    for(int i=m-1;i;i--) ans[i]+=ans[i+1];

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

    return 0;

}

---

2018.11.27