3295: [Cqoi2011]动态逆序对

Time Limit: 10 Sec  Memory Limit: 128 MB

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

　　表示当时没看出来是CDQ，树套树倒是瞄出来了，只是不会写啊。

　　现在看来还是很显然的。

　　对于排列中的数，记它被删除的时间为t(未删除的设为m+1)，下标为X，大小为Y。

　　那么对于一个数i，来看在它前面被删除的数对它的答案的减小值为多少：

　　　　Σ(Tj<Ti && Xj<Xi && Yj>Yi) + Σ(Tj<Ti && Xj>Xi && Yj<Yi)

　　做两次CDQ就好了。这种没有重复的算起来真是爽啊。

　　做的时候没有草稿纸真TM不爽。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring> 
using namespace std;
 
const int N = 100010;
struct Data{
    int X,Y,T;long long len;
    bool operator <(const Data &t)const{
        return T<t.T;
    }
}rem[N],f[N],t[N];
int n,m,ban[N],bplace[N],A[N],T[N];
long long Ans,ans[N];
 
inline int gi()
{
    int x=0,res=1;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')res=-res;ch=getchar();}
    while(ch>'/' && ch<':')x=x*10+ch-48,ch=getchar();
    return x*res;
}
 
inline int lb(int k){return k&-k;}
 
inline void update(int x){for(;x<=n;x+=lb(x))T[x]++;}
 
inline int query(int x)
{
    int ans=0;
    for(;x;x-=lb(x))ans+=T[x];
    return ans;
}
 
inline void clean(int x){for(;x<=n;x+=lb(x))T[x]=0;}
 
inline void calc()
{
    memset(T,0,sizeof(T));Ans=0;
    for(int i=1;i<=n;++i){
        Ans+=(i-query(A[i])-1);
        update(A[i]);
    }
    memset(T,0,sizeof(T));
}
//在外面保证T有序，CDQ内保证X有序，统计Y值。 
//T：时间 X：位置 Y：权值
//CDQ calc Ti<Tj Xi<Xj Y[i]<Y[j]
inline void CDQ(int l,int r)
{
    if(l==r)return;int mid=(l+r)>>1;
    CDQ(l,mid);CDQ(mid+1,r);
    int x=l,y=mid+1,z=l;
    while(x<=mid && y<=r)
        if(f[x].X<f[y].X)update(f[x].Y),t[z++]=f[x++];
        else f[y].len+=query(f[y].Y),t[z++]=f[y++];
    while(x<=mid)t[z++]=f[x++];
    while(y<=r)f[y].len+=query(f[y].Y),t[z++]=f[y++];
    for(int i=l;i<=mid;++i)clean(f[i].Y);
    for(int i=l;i<=r;++i)f[i]=t[i];
}
 
int main()
{
    n=gi();m=gi();
    for(int i=1;i<=n;++i)
        A[i]=gi();
    for(int i=1;i<=m;++i)
        bplace[ban[i]=gi()]=i;
    for(int i=1;i<=n;++i){
        rem[i].T=bplace[A[i]];
        rem[i].X=i;
        rem[i].Y=A[i];
        if(!rem[i].T)rem[i].T=m+1;
    }
    sort(rem+1,rem+n+1);calc();
    for(int i=0;i<=m;++i)ans[i]=Ans;
    for(int i=1;i<=n;++i){
        f[i]=rem[i];
        f[i].Y=n-f[i].Y+1;
    }
    reverse(f+1,f+n+1);
    CDQ(1,n);sort(f+1,f+n+1);
    for(long long i=1,s=0;i<=n;++i){
        if(!f[i].T)continue;
        ans[f[i].T]-=s;s+=f[i].len;
    }
    for(int i=1;i<=n;++i){
        f[i]=rem[i];
        f[i].X=n-f[i].X+1;
    }
    reverse(f+1,f+n+1);
    CDQ(1,n);sort(f+1,f+n+1);
    for(long long i=1,s=0;i<=n;++i){
        if(!f[i].T)continue;
        ans[f[i].T]-=s;s+=f[i].len;
    }
    for(int i=1;i<=m;++i)
        printf("%lld\n",ans[i]);
    return 0;
}

　　

　　然后看见我在上古时期的分块？？！！

　　一脸懵逼。

　　瞪了好久发现 不是我写的。

　　大概思想就是分块，每块内排序。

　　然