題目
題意：給你N個排列不規則的數，任務是把它從小到大排好，每次隻能交換相鄰兩個數，交換一次的代價為兩數之和，求最小代價
拿到這道題，我根本看不出這道題和樹狀數組有半毛錢關系，部落格之，全說用樹狀數組做，納尼。。。看來我還是太年輕。。
這道題還涉及到了逆序對，何為逆序對：對于一個包含N個非負整數的數組A[1..n]，如果有i < j，且A[ i ]>A[ j ]，則稱(A[ i] ,A[ j] )為數組A中的一個逆序對。
放到這道題中，如何求代價即：這有N個數，第i個數的代價 = 在i前面大于 i 的數字個數 * i + 在 i 前面大于 i 的數字之和。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 100001
int n;
struct node
{
int cnt;
__int64 sum;
}c[N];
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int s)
{
while(x<=n)
{
c[x].cnt+=1;
c[x].sum+=s;
x+=lowbit(x);
}
}
int getsum_cnt(int x)
{
int ans=0;
while(x>0)
{
ans+=c[x].cnt;
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,x);
__int64 k1=i-getsum_cnt(x);
//getsum_cnt(x)是小于等于x的數字的個數，i-getsum_cnt(x)就是大于x的數字的個數
if(k1!=0)
{
__int64 k2=getsum_sum(n)-getsum_sum(x);//[x+1,n]區間的數字值和，即[1,n]-[1,x]
ans=ans+k1*x+k2;
}
}
printf("%I64d\n",ans);
}
}
樹狀數組求逆序對個數
#include <bits/stdc++.h>
using namespace std;
const int Max = 1e3;
int c[Max],a[Max];
int n,t;
int Lowbit(int x)
{
return x&(-x);
}
void update(int i,int x)
{
while(i<=n)
{
c[i]+=x;
i+=Lowbit(i);
}
}
int sum(int x)
{
int sum=0;
while(x>0)
{
sum+=c[x];
x-=Lowbit(x);
}
return sum;
}
int Getsum(int x1,int x2)
{
return sum(x2)-sum(x1);
}
int main()
{
int ans = 0;
int x;cin>>n;
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
{
cin>>x;
update(x,1);
int k = i-sum(x);
//sum(x)是[1,i]中，小于等于x的數字的個數，
//則 i-sum(x)就是大于x的數字的個數
// cout<<"k="<<k<<endl;
ans+=k;
}
cout<<ans<<endl;
return 0;
}