@[Little_AC_Prince](/space/show?uid=18993)
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=20007;
int n;
ll ans,su,BIT[3][N];
struct Node{
int num,pos;
}a[N];
inline bool cmp(Node p,Node q){
return p.num<q.num;
}
inline int lowbit(int x){
return x&(-x);
}
inline ll Query(int xz,int i){
ll su=0;
while(i>0)
su+=BIT[xz][i],i-=lowbit(i);
return su;
}
inline void Insert(int xz,int i,int x){
while(i<=N-1)
BIT[xz][i]+=x,i+=lowbit(i);
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d",&a[i].num,&a[i].pos);
sort(a,a+n,cmp);
for(int i=0;i<n;i++){
int x=Query(1,a[i].pos),s=Query(2,a[i].pos);
ans+=1ll*a[i].num*(a[i].pos*x-s+su-s-a[i].pos*(i-x));
su+=a[i].pos;
Insert(1,a[i].pos,1);
Insert(2,a[i].pos,a[i].pos);
}
printf("%lld\n",ans);
return 0;
}
```
by iwprc @ 2018-10-08 23:42:28
建议您将结构体中的元素换成longlong,或者计算时强制转换,并且树状数组内存开大一些。您可以参考一下我博客里的树状数组代码。(我最喜欢树状数组,blog里面有几篇树状数组的代码。)希望可以帮到您。
by 墨舞灵纯 @ 2018-10-08 23:43:18
@[U41485](/space/show?uid=41485) YYRjulao你好
by Sshenyyyu @ 2018-10-08 23:43:39
@[U41485](/space/show?uid=41485) 你对他真好啊……~~(我保证我没有嫉妒,我心里一点都不难受,一点都没有……)~~
by Kylin_xy @ 2018-10-08 23:45:11
@[面瘫者](/space/show?uid=53614) hyf 吧,嘤嘤嘤
by Sshenyyyu @ 2018-10-08 23:45:58
@[Fitzwilliam_Darcy](/space/show?uid=26800) 也许是,也许不是。。
by Kylin_xy @ 2018-10-08 23:46:51
# JSB发现树状数组比线段树好
by Sshenyyyu @ 2018-10-08 23:47:18
@[Fitzwilliam_Darcy](/space/show?uid=26800) 我发现
by Sshenyyyu @ 2018-10-08 23:47:31
我脑抽了,上课的时候改了一堂课,回家还看不出来。
by 以墨 @ 2018-10-10 22:09:40