欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[CQOI2011] 动态逆序对

程序员文章站 2022-04-13 15:33:24
使用树状数组求出初态下出f[i]、g[i]表示位置小(大)于i且值大(小)于a[i]的元素个数。显然ans|初=sum f[i]=sum g[i]。 考虑第一个删去的点x,删去以后,ans减少f[x]+g[x];再考虑第二个删去的点y,删去以后,ans减少f[y]+g[y]?不,f[y]、g[y]中 ......

使用树状数组求出初态下出f[i]、g[i]表示位置小(大)于i且值大(小)于a[i]的元素个数。显然ans|初=sum f[i]=sum g[i]。

考虑第一个删去的点x,删去以后,ans减少f[x]+g[x];再考虑第二个删去的点y,删去以后,ans减少f[y]+g[y]?不,f[y]、g[y]中可能算上了x(此题里是必然),这{x,y}这一对已经在上一次删除时减掉了,所以ans减少f[y]+g[y]的同时,还应加上已删除的点中与y构成的“逆序对数”。以后删除的点同理;

假设当前正在删除元素x,设元素到位置的映射为id[x],设f1、g1为在已删的点中与x相比位置小(大)于i且值更大(小)于的点的个数,那么ans应该为ans-f[x]-g[x]+f1+g1。现考虑如何快速计算f1、g1。以计算f1为例:

一:将删除的点放在新序列b的相应位置,每次扫描b[1~id[x]]中有多少满足b[i]>x的点。
二:不放将序列b扩充为矩阵b[i,j],b[i,j]表示位置为i,值为j的元素是否已经被删除。每次n^2求矩阵b[1~id[x], x+1,n]的和
三:二中的b大小为n*n显然不行。考虑将b[i]改为一颗权值线段树(求一段值域内的元素个数),这样大小变为nlogn。
四:每一次删除一个点,会修改线段树b[id[x]~n],用时过久。不放对所有权值线段树的同一个区间求前缀和(实例:主席树)查询变为作差;这时修改线段树b[id[x]~n]相当于是单点修改更新前缀和,考虑使用树状数组来完成。

就是树状数组套权值线段树了。

#include <bits/stdc++.h>
using namespace std;

const int n=1e6+10;

int n,m,tot;
long long ans;
int root[n],bit[n],id[n],a[n],f[n],g[n];

struct edge {
    int ls,rs,sum;
} t[n*30];

void update(int&x,int l,int r,int w) {
    if(!x) x=++tot;
    t[x].sum+=(w!=0);
    if(l==r) return;
    int mid=(l+r)>>1;
    if(w<=mid) update(t[x].ls,l,mid,w);
    else update(t[x].rs,mid+1,r,w);
}
int l[n],cntl,r[n],cntr;
int f1(int x,int y,int w) {
    cntl=cntr=0, x--;
    for(; x>0; x-=(x&-x)) l[++cntl]=root[x];
    for(; y>0; y-=(y&-y)) r[++cntr]=root[y];
    int l=1, r=n, ret=0;
    while(l!=r) {
        int mid=(l+r)>>1;
        if(w<=mid) { //右区间全满
            for(int i=1; i<=cntl; ++i) ret-=t[t[l[i]].rs].sum;
            for(int i=1; i<=cntr; ++i) ret+=t[t[r[i]].rs].sum;
            for(int i=1; i<=cntl; ++i) l[i]=t[l[i]].ls;
            for(int i=1; i<=cntr; ++i) r[i]=t[r[i]].ls;
            r=mid;
        } else {
            for(int i=1; i<=cntl; ++i) l[i]=t[l[i]].rs;
            for(int i=1; i<=cntr; ++i) r[i]=t[r[i]].rs;
            l=mid+1;
        }
    }
    return ret;
}
int g1(int x,int y,int w) {
    cntl=cntr=0, x--;
    for(; x>0; x-=(x&-x)) l[++cntl]=root[x];
    for(; y>0; y-=(y&-y)) r[++cntr]=root[y];
    int l=1, r=n, ret=0;
    while(l!=r) {
        int mid=(l+r)>>1;
        if(mid<w) { //左区间全满
            for(int i=1; i<=cntl; ++i) ret-=t[t[l[i]].ls].sum;
            for(int i=1; i<=cntr; ++i) ret+=t[t[r[i]].ls].sum;
            for(int i=1; i<=cntl; ++i) l[i]=t[l[i]].rs;
            for(int i=1; i<=cntr; ++i) r[i]=t[r[i]].rs;
            l=mid+1;
        } else {
            for(int i=1; i<=cntl; ++i) l[i]=t[l[i]].ls;
            for(int i=1; i<=cntr; ++i) r[i]=t[r[i]].ls;
            r=mid;
        }
    }
    return ret;
}
int sum(int x,int y=0) {
    for(; x>0; x-=(x&-x)) y+=bit[x];
    return y;
}
void add(int x,int y) {
    for(; x<=n; x+=(x&-x)) bit[x]+=y;
} 

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i) {
        scanf("%d",&a[i]);
        id[a[i]]=i;
        f[i]=sum(n)-sum(a[i]);
        add(a[i],1);
        ans+=f[i];
    }
    for(int i=1; i<=n; ++i) bit[i]=0;
    for(int i=n; i>=1; --i) {
        g[i]=sum(a[i]);
        add(a[i],1);
    }
    update(root[0],1,n,0);
    for(int x; m--; ) {
        scanf("%d",&x);
        printf("%lld\n",ans);
        ans-=f[id[x]]-f1(1,id[x],x)+g[id[x]]-g1(id[x],n,x);
        for(int i=id[x]; i<=n; i+=(i&-i)) {
            update(root[i],1,n,x);
        }
    }
    return 0;
}