【bzoj3295】[Cqoi2011]动态逆序对

2015.05.20 09:05 Wed | 31次阅读 | 旧日oi | 固定链接 | 源码

Description

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

Input

输入第一行包含两个整数nm,即初始元素的个数和删除的元素个数。以下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

题解

思路去膜拜popoqqq吧……给代码写个注释,也方便自己理解。。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 100005
int n,m;
long long ans;
int a[N],pos[N],cnt[N],f[N];
struct node{
    int x,y,id;
}q[N],nq[N];
int c[N],tim[N],tot;
bool cmp(const node &a,const node &b)
{
    return a.y<b.y;
}
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int flag)
{
    for(;x<=n&&x;x+=lowbit(x)*flag)
    {
        if(tim[x]!=tot) tim[x]=tot,c[x]=0;
        c[x]++;
    }
}
int getans(int x,int flag)
{
    int ret=0;
    for(;x&&x<=n;x+=lowbit(x)*flag) 
    if(tim[x]==tot) ret+=c[x];
    return ret;
}
void prework() 
{
    tot++;
    for(int i=1;i<=n;i++)
    {
        cnt[i]=getans(a[i],1);
        update(a[i],-1);
        ans+=cnt[i];
    } 
    tot++;
    for(int i=n;i;i--)
    {
        cnt[i]+=getans(a[i],-1);
        update(a[i],1);
    }
}
void cdq(int l,int r)
{
    if(l==r)
    {
        printf("%lld\n",ans);
        ans-=cnt[q[l].y];//减掉第l个删除的位置的cnt值 
        ans+=f[l];//加上第l个删除的f值,这里要和上面有所区分 
        return;
    }
    int mid=(l+r)>>1,i,j,l1,l2;
    l1=l,l2=mid+1;
    for(i=l;i<=r;i++)
    {
        if(q[i].id<=mid) nq[l1++]=q[i];
        else nq[l2++]=q[i];
    }
    memcpy(q+l,nq+l,sizeof(q[0])*(r-l+1));
    cdq(l,mid);
    tot++;j=l;
    for(i=mid+1;i<=r;i++)//正序统计q[j].y<q[i].y且q[j].x>q[i].x的个数) 
    {
        for(;j<=mid&&q[j].y<q[i].y;j++) update(q[j].x,-1);
        f[q[i].id]+=getans(q[i].x,1);
    }
    tot++;j=mid;
    for(i=r;i>mid;i--)//逆序统计q[j].y>q[i].y且q[j].x<q[i].x的个数) 
    {
        for(;j>=l&&q[j].y>q[i].y;j--) update(q[j].x,1);
        f[q[i].id]+=getans(q[i].x,-1);
    }
    cdq(mid+1,r);
    l1=l;l2=mid+1;//重新按y排序 
    for(i=l;i<=r;i++)
    {
        if((q[l1].y<q[l2].y||l2>r)&&l1<=mid) nq[i]=q[l1++];
        else nq[i]=q[l2++];
    }
    memcpy(q+l,nq+l,sizeof(q[0])*(r-l+1));
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),pos[a[i]]=i;
    prework();//预处理出总的逆序对数和每个位置的逆序对数。
    for(int i=1;i<=m;i++) scanf("%d",&q[i].x),q[i].y=pos[q[i].x],q[i].id=i;
    sort(q+1,q+m+1,cmp);//按在原串中的位置排序。 
    cdq(1,m);
}```