题目描述
给出一个长度为 $n$ 的整数序列，求序列中的逆序对数量
树状数组
首先对序列进行离散化
先排序，再去重，使 $b[1]$ 到 $b[m]$ 是严格单调递增的整数序列，并包含了 $a$ 数组中的每一个数
for(int i = 1; i <= n; i ++) b[i] = a[i];
sort(b + 1, b + n + 1);
m = 1;
for(int i = 2; i <= n; i ++)
if(b[i] != b[m]) b[++ m] = b[i];
$find(a[i])$ 返回整数 $a[i]$ 在 $b$ 数组中的下标
然后从前往后遍历 $a$ 数组，树状数组维护 $\leq b[i]$ 的数有几个
对于每一个 $a[i]$ 我们需要知道前面有几个数大于它
可以用前面的数的个数减去 $\leq a[i]$ 的数的个数，累加到答案里
res += sum(m) - sum(find(a[i]))
然后再往树状数组里加一个 $a[i]$ 就可以了
时间复杂度 $O(nlogn)$
C++ 代码
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 500010;
int n, m;
int a[N], b[N];
int find(int x)
{
int l = 1, r = m;
while(l < r)
{
int mid = l + r >> 1;
if(b[mid] >= x) r = mid;
else l = mid + 1;
}
return l;
}
int tr[N];
void add(int x)
{
for(int i = x; i <= m; i += i & -i) tr[i] ++;
}
int sum(int x)
{
int res = 0;
for(int i = x; i; i -= i & -i) res += tr[i];
return res;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]), b[i] = a[i];
sort(b + 1, b + n + 1);
m = 1;
for(int i = 2; i <= n; i ++)
if(b[i] != b[m]) b[++ m] = b[i];
LL res = 0;
for(int i = 1; i <= n; i ++)
{
int x = find(a[i]);
res += sum(m) - sum(x);
add(x);
}
printf("%lld", res);
return 0;
}
太帅了哥
可以用map替换掉find函数
去重的话不会影响答案吗
去重是离散化的一环，原数组还是 $a[1] … a[n]$
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
const int N = 1e5+10;
int tr[N];
int n,m;
int a[N];
vector[HTML_REMOVED] num;
int lowbit(int x) // 返回末尾的1
{
return x & -x;
}
void add(int x)
{
for(int i = x; i <= m; i += i & -i) tr[i] ++;
}
int sum(int x)
{
int res = 0;
for(int i = x; i; i -= i & -i) res += tr[i];
return res;
}
int find(int y){
return lower_bound(num.begin(),num.end(),y)-num.begin();
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
num.push_back(a[i]);
}
sort(num.begin(),num.end());
num.erase(unique(num.begin(),num.end()),num.end());
int res=0;
}
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
const int N = 1e5+10;
int tr[N];
int n,m;
int a[N];
vector[HTML_REMOVED] num;
int lowbit(int x) // 返回末尾的1
{
return x & -x;
}
void add(int x)
{
for(int i = x; i <= N; i += (i & -i)) tr[i] ++;
}
int sum(int x)
{
int res = 0;
for(int i = x; i; i -= (i & -i)) res += tr[i];
return res;
}
int find(int y)
{
return (lower_bound(num.begin(),num.end(),y) - num.begin() + 1);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
num.push_back(a[i]);
}
sort(num.begin(),num.end());
num.erase(unique(num.begin(),num.end()),num.end());
long long res=0;
}
帮你改好了
树状数组的询问和find函数有问题，最后是res要开long long
为啥find函数要+1，大佬
系统中的地址是十六进制表示的，所以返回出来的是一个十六进制，然后经过进制转换也就是+1，就是其在连续空间中的下标，其次是树状数组也是从1开始的
不能用容器吗
tle了无语
从后往前找的话前缀和操作只需要做一次，从前往后找是弄麻烦了。
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#define lowbit(x) x&(-x)
using namespace std;
const int N = 1e5 + 10;
struct Pro
{
int val, id;
}z[N];
int d[N], n;
int a[N];
long long ans;
bool cmp(Pro a, Pro b)
{
if(a.val == b.val)
return a.id < b.id;
return a.val < b.val;
}
void add(int x, int v)
{
while(x <= N)
{
d[x] += v;
x += lowbit(x);
}
}
int query(int x)
{
int res = 0;
while(x)
{
res += d[x];
x -= lowbit(x);
}
return res;
}
void Dico()
{
sort(z + 1, z + 1 + n, cmp);
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> z[i].val, z[i].id = i;
}
不需要去重哦
可以去重，他是用a保存了，b去重离散化而已
m = 1;
for(int i = 2; i <= n; i )
if(b[i] != b[m]) b[ m] = b[i];
请问这一段是什么意思呢，用它做什么呀
对有序数组的双指针去重
大佬，最后一句添加一个a[i]，您这里指的是a[i]的值，还是位置
位置
为啥离散化之后要排序呢 https://www.acwing.com/solution/content/10550/这个不排序的也可以过
我看不到哦，这个提交记录是有权限的
不好意思 应该是这个 https://www.acwing.com/solution/content/10550/
不排序咋二分