时间戳

首页 > 技术文章 > 树状数组优化暴力求逆序对

树状数组优化暴力求逆序对

29taorz 2021-08-19 21:00 原文

树状数组优化暴力求逆序对

虽然说这个不难，但是为什么大佬们的博客都是一句话“用树状数组的性质”然后就是代码了qwq，小蒟蒻愣是呆了半小时才明白。

离散化

对于一个要求逆序对的数组，我们只关心数字间的大小关系，于是我们可以将数组中最小的数改成1，次小的改成2……

法一：

结构体保存数组num 和它在原数组里的下标

{3,1}{-1,2}{2,3}{-2,4}

然后按数字大小排序

{-2,4}{-1,2}{2,3}{3,1}

现在我们就得到了 4 2 3 1了。

for(int i=1;i<=n;i++)
    scanf("%d",&a[i].val),a[i].num=i;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
    rank[a[i].num]=i;

法二：

将原数组a复制得到b

将b排序，然后用二分去找a中的元素在b中的下标

for(int i=1;i<=n;i++)
    cin>>a[i],b[i]=a[i];
sort(b+1,b+n+1);
n=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++)
    a[i]=lower_bound(b+1,b+n+1,a[i])-b;

O(nlogn)

这样就可以得到离散化后的数组了，这个技巧可以用来去重去负数，可以在所有答案只与数字大小关系的情况下使用。

树状数组

a[]为原数组

求逆序对，就是求在对于没个i，a[1~i-1]中比a[i]大的数的个数的总和。

显然一个简单的处理方法就是每次让b[a[i]]+1，然后找b[1~i-1]的和就代表在a[1~i-1]中比a[i]小的数的个数，一减就可以得到比a[i]大的个数。

再看一眼，这不就是求b[1~i-1]的区间和吗，这里就可以用到树状数组了。（本人认为这个求逆序对的方法本质就是暴力，树状数组无非是个优化，叫树状数组逆序对属实误人子弟）

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int tree[500010],rank[500010],n;
long long ans; 
struct point
{
    int num,val;
}a[500010];
inline bool cmp(point q,point w)
{
    if(q.val==w.val)
        return q.num<w.num;
    return q.val<w.val;
}
inline void insert(int p,int d)
{
    for(;p<=n;p+=p&-p)
        tree[p]+=d; 
}
inline int query(int p)
{
    int sum=0;
    for(;p;p-=p&-p)
        sum+=tree[p];
    return sum;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].val),a[i].num=i;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
        rank[a[i].num]=i;
    for(int i=1;i<=n;i++)
    {
        insert(rank[i],1);
        ans+=i-query(rank[i]);
    }
    printf("%lld",ans);
    return 0;
}

 练手题 P3605 [USACO17JAN]Promotion Counting

dfs记录下第一次搜到该点时比它大的点，回溯时再记一次然后相减

#include<bits/stdc++.h>
using namespace std;
const int MM=100005;
int n,a[MM],b[MM],f,t[MM],head[MM],nxt[MM],to[MM],tot,ans[MM];
void add(int u,int v)
{
    nxt[++tot]=head[u];
    head[u]=tot;
    to[tot]=v;
}
int lowbit(int x)
{
    return x&(-x);
}
void insert(int x)
{
    for(;x<=n;x+=lowbit(x))
        t[x]++;
}
int query(int x)
{
    int ret=0;
    for(;x;x-=lowbit(x))
        ret+=t[x];
    return ret;
}
void dfs(int now)
{
    insert(a[now]);
    int tmp=query(n)-query(a[now]);
    for(int i=head[now];i;i=nxt[i])
        dfs(to[i]);
    ans[now]=query(n)-query(a[now])-tmp;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+n+1,a[i])-b;
    for(int i=2;i<=n;i++)
        cin>>f,add(f,i);
    dfs(1);
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<endl;
    return 0;
}
View Code

 

推荐阅读