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

[51Nod](1019)逆序数 ---- 树状数组+离散化★

程序员文章站 2022-05-11 17:07:30
...

题目链接

做法:

  • 复习一下树状数组~
  • 首先直接暴力求的话,O(n^2) 一定会超时。(`・ω・´) 为什么有时这句话总出现在博文呢?因为提醒自己有时不要瞎暴力
  • 利用树状数组求逆序数是非常经典的一种写法,下面说一下我自己的理解
  • 利用树状数组的特点,单点修改和区间查询的特性。
  • 1.对于每一个位置的数,我们update更新,从这个位置更新值(val+1),即比我大的数都加1(包括自己)。
  • 2.所以使用query(该位置的数)时,求得的就是比我小的数有多少个(包括这个数本身)
  • 通俗的讲就是,更新当前数到最大数的一个档案,比某个数小的数有n个,一定是update了n次
  • ヾ(◍°∇°◍)ノ゙ 是不是这样非常巧妙~
  • 所以ans = i - query(该位置的数)。 i表示这是第i个插入序列中的数,所以这个差表示的就是比我大的数有多少个
  • 又因为最大的数有1e9,酱紫肯定会撑爆我们的树状数组,所以我们离散化,用序列1~N的编号表示该数,从而达到离散的目的,这样能唯一表示,还能解决重复数字的问题

AC代码:

#include<bits/stdc++.h>
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define rep(i,s,t) for(int i = (int)(s); i <= (int)(t); i++)
#define rev(i,t,s) for(int i = (int)(t); i >= (int)(s); i--)
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x).size()
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const double PI = 4*atan(1.0);
const int maxm = 1e8+5;
const int maxn = 1e5+5;
const int INF = 0x3f3f3f3f;
struct node{
    int v;
    int idx;
};
node a[maxn];
bool cmp(node a,node b)
{
    return a.v<b.v;
}
ll c[maxn];
int lowbit(int x) {return x&(-x);}
void update(int st,ll x,int n)
{
    for(int i=st;i<=n;i+=lowbit(i)) c[i]+=x;
}
ll query(int x)
{
    ll ans = 0;
    for(int i=x;i;i-=lowbit(i)) ans+=c[i];
    return ans;
}
int b[maxn];
int main()
{
    #ifdef LOCAL_FILE
    freopen("in.txt","r",stdin);
    #endif // LOCAL_FILE
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].v);
        a[i].idx = i;
    }
    sort(a+1,a+1+n,cmp); //离散化
    for(int i=1;i<=n;i++) //离散化
    {
        b[a[i].idx] = i;
    }
    ll ans = 0;
    for(int i=1;i<=n;i++)
    {
        update(b[i],1,n);
        ans += i-query(b[i]);
    }
    printf("%lld\n",ans);
    return 0;
}