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

· · 题解

恩这道题典型的CDQ分治思想（洛谷上A的第100题,撒花~）

顺便以此讲解一下CDQ的板子吧

（其实哪里有什么板子，中间部分各种魔改）

CDq的思想是基于分治原理的

如果任何两个操作-询问对被且仅被执行了一次，那么这个操作-询问序列一定是准的

所以我们将一个操作重复做logN次

每次操作作用于不同的logN个询问段，这样完成了logN^2的复杂度

(有点像线段树的区间拆分法，但只是像)

下面来看这道动态逆序对

发现只要求出初始逆序对，然后每次求出降低的逆序对即可

对于每一个被删的元素，消失的逆序对等于

在它前面，权值比他大，且删去时间比他晚的点个数+

在它后面，权值比他小，且删去时间比他晚的点个数

那么每一个点上维护三个属性，位置，权值，删去时间

先静态排序，削去一维

就变成了我们熟悉的双统计问题

限制1：删去时间晚；限制2：权值大于（或小于关系）

先摁死一维，比如把权值排个序

那么只剩下删去时间了

由于还要保证CDQ要求的相对位序，所以我们的排序都是在内部进行

（也就是你CDQ分的区间(l,r)）这样对于(l,mid)和(mid,r)这两个区间来讲

(l,mid)的位置统统小于(mid，r)，但是(l,mid)和(mid,r)内部的位置关系已经不确定了，因为你对这两个区间内部按的权值排序）

这样的话其实是对左区间的每一个元素都统计一下右区间有多少个符合要求的点

再对右区间的每一个元素都统计一下左区间有多少个符合要求的点

对于这个，我们可以用树状数组来统计，因为限制已经被削成一维的了

具体来讲，保证对于左边的一个点i，权值比他大的右边点全被加了进去

每次加一个右边点，它的删去时间那个位置就+1

然后统计一个（i的删除时间，m+1）就行了

右边点的计算同理，记得开long long

上代码~

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    int n;int m;
    struct treearray//4行树状数组
    {
        int ta[200010];
        inline void ub(int& x){x+=x&(-x);}inline void db(int& x){x-=x&(-x);}
        inline void c(int x,int t){for(;x<=n+1;ub(x))ta[x]+=t;}
        inline int sum(int x){int r=0;for(;x>0;db(x))r+=ta[x];return r;}
    }ta;
    struct data{int val;int del;int ans;}a[100010];int rv[100010];ll res;//点
    bool cmp1(const data& a,const data& b){return a.val<b.val;}
    bool cmp2(const data& a,const data& b){return a.del<b.del;}
    void solve(int l,int r)//CDQ统计
    {
        if(r-l==1){return;}int mid=(l+r)/2;
        solve(l,mid);solve(mid,r);//先处理好左边和右边
        int i=l+1;int j=mid+1;
        while(i<=mid)
        {
            while(a[i].val>a[j].val&&j<=r){ta.c(a[j].del,1);j++;}//保证左边大于右边
            a[i].ans+=ta.sum(m+1)-ta.sum(a[i].del);i++;//统计
        }i=l+1;j=mid+1;//回撤操作
        while(i<=mid){while(a[i].val>a[j].val&&j<=r){ta.c(a[j].del,-1);j++;}i++;}
        i=mid;j=r;
        while(j>mid)
        {
            while(a[j].val<a[i].val&&i>l){ta.c(a[i].del,1);i--;}//保证右边大于左边
            a[j].ans+=ta.sum(m+1)-ta.sum(a[j].del);j--;//统计
        }i=mid;j=r;//回撤操作
        while(j>mid){while(a[j].val<a[i].val&&i>l){ta.c(a[i].del,-1);i--;}j--;}
        sort(a+l+1,a+r+1,cmp1);return;//排好序，为上一层的CDQ做准备
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){scanf("%d",&a[i].val);rv[a[i].val]=i;}
        for(int i=1;i<=m;i++){int p;scanf("%d",&p);a[rv[p]].del=i;}
        for(int i=1;i<=n;i++){if(a[i].del==0)a[i].del=m+1;}//计算初始逆序
        for(int i=1;i<=n;i++){res+=ta.sum(n+1)-ta.sum(a[i].val);ta.c(a[i].val,1);}
        for(int i=1;i<=n;i++){ta.c(a[i].val,-1);}solve(0,n);sort(a+1,a+n+1,cmp2);
        for(int i=1;i<=m;i++){printf("%lld\n",res);res-=a[i].ans;}return 0;//拜拜程序~
    }