其实刚开始一看到这道题就想到了逆序对数,用归并或者树状数组来搞,不过加上了一个权值,顿时头就大了。。。。不知道该怎么换了。。。,后来发现读题真的很重要,题目给的数的范围是1-n之间的,而且没有重复。这样写法就变得很简单,而且在线了
code:
#include <iostream> #define LL __int64 using namespace std; const int MAXN = 100010 ; int n; struct node { int cnt; LL val; }c[MAXN]; int lowbit(int i) { return i&(-i); } void add(int i,int num) { while(i<=n) { c[i].val+=num; c[i].cnt+=1; i+=lowbit(i); } } LL getsum(int i) { LL sum=0; while(i) { sum+=c[i].val; i-=lowbit(i); } return sum; } LL getnum(int i) { LL cnt=0; while(i) { cnt+=c[i].cnt; i-=lowbit(i); } return cnt; } int main() { int i,tmp; LL k1,k2,ans=0; cin>>n; for(i=1;i<=n;i++) { cin>>tmp; add(tmp,tmp); k1=i-getnum(tmp); // k1是 到这个数为止,在这个数之前 比这个数大的数有多少个,注意本题没有相同的值 if(k1) { k2=getsum(n)-getsum(tmp); //因为 n总是大于等于x ,所以可以直接这样写 ans+= k1*tmp + k2; } } cout<<ans<<endl; return 0; }