[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;
}