bzoj千题计划146：bzoj3295: [Cqoi2011]动态逆序对

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

正着删除看做倒着添加

对答案有贡献的数对满足以下3个条件：

出现时间：i<=j

权值大小关系：x[i]>x[j]

位置关系：pos[i]<pos[j]

或者是

出现时间：i<=j

权值大小关系：x[i]<x[j]

位置关系：pos[i]>pos[j]

所以是三维偏序问题

排序时间，CDQ分治解决权值大小关系，树状数组解决位置关系

CDQ分治后，只要不重新sort，内部区间仍满足第一维排序的大小顺序

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 100001

#define M 50001

#define lowbit(x) x&-x

int n;

struct node

{

    int pos,val,tim;

}e[N],a[N];

int dy[N],cut[N];

int c[N];

long long ans[N];

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

bool cmp(node p,node q)

{

    return p.tim<q.tim;

}

void add(int x,int y)

{

    while(x<=n)

    {

        c[x]+=y;

        x+=lowbit(x);

    }

}

int query(int x)

{

    int sum=;

    while(x)

    {

        sum+=c[x];

        x-=lowbit(x);

    }

    return sum;

}

void solve(int l,int r)

{

    if(l==r) return;

    int mid=l+r>>;

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

    {

        if(e[i].val<=mid) add(e[i].pos,);

        else ans[e[i].tim]+=query(n)-query(e[i].pos);

    }

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

        if(e[i].val<=mid) add(e[i].pos,-);

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

    {

        if(e[i].val>mid) add(e[i].pos,);

        else ans[e[i].tim]+=query(e[i].pos-);

    }

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

        if(e[i].val>mid) add(e[i].pos,-);

    int i=l,j=mid+;

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

    {

        if(e[k].val<=mid) a[i++]=e[k];

        else a[j++]=e[k];

    }

    for(int k=l;k<=r;++k) e[k]=a[k];

    solve(l,mid);

    solve(mid+,r);

}

int main()

{

    int m,x;

    read(n); read(m);

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

    {

        read(x);

        dy[x]=i;

        e[i].pos=i;

        e[i].val=x;

    }

    int ti=n;

    for(int i=;i<=m;++i)

    {

        read(x);

        e[dy[x]].tim=ti--;

    }

    sort(e+,e+n+,cmp);

    for(int i=;i<=n;++i) e[i].tim=i;

    solve(,n);

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

    for(int i=m;i;--i) cout<<ans[n-m+i]<<'\n';

}

3295: [Cqoi2011]动态逆序对

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 5946 Solved: 2064
[Submit][Status][Discuss]

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

样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

HINT

N<=100000 M<=50000

秒客网