前排$Orz \ wf \ julao$
by tocek_shiki @ 2018-08-14 00:31:42
@[wseqwq](/space/show?uid=111623) 您为什么要用$Fenwick\ Tree$
这不是裸的逆序对吗？
by tocek_shiki @ 2018-08-14 00:40:00
id 的 < 改成 >
输入：
5
1 1 1 1 2
应该输出0
by Hide_on_Bush_ @ 2018-08-14 00:56:53
感觉倒序好理解一点。。
by Hide_on_Bush_ @ 2018-08-14 00:59:48
@[wseqwq](/space/show?uid=111623) 用小号帮您改过了，这题真是玄学，**树状数组必须在一开始的时候从小大大排序！**而且不能忽略原顺序！然后再注意下一定要开 longlong！
（先用自己的大号 A 掉此题再用小号帮您调试应该不会变屎名吧 QωQ）
https://www.luogu.org/recordnew/show/9682019
```cpp
#include <cstdio>
#include <algorithm>
#define int long long
#define lowbit(x) (x&(-x))
struct nod{
int id,num;
inline bool operator < (const nod& rhs) const{
return num < rhs.num;
}
}g[500000+5];
int n,c[500000+5];
inline void update(int x){
for(;x<=n;x+=lowbit(x)) ++c[x];
}
inline long long query(int x){
long long ret=0;
for(;x;x-=lowbit(x)) ret+=c[x];
return ret;
}
signed main(){
#ifdef yyfLocal
freopen("testdata.in", "r", stdin);
#endif
scanf("%lld",&n);
for(register int i=1;i<=n;++i) scanf("%lld",&g[i].num),g[i].id=i;
std::stable_sort(g+1,g+n+1);
long long ans=0;
for(register int i=n;i;--i) ans+=query(g[i].id-1),update(g[i].id);
printf("%lld\n",ans);
return 0;
}
```
by Anguei @ 2018-08-14 02:05:51
@[wseqwq](/space/show?uid=111623) 对呀就算用$Binary Indexed Tree$还是错了，话说为啥要排序
by Aleph1022 @ 2018-08-14 06:51:17
哦哦离散化
by Aleph1022 @ 2018-08-14 06:56:52
果然要离散化……
by Aleph1022 @ 2018-08-14 07:01:00
本人AC代码，供参考：
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lowbit(x) ((x) & -(x))
using namespace std;
int n,a[500010],ind[500010],len;
long long ans,sum[500010];
inline void update(int x,long long k)
{
for(;x <= 500000;x += lowbit(x))
sum[x] += k;
}
inline long long query(int x)
{
long long ret = 0;
for(;x;x -= lowbit(x))
ret += sum[x];
return ret;
}
inline int getid(const int &x)
{
return lower_bound(ind + 1,ind + len + 1,x) - ind;
}
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
memcpy(ind,a,sizeof ind);
sort(ind + 1,ind + n + 1);
len = unique(ind + 1,ind + n + 1) - ind - 1;
for(register int i = 1;i <= n;++i)
{
update(getid(a[i]),1);
ans += query(500000) - query(getid(a[i]));
}
printf("%lld\n",ans);
}
```
by Aleph1022 @ 2018-08-14 07:08:31
@[fff团666](/space/show?uid=49562) 裸的逆序对 树状数组不是正解之一吗
by 老K @ 2018-08-14 08:24:43