[BZOJ3295/Luogu3157][CQOI2011]动态逆序对(CDQ分治)

发布于 2018-04-08  58 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3295/Luogu3157][CQOI2011]动态逆序对(CDQ分治)

Description

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

Tag

CDQ分治

解决思路

给每一个数赋上一个时间戳Tim[i],第一个删除的数时间戳最大,然后依次递减,这样转化为一个偏序问题。
删除一个数i,减去的逆序对个数有两种,一种是对于j< i且A[i]< A[j]并且Tim[j]< Tim[i],另一种是对于j>i,A[i] >A[j]并且Tim[j]< Tim[i],这个可以用CDQ分治解决。
在外面对tim排序,然后分治,保证左边的tim一定小于右边。先递归左右两边,回来后保证左右分别按照在原数列中的位置(下面称作编号)排序。然后对右边的每一个数计算两次,第一次计算左边的编号小于它而值大于它的,第二次计算左边编号大于它而值小于它的,这个可以分别用树状数组做。
最后返回上一层的时候,把左右区间按照编号归并排序

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define lowbit(x) ((x)&(-(x)))

const int maxN=101000;
const int inf=2147483647;

class Data
{
public:
    ll tim,id,key;
    ll ans;
};

int n,m;
int Pos[maxN];
Data Q[maxN],Q2[maxN];
ll BIT[maxN],histcnt=0,Hist[maxN];
ll Ans[maxN];

bool operator < (Data A,Data B);
void Add(int pos,ll key);
ll Sum(int pos);
ll Query(int l,int r);
void Divide(int l,int r);

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        cin>>Q[i].key;Pos[Q[i].key]=i;
        Q[i].id=i;Q[i].tim=0;
    }
    int cnt=n;
    for (int i=m;i>=1;i--)
    {
        int pos;cin>>pos;pos=Pos[pos];
        Q[pos].tim=cnt--;
    }
    for (int i=1;i<=n;i++) if (Q[i].tim==0) Q[i].tim=cnt--;
    sort(&Q[1],&Q[n+1]);
    Divide(1,n);
    for (int i=1;i<=n;i++) Ans[Q[i].tim]=Q[i].ans;
    for (int i=1;i<=n;i++) Ans[i]+=Ans[i-1];
    for (int i=1,j=n;i<=m;i++,j--) cout<<Ans[j]<<endl;
    return 0;
}

bool operator < (Data A,Data B)
{
    if (A.tim!=B.tim) return A.tim<B.tim;
    return A.id<B.id;
}

void Add(int pos,ll key)
{
    while (pos<=n)
    {
        if (Hist[pos]!=histcnt) BIT[pos]=key,Hist[pos]=histcnt;
        else BIT[pos]+=key;
        pos+=lowbit(pos);
    }
    return;
}

ll Sum(int pos)
{
    int ret=0;
    while (pos)
    {
        if (Hist[pos]==histcnt) ret+=BIT[pos];
        pos-=lowbit(pos);
    }
    return ret;
}

ll Query(int l,int r)
{
    if (l>r) return 0;
    return Sum(r)-Sum(l-1);
}

void Divide(int l,int r)
{
    if (l==r) return;
    int mid=(l+r)>>1;
    Divide(l,mid);Divide(mid+1,r);//递归处理左右区间
    int p1=l,p2=mid+1;
    histcnt++;
    for (int i=l;i<=r;i++)//先算左边编号小于而值大于的
        if ((p1<=mid)&&((p2>r)||(Q[p1].id<Q[p2].id))){
            Add(Q[p1].key,1);p1++;
        }
        else{
            Q[p2].ans+=Query(Q[p2].key,n);p2++;
        }
    p1=mid,p2=r;histcnt++;
    for (int i=r;i>=l;i--)//再算左边编号大于而值小于的
        if ((p1>=l)&&((p2<mid+1)||(Q[p1].id>Q[p2].id))){
            Add(Q[p1].key,1);p1--;
        }
        else {
            Q[p2].ans+=Query(1,Q[p2].key);p2--;
        }

    p1=l;p2=mid+1;
    for (int i=l;i<=r;i++)
        if ((p1<=mid)&&((p2>r)||(Q[p1].id<Q[p2].id))) Q2[i]=Q[p1++];
        else Q2[i]=Q[p2++];
    for (int i=l;i<=r;i++) Q[i]=Q2[i];
    return;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3295/Luogu3157][CQOI2011]动态逆序对(CDQ分治)


HNCJ OIer 一枚