离散化和排序后的序号问题搞得我实在是头痛
不过树状数组解逆序和偏序一类问题真的好用
更新：hdu的数据弱的真实，我交上去错的代价也对了。。
下面的代码是错的
/* 每个点的贡献度=权值*在这个点之前的比它大的点数量+在这个点前面比它大的所有点之和 开两个树状数组，一个保存相应序号的点值，另一个保存相应序号的 */ #include<bits/stdc++.h> using namespace std; #define ll long long #define maxn 100005 struct node{ int x,id; bool operator<(const node & a)const{ return x<a.x; } }a[maxn]; int b[maxn];//b数组按输入顺序维护每个点的权值，序号 ll bit1[maxn],bit2[maxn]; int n; void add1(int x){ for(int i=x;i<=maxn;i+=i&-i) bit1[i]++; } void add2(int x,int num){ for(int i=x;i<=maxn;i+=i&-i) bit2[i]+=num; } ll query1(int x){ ll res=0; for(int i=x;i;i-=i&-i) res+=bit1[i]; return res; } ll query2(int x){ ll res=0; for(int i=x;i;i-=i&-i) res+=bit2[i]; return res; } int main(){ while(scanf("%d",&n)==1){ for(int i=1;i<=n;i++) scanf("%d",&a[i].x),a[i].id=i; sort(a+1,a+1+n); for(int i=1;i<=n;i++) b[a[i].id]=i;//其实就是一次映射,由于a数组进行了排序，该映射要找到原序列的每个数在排序后，在新的数组里的位置 ll ans=0; for(int i=1;i<=n;i++){ ans+=a[b[i]].x*(query1(100000)-query1(a[b[i]].x));//通过映射i->b[i],找到每个数新的位置 ans+=query2(100000)-query2(a[b[i]].x); add1(b[i]); add2(b[i],a[b[i]].x); } printf("%lld ",ans); } return 0; }
下面的代码是对的
#include<iostream> using namespace std; #define N 100001 int n; struct node { int index; __int64 sum; }c[N]; int lowbit(int x) { return x&(-x); } void update(int x,int k,int s) { while(x<=n) { c[x].index+=k; c[x].sum+=s; x+=lowbit(x); } } int getsum_index(int x) { int ans=0; while(x>0) { ans+=c[x].index; x-=lowbit(x); } return ans; } __int64 getsum_sum(int x) { __int64 ans=0; while(x>0) { ans+=c[x].sum; x-=lowbit(x); } return ans; } int main(void) { while(~scanf("%d",&n)) { int i; __int64 ans=0; memset(c,0,sizeof(c)); for(i=1;i<=n;i++) { int x; scanf("%d",&x); update(x,1,x); __int64 k1=i-getsum_index(x); if(k1!=0) { __int64 k2=getsum_sum(n)-getsum_sum(x); ans=ans+k1*x+k2; } } printf("%I64d/n",ans); } }