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

P3157 [CQOI2011]动态逆序对

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

说明

(Nle 100000,Mle 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
",ans[i]);
    return 0;
}

2018.11.27