51Nod 1019树状数组离散化
程序员文章站
2022-05-11 17:04:14
...
开始RE,后面终于想通,数是10^9,然后离散化一下就行了;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
const int maxn = 100000 + 10;
#define INF 0x3f3f3f3f
#define clr(x,y) memset(x,y,sizeof x )
typedef long long ll;
#define eps 10e-10
const int Mod = 1000000007;
typedef pair<ll, ll> P;
ll tree[maxn];
ll a[maxn];
inline lowbit(ll x)
{
return x &(- x);
}
ll get(ll x)
{
ll ans = 0;
for(ll i = x; i > 0; i -= lowbit(i))
ans += tree[i];
return ans;
}
void update(ll x,ll val)
{
for(ll i = x; i < maxn; i += lowbit(i))
tree[i] += val;
}
int b[maxn];
int main()
{
ll n;
while( ~ scanf("%I64d",&n))
{
clr(tree,0);
for(ll i = 1; i <= n; i ++)
scanf("%I64d",&a[i]),b[i] = a[i];
sort(b+1,b+n+1);
int len = unique(b+1,b+n+1) - b;
for(int i = 1; i <= n; i ++)
a[i] = lower_bound(b+1,b+len + 1,a[i]) - b + 2;
// for(int i = 1; i <= n; i ++)
// cout << a[i] << " ";
// cout << endl;
ll ans = 0;
for(ll i = n; i >= 1; i --)
{
ans += get(a[i]);
update(a[i],1);
}
printf("%I64d\n",ans);
}
return 0;
}
下一篇: 51NOD 1019 逆序数