CQOI2011 动态逆序对

题目:

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

思路:

  • 树状数组套线段树、分块套线段树:
      如果动态的解决这个问题,可以先预处理出在不删除前,整个序列的逆序对数。每次删去后,减少的对数就是的个数和的个数,这个两维的偏序就可以通过数据结构嵌套处理了
  • CDQ分治:
      反过来考虑一个个数字被加入,计算出每个数字被加入时增加的逆序对数(也是被删去时减少的值)。那么这时计算逆序对数时就多了一个维度,要满足被加入的时间小于当前的数字。时间这一维用树状数组维护,其余的就和分治求逆序对类似。

代码:

  • 树状数组套线段树:
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define DOR(i,a,b) for(int i=(a),i##END=(b);i>=i##END;i--)
#define ll long long
#define MN 100005
#define NlogNlogN (100005*17*17)
#define low(x) (-(x)&x)
using namespace std;
struct Node{int Ls,Rs,sum;};
Node nod[NlogNlogN];
int tot;
struct Seg{
    int rt;
    Seg(){rt=0;}
    #define mid (L+R>>1)
    #define ls nod[o].Ls
    #define rs nod[o].Rs
    void Upd(int &o,int w,int d,int L,int R){
        if(!o)o=++tot;
        nod[o].sum+=d;
        if(L==R)return;
        if(w<=mid)Upd(ls,w,d,L,mid);
        else Upd(rs,w,d,mid+1,R);
    }
    void upd(int w,int d){Upd(rt,w,d,1,MN-5);}
    int Qry(int o,int l,int r,int L,int R){
        if(!o)return 0;
        if(l==L&&r==R)return nod[o].sum;
        if(r<=mid)return Qry(ls,l,r,L,mid);
        else if(l>mid)return Qry(rs,l,r,mid+1,R);
        else return Qry(ls,l,mid,L,mid)+Qry(rs,mid+1,r,mid+1,R);
    }
    int qry(int l,int r){return Qry(rt,l,r,1,MN-5);}
};
template<int N> struct BIT_Seg{
    Seg s[N];int a;
    void upd(int x,int y,int d){for(;x<N;x+=low(x))s[x].upd(y,d);}
    int qry_pre(int x,int l,int r){for(a=0;x;x-=low(x))a+=s[x].qry(l,r);return a;}
    int qry_nxt(int x,int l,int r){return qry_pre(N-1,l,r)-qry_pre(x-1,l,r);}
};
template<int N> struct BIT{
    int c[N],a;
    void upd(int x,int d){for(;x<N;x+=low(x))c[x]+=d;}
    int qry_pre(int x){for(a=0;x;x-=low(x))a+=c[x];return a;}
    int qry_nxt(int x){return qry_pre(N-1)-qry_pre(x);}
};
int n;
int a[MN],id[MN];
ll calc(){
    static BIT<MN> tmp;
    ll ans=0;
    DOR(i,n,1){
        ans+=tmp.qry_pre(a[i]);
        tmp.upd(a[i],1);
    }
    return ans;
}
BIT_Seg<MN> bs;
int main(){
    int m,x;
    scanf("%d%d",&n,&m);
    FOR(i,1,n)scanf("%d",a+i),id[a[i]]=i;
    FOR(i,1,n)bs.upd(i,a[i],1);
    ll ans=calc();
    while(m--){
        scanf("%d",&x);x=id[x];
        printf("%lld\n",ans);
        bs.upd(x,a[x],-1);
        ans-=bs.qry_pre(x,a[x],n);
        ans-=bs.qry_nxt(x,1,a[x]);
    }
    return 0;
}
  • 分块套树状数组:
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define DOR(i,a,b) for(int i=(a),i##END=(b);i>=i##END;i--)
#define ll long long
#define MN 100005
#define Log(a,b) (log(a)/log(b))
using namespace std;
template<int N> struct BIT{
    int c[N],a;
    #define low(x) (-(x)&(x))
    void upd(int x,int d){for(;x<N;x+=low(x))c[x]+=d;}
    int qry_pre(int x){for(a=0;x;x-=low(x))a+=c[x];return a;}
    int qry_nxt(int x){return qry_pre(N-1)-qry_pre(x);}
};
BIT<MN> bit[90],tmp;
int a[MN],n;
ll calc(){
    ll ans=0;
    DOR(i,n,1){
        ans+=tmp.qry_pre(a[i]);
        tmp.upd(a[i],1);
    }
    return ans;
}
int id[MN];
void init(){
    int bs;
    bs=sqrt(n*Log(n,2))+1;
    FOR(i,1,n)id[i]=i/bs+1;
    FOR(i,1,n)bit[id[i]].upd(a[i],1);
}
bool del[MN];
int Del(int x){
    int ans=0;
    del[x]=1;bit[id[x]].upd(a[x],-1);
    for(int i=x-1;id[i]==id[x];i--)ans+=(!del[i]&&a[i]>a[x]);
    for(int i=x+1;id[i]==id[x];i++)ans+=(!del[i]&&a[i]<a[x]);
    for(int k=id[x]-1;k>=id[1];k--)ans+=bit[k].qry_nxt(a[x]);
    for(int k=id[x]+1;k<=id[n];k++)ans+=bit[k].qry_pre(a[x]);
    return ans;
}
int No[MN];
int main(){
    int m,x;
    scanf("%d%d",&n,&m);
    FOR(i,1,n)scanf("%d",a+i),No[a[i]]=i;
    ll ans=calc();
    init();
    while(m--){
        scanf("%d",&x);
        printf("%lld\n",ans);
        ans-=Del(No[x]);
    }
    return 0;
}
  • CDQ分治:
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define DOR(i,a,b) for(int i=(a),i##END=(b);i>=i##END;i--)
#define ll long long
#define MN 100005
using namespace std;
template<int N> struct BIT{
    int s[N],a;
    #define low(x) (-(x)&(x))
    void upd(int x,int d){for(;x<N;x+=low(x))s[x]+=d;}
    int qry(int x){for(a=0;x;x-=low(x))a+=s[x];return a;}
    int sum(int l,int r){return qry(r)-qry(l-1);}
};
BIT<MN> b1,b2;
int add[MN],a[MN],t[MN],m;
ll ans[MN],Ans;
void CDQ(int l,int r){
    if(l==r)return;
    int mid=l+r>>1;
    CDQ(l,mid);CDQ(mid+1,r);
    FOR(k,l,mid)b1.upd(add[a[k]],1);
    int i=l,j=mid+1,tot=l;
    while(i<=mid&&j<=r){
        if(a[i]<a[j]){
            ans[m-add[a[i]]+2]+=b2.qry(add[a[i]]);
            b1.upd(add[a[i]],-1);
            t[tot++]=a[i++];
        }
        else {
            Ans+=mid-i+1;
            ans[m-add[a[j]]+2]+=b1.qry(add[a[j]]);
            b2.upd(add[a[j]],1);
            t[tot++]=a[j++];
        }
    }
    while(i<=mid){
        ans[m-add[a[i]]+2]+=b2.qry(add[a[i]]);
        b1.upd(add[a[i]],-1);
        t[tot++]=a[i++];
    }
    while(j<=r){
        Ans+=mid-i+1;
        ans[m-add[a[j]]+2]+=b1.qry(add[a[j]]);
        b2.upd(add[a[j]],1);
        t[tot++]=a[j++];
    }
    FOR(k,mid+1,r)b2.upd(add[a[k]],-1);
    FOR(k,l,r)a[k]=t[k];
}
int main(){
    int n,x;
    scanf("%d%d",&n,&m);
    FOR(i,1,n)scanf("%d",a+i);
    FOR(i,1,n)add[i]=1;
    FOR(i,1,m){
        scanf("%d",&x);
        add[x]=m-i+2;
    }
    CDQ(1,n);
    FOR(i,1,m){
        printf("%lld\n",Ans);
        Ans-=ans[i];
    }
    return 0;
}