hytallenxu @ 2024-05-10 18:15:22
先开始心血来潮，想用 treap 来写在线的逆序对，但是发现了打了上去只有30分。
后面发现是数据里面有重复的元素，导致treap的排名函数出了问题。
比如说：
2
1 1我的 treap 输出
原因就在于 treap 排名的定义是排名定义为比当前数小的数的个数 +1，导致重复元素都会当做同一个排名来看待。
请问有什么方法可以解决这个问题？
by daiyulong2024 @ 2024-05-10 18:17:02
@hytallenxu 树状数组或线段树或归并排序。
//树状数组做法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> a(1),c,ls(1);
ll n,ans,x;
ll lowbit(ll x) {
return x&-x;
}
void add(int id,ll x) {
for(int i=id;i<=n;i+=lowbit(i)) {
c[i]+=x;
}
}
ll getsum(ll x) {
int sum=0;
for(int i=x;i;i-=lowbit(i)) {
sum+=c[i];
}
return sum;
}
int main() {
cin>>n;
c.resize(n+5);
for(int i=1;i<=n;i++) {
cin>>x;
a.push_back(x),ls.push_back(x);
}
sort(ls.begin()+1,ls.end());
for(int i=1;i<=n;i++) {
a[i]=lower_bound(ls.begin()+1,ls.end(),a[i])-ls.begin()+1;
}
for(int i=n;i>=1;i--) {
ans+=getsum(a[i]-1);
add(a[i],1);
}
cout<<ans;
return 0;
}by daiyulong2024 @ 2024-05-10 18:17:23
@hytallenxu 别忘了加离散化。
by hytallenxu @ 2024-05-10 18:19:25
@daiyulong2024 我知道，但就是想问treap怎么做。
by _fairytale_ @ 2024-05-11 11:58:37
@hytallenxu 将下标也作为关键字比较即可，一个偷懒的办法是把值都变成它乘上 100000 加下标。
by _fairytale_ @ 2024-05-11 11:59:23
哦应该是 500000
by hytallenxu @ 2024-05-11 20:17:09
@fairytale 按您这个方法爆0了 Record
by _fairytale_ @ 2024-05-11 20:50:45
@hytallenxu 开 long long 就过了
by hytallenxu @ 2024-05-11 21:50:23
@fairytale ok thx