离散化和排序后的序号问题搞得我实在是头痛
不过树状数组解逆序和偏序一类问题真的好用
更新：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=;
for(int i=x;i;i-=i&-i)
res+=bit1[i];
return res;
}
ll query2(int x){
ll res=;
for(int i=x;i;i-=i&-i)
res+=bit2[i];
return res;
} int main(){
while(scanf("%d",&n)==){
for(int i=;i<=n;i++)
scanf("%d",&a[i].x),a[i].id=i;
sort(a+,a++n);
for(int i=;i<=n;i++) b[a[i].id]=i;//其实就是一次映射,由于a数组进行了排序，该映射要找到原序列的每个数在排序后，在新的数组里的位置
ll ans=;
for(int i=;i<=n;i++){
ans+=a[b[i]].x*(query1()-query1(a[b[i]].x));//通过映射i->b[i],找到每个数新的位置
ans+=query2()-query2(a[b[i]].x);
add1(b[i]);
add2(b[i],a[b[i]].x);
}
printf("%lld\n",ans); }
return ;
}
下面的代码是对的
#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=;
while(x>)
{
ans+=c[x].index;
x-=lowbit(x);
}
return ans;
}
__int64 getsum_sum(int x)
{
__int64 ans=;
while(x>)
{
ans+=c[x].sum;
x-=lowbit(x);
}
return ans;
}
int main(void)
{
while(~scanf("%d",&n))
{
int i; __int64 ans=;
memset(c,,sizeof(c));
for(i=;i<=n;i++)
{
int x;
scanf("%d",&x);
update(x,,x);
__int64 k1=i-getsum_index(x);
if(k1!=)
{
__int64 k2=getsum_sum(n)-getsum_sum(x);
ans=ans+k1*x+k2;
} }
printf("%I64d/n",ans);
}
}