题目链接：http://icpc.njust.edu.cn/Problem/Hdu/2838/
题目解法：题目给出一个1-n的排列，操作只有一种：交换相邻的元素，代价是两个元素之和，问将该序列变成升序排列的最小代价。就是要在线求解，每输入一个数a就要查询之前的数中有多少数比a大，这些数由于在a的前面，所以都会与a发生一次交换，否则a无法排在他们前面。假设a前面有k个数比a大，则代价之一是k*a。另一部分代价来自于交换这些数时前面的比a大的数的和。我们可以用树状数组高效的求出截止a位置的逆序对数量，并且可以用另一个树状数组维护比a小的数的和，这个操作很简单，只需要没次输入x时在x位置加上x就行，然后对a求前缀和就可得比a小的所有的数的和，由于所有的数都是小于等于n的，所以大于a的数的和是小于等于n的数的和减去小于等于x的数的和（容斥原理）。最后要注意的一点是要用long long整数。
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned int ui; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 #define pf printf 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 #define prime1 1e9+7 9 #define prime2 1e9+9 10 #define pi 3.14159265 11 #define scand(x) scanf("%llf",&x) 12 #define f(i,a,b) for(int i=a;i<=b;i++) 13 #define scan(a) scanf("%d",&a) 14 #define dbg(args) cout<<#args<<":"<<args<<endl; 15 #define pb(i) push_back(i) 16 #define ppb(x) pop_back(x) 17 #define inf 0x3f3f3f3f 18 #define maxn 100010 19 int n,m,t; 20 ll sum[maxn],c[maxn]; 21 ll lowbit(ll x) 22 { 23 return x&(-x); 24 } 25 void update(int x,int y) 26 { 27 for(int i=x;i<=n;i+=lowbit(i)) 28 { 29 c[i]+=y;//c[i]=1时表示插入数i 30 sum[i]+=x;//sum[i]:可以理解为在i位置上放i 31 } 32 } 33 ll query(int x)//求出小于等于x的所有数之和 34 { 35 ll ans=0; 36 for(int i=x;i;i-=lowbit(i)) 37 { 38 ans +=sum[i]; 39 } 40 return ans; 41 } 42 ll query2(int x)//求出比x小的数的个数 43 { 44 ll ans=0; 45 for(int i=x;i;i-=lowbit(i)) 46 { 47 ans+=c[i]; 48 } 49 return ans; 50 } 51 int main() 52 { 53 //freopen("input.txt","r",stdin); 54 //freopen("output.txt","w",stdout); 55 std::ios::sync_with_stdio(false); 56 scan(n); 57 int x; 58 ll ans=0 ; 59 f(i,1,n) 60 { 61 scan(x); 62 ll tmp=i-1-query2(x-1);//选出比x大的数的个数,tmp=0时表示i是当前最大的数，所以不需要 63 //dbg(tmp); 64 if(tmp!=0) 65 { 66 ans+=tmp*x; 67 ans+=query(n)-query(x);//选出比x大但是小于等于n的数(因为编号是连续的，所以最大是n) 68 } 69 update(x,1); 70 } 71 pf("%lld ",ans); 72 }