题解 P3157 【[CQOI2011]动态逆序对】

· · 题解

大佬们太强了，题解超级优质可惜本巨弱根本看不懂啊。

我来讲一下一个刚学会主席树的人怎么看遍所有看不懂的题解然后写出来这个题吧。

首先，题解上好多CDQ分治，这个东西我不讲，我来讲一下主席树的做法。

普通的树状数组求逆序对大家肯定会吧。

那么删除第一个前的逆序对自然能求出来，此时我们考虑删除第一个元素，减少的逆序对个数就是在它前面的比他大的和在它后面比它小的，于是我们开两个数组来存:

as1[i]表示的就是在i前面而且大于i位置上的元素的元素的个数

as2[i]表示的就是在i后面而且小于i位置上的元素的元素的个数

as1[i]就可以在读入的时候直接处理一下

BIT就是简单的前缀和树状数组.

for(int i=1;i<=n;++i){
    scanf("%d",&endq[i]);
    as1[i]=BIT.queryb(n)-BIT.queryb(endq[i]);
    ans+=as1[i];
    BIT.addb(endq[i],1);
}

as2[i]可以反向添加然后处理出来

for(int i=n;i>=1;--i){
    as2[i]=BIT.queryb(endq[i]-1);
    BIT.addb(endq[i],1);
}

但是又有一个问题了,我已经删了的还是被计算在内了,怎么办?

我减去它与已经删了的构成的逆序对的个数不就好了吗?

那么我们就做成了什么?

每一次在已经删除的元素里面找[l,r]里面小于某个数的元素的个数,很容易想到主席树来做.

既然是维护前缀和的主席树,那是不是我每修改一个都要向后一直修改?

显然复杂度爆表.

前缀和我们还有一种求法,那就是用树状数组,那我能不能用树状数组来代替这种一般前缀和?

显然是可以的,我们每次修改的时候,按照树状数组那样,一直向上修改,求前缀和也像树状数组那样不断加和就好了.

至此,一个树状数组套主席树解决动态逆序对就完结了.

有什么不懂的欢迎提问原作者我

全代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,endq[100010],pls[100010];//pls[i]记录的是i的位置
long long ans=0;
struct Zxt{
    #define Nmax 6000001
    #define mid ((ln+rn)>>1)
    #define out_it (ln>rd || rn<ld)
    #define in_it (ln>=ld && rn<=rd)
    long long sum[Nmax],tailn;
    int ls[Nmax],rs[Nmax],root[Nmax];
    void add(int &num,int ln,int rn,int pos){
        if(!num){
            num=++tailn;
        }
        ++sum[num];
        if(ln==rn)
            return;
        if(pos<=mid)
            add(ls[num],ln,mid,pos);
        else
            add(rs[num],mid+1,rn,pos);
    }
    long long query(int num1,int ln,int rn,int ld,int rd){//last jian old
        if(out_it)
            return 0;
        if(in_it)
            return sum[num1];
        return query(ls[num1],ln,mid,ld,rd)+
            query(rs[num1],mid+1,rn,ld,rd);
    }
    long long find(int pos1,int pos2,int lowest,int uppest){
        if(lowest>uppest)
            return 0;
        long long asp=0;
        for(;pos2;pos2-=(pos2)&(-pos2))
            asp+=query(root[pos2],1,n,lowest,uppest);
        for(;pos1;pos1-=(pos1)&(-pos1))
            asp-=query(root[pos1],1,n,lowest,uppest);
        return asp;
    }
}Zxt;
struct BITs{
    long long val[100001];
    int lowbit(int x){
        return x&(-x);
    }
    void addb(int pos,int num){
        for(;pos<=100000;pos+=lowbit(pos))
            val[pos]+=num;
    }
    long long queryb(int pos){
        long long ans=0;
        for(;pos;pos-=lowbit(pos))
            ans+=val[pos];
        return ans;
    }
}BIT;
long long as1[100001],as2[100001],p1,p2;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&endq[i]);
        pls[endq[i]]=i;
        as1[i]=BIT.queryb(n)-BIT.queryb(endq[i]);
        ans+=as1[i];
        BIT.addb(endq[i],1);
    }
    for(int i=1;i<=100000;++i)  BIT.val[i]=0;//防止第二遍统计出问题 
    for(int i=n;i>=1;--i){
        as2[i]=BIT.queryb(endq[i]-1);
        BIT.addb(endq[i],1);
    }//原来的BIT已经用完了，没用了，剩下的就是树状数组思想了 
    for(int i=1;i<=m;++i){
        printf("%lld\n",ans);//注意是先输出,因为是删除前.
        scanf("%lld",&p1);
        p2=pls[p1];
        ans-=(as1[p2]+as2[p2])-(Zxt.find(0,p2,p1+1,n)+Zxt.find(p2,n,1,p1-1));
        for(int qqq=p2;qqq<=n;qqq+=qqq&(-qqq))
            Zxt.add(Zxt.root[qqq],1,n,p1);
    }
    return 0;
}