bzoj3295 洛谷P3157、1393 动态逆序对—

题目：bzoj3295 https://www.lydsy.com/JudgeOnline/problem.php?id=3295

洛谷 P3157(同一道题) https://www.luogu.org/problemnew/show/P3157

洛谷 P1393(略有不同) https://www.luogu.org/problemnew/show/P1393

动态逆序对问题；

树状数组套权值线段树，动态开点；

就像树状数组那样做就可以了，每个线段树维护一段区间内的不同权值的数的个数；

删除一个点，就把答案减去它贡献的逆序对数量就可以了；

有点不太懂空间范围怎么算...

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

int const maxn=1e5+,maxm=maxn*;

int n,m,pos[maxn],t[maxn],rt[maxn],ls[maxm],rs[maxm],sum[maxm],cnt;

ll ans;

ll getsum(int x)

{

    ll ret=;

    for(;x;x-=(x&-x)) ret+=t[x];

    return ret;

}

void add(int x)

{

    for(;x<=n;x+=(x&-x)) t[x]++;

}

void update(int &x,int l,int r,int p,int v)

{

    if(!x)x=++cnt; sum[x]+=v;

    if(l==r)return;

    int mid=(l+r)>>;

    if(p<=mid)update(ls[x],l,mid,p,v);

    else update(rs[x],mid+,r,p,v);

}

void insert(int x,int p,int v)

{

    for(;x<=n;x+=(x&-x)) update(rt[x],,n,p,v);

}

ll ask(int x,int l,int r,int p)

{

    if(l==r)return sum[x];

    int mid=(l+r)>>;

    if(p<=mid)return ask(ls[x],l,mid,p);

    return sum[ls[x]]+ask(rs[x],mid+,r,p);

}

ll query(int x,int p)//<=p 的个数

{

    ll ret=;

    for(;x;x-=(x&-x)) ret+=ask(rt[x],,n,p);

    return ret;

}

ll pre(int x,int p){return query(p,n)-query(p,x);}

ll suf(int x,int p){return query(n,x)-query(p,x);}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=,x;i<=n;i++)

    {

        scanf("%d",&x); pos[x]=i;

        ans+=getsum(n)-getsum(x);

        add(x); insert(i,x,);

    }

    for(int i=,x;i<=m;i++)

    {

        printf("%lld\n",ans); scanf("%d",&x);

        ans-=pre(x,pos[x])+suf(x,pos[x]);

        insert(pos[x],x,-);

    }

    return ;

}

洛谷P1393，离散化一下即可。(通过数喜+1)

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const maxn=4e4+,maxm=maxn*;

int n,m,t[maxn],rt[maxn],ls[maxm],rs[maxm],sum[maxm],cnt,tot;

ll ans,a[maxn],b[maxn];

ll getsum(int x)

{

    ll ret=;

    for(;x;x-=(x&-x)) ret+=t[x];

    return ret;

}

void add(int x)

{

    for(;x<=n;x+=(x&-x)) t[x]++;

}

void update(int &x,int l,int r,int p,int v)

{

    if(!x)x=++cnt; sum[x]+=v;

    if(l==r)return;

    int mid=(l+r)>>;

    if(p<=mid)update(ls[x],l,mid,p,v);

    else update(rs[x],mid+,r,p,v);

}

void insert(int x,int p,int v)

{

    for(;x<=n;x+=(x&-x)) update(rt[x],,n,p,v);

}

ll ask(int x,int l,int r,int p)

{

    if(l==r)return sum[x];

    int mid=(l+r)>>;

    if(p<=mid)return ask(ls[x],l,mid,p);

    return sum[ls[x]]+ask(rs[x],mid+,r,p);

}

ll query(int x,int p)//<=p 的个数

{

    ll ret=;

    for(;x;x-=(x&-x)) ret+=ask(rt[x],,n,p);

    return ret;

}

ll pre(int x,int p){return query(p,n)-query(p,x);}

ll suf(int x,int p){return query(n,x)-query(p,x);}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)scanf("%lld",&a[i]),b[i]=a[i];

    sort(b+,b+n+);

    tot=unique(b+,b+n+)-b-;

    for(int i=;i<=n;i++) a[i]=lower_bound(b+,b+tot+,a[i])-b;

    for(int i=;i<=n;i++)

    {

        ans+=getsum(n)-getsum(a[i]);

        add(a[i]); insert(i,a[i],);

    }

    for(int i=,k;i<=m;i++)

    {

        printf("%lld ",ans); scanf("%d",&k);

        ans-=pre(a[k],k)+suf(a[k],k);

        insert(k,a[k],-);

    }

    printf("%lld\n",ans);

    return ;

}

巴特西

bzoj3295 洛谷P3157、1393 动态逆序对——树套树

最新文章

热门文章