Zlc晨鑫 @ 2021-08-05 18:16:15
RT,这是我自己学的离散化。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e5 + 10;
int a[N], v[N], c[N], m, n;
int lowbit(int x)
{
return x & (~x + 1);
}
// 离散化begin
void init()
{
sort(v + 1, v + n + 1);
m = unique(v + 1, v + n + 1) - v - 1;
}
int ask(int x)
{
return lower_bound(v + 1, v + m + 1, x) - v;
}
// 离散化end
// 树状数组begin
void add(int x, int k)
{
for ( ; x <= m; x += lowbit(x))
c[x] += k;
}
int query(int x)
{
int ans = 0;
for ( ; x; x -= lowbit(x))
ans += c[x];
return ans;
}
// 树状数组end
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
v[i] = a[i];
}
init();
long long ans = 0;
for (int i = 1; i <= n; ++i)
{
add(ask(a[i]), 1);
ans += i - query((ask(a[i])));
// 所有数的个数-小于等于x的数的个数=大于x的数的个数
}
printf("%lld\n", ans);
return 0;
}
可是题解里面那种写cmp的离散化是啥啊?
这两个的复杂度一样吗qwq?
by Zlc晨鑫 @ 2021-08-05 18:17:57
所以,这两种离散化是不是不用二分的更快?
by _caiji_ @ 2021-08-05 19:30:59
两个离散化都是可行的,时间复杂度一样都是
5
19260817 1919810 1919810 1919810 114514
您的离散化会输出:
3 2 2 2 1
题解的离散化的一种可能输出:
5 2 3 4 1
by Zlc晨鑫 @ 2021-08-14 14:29:54
@caijianhong 可是查询起来是不是题解的那种更快?