Description
著名乐队L2B宣布要在Music岛举办一场演唱会，售票当天那家伙，那场面，相当热闹，真是锣鼓喧天，鞭炮齐鸣，旌旗招展，人山人海啊。
L2B的粉丝小C得知消息，飞奔到售票处，却发现买票的人已经排起了长龙的队伍，正当他万般绝望的时候，他看到了敬爱的PengSir，于是他向PengSir请求帮助。PengSir嘴角微微一笑，说道：票我倒是可以给你一张，可是白给的话就太没意思了，这样吧，我有一个问题考考你，如果你能在5秒钟内答出来的话，我就送你这张票，怎么样？小C急不可待的说：没问题。于是PengSir徐徐说道：这里排队的一共有N个人，每个人之前都发了一个号码牌（数字从1到N各不相同），我们假定队头是前，队尾是后，每个人P最多能够买的票数是在这个人后面而且号码牌的数字比这个人P的数字小的人数总和。我的问题是，告诉你每个人手中的号码，你来算出今天最多一共能卖出去多少张票S么？
举个例子说吧
假设我们现在有10个人在排队，他们手中的号码分别是2 5 8 7 6 1 9 4 10 3，那么可以很快算出他们最多可以买的票数分别是1 3 5 4 3 0 2 1 1 0，所以最多一共能卖出去1+3+5+4+3+0+2+1+1+0=20张票。怎么样？明白了吧？
小C听完，顿时傻眼，亲爱的朋友，你能帮助小C来实现自己心愿吗？
Input
输入有多个测试用例
每个测试用例的第一行是正数N（ 0 < N <= 30000 ），
第二行是N个整数Ai（ 0 < Ai <= N ），且每个Ai出现且仅出现一次，每两个相邻的整数之间有且仅有一个空格隔开
Output
对于每一个测试用例，只输出一个整数S
Sample Input
10
2 5 8 7 6 1 9 4 10 3
Sample Output
20
* 从n开始到1 将a[i]所代表的数 安放到树状数组的相应位置上 * * 每个数进入数组以后 都求一下它前面数的个数 * * 把这些数的个数加起来 即是所求的和 * * 用树状数组的目的是 求前n项的和可以节省时间 * * 达到不超时的目的 Oh！yeah ~ ！ * **********************************************************/ #include < iostream > #include < string .h > #include < stdio.h > using namespace std; const int N = 30010 ; int t[N],a[N],n; void add( int x) // 改变下表为x的元素的值 会导致所有x的父节点的值的改变 { for (;x <= n;x += x &- x) t[x] += 1 ;} int sum( int x){ int ans = 0 ; for (;x > 0 ;x -= x &- x) { ans += t[x]; } return ans;} int main(){ while ( ~ scanf( " %d " , & n)) // 与!=EOF相同 { int i; memset(t, 0 , sizeof (t)); for (i = 1 ;i <= n;i ++ ) scanf( " %d " , & a[i]); int ans = 0 ; for (i = n;i >= 1 ;i -- ) { ans += sum(a[i]); add(a[i]); } printf( " %d\n " ,ans); } return 0 ;}转载于:https://www.cnblogs.com/cyiner/archive/2011/05/16/2048205.html
相关资源：树状数组算法的描述和代码的实现