hoj 2275 Number sequence(树状数组)

题意问你在序列中有多少个这样的关系式：ai <aj > ak (i<j<k)

两次使用树状数组。 注意：ai可以为0！！

/*This Code is Submitted by yew1eb for Problem 2275 at 2014-01-13 11:14:55*/
#include <stdio.h>
#include <string.h>
#define MAXA  32768
#define MAXN  50000 + 10
typedef long long LL;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
inline int lowbit(int x) {return (x&-x);}
void modify(int i, int d) {for(;i<=MAXA; i +=lowbit(i)) c[i] +=d;}
int sum(int i) {int ret = 0; for(;i>0; i-=lowbit(i)) ret+=c[i]; return ret;}

int main()
{
        int n, i;
        LL ans;
        while(scanf("%d",&n)!=EOF) {
                memset(c, 0, sizeof c);
                for(i=1; i<=n; ++i) {
                        scanf("%d",&d[i]);
                        a[i] = sum(d[i]);
                        modify(d[i]+1, 1);
                }
                memset(c, 0, sizeof c );
                for(i=n; i>0; --i) {
                        b[i] = sum(d[i]);
                        modify(d[i]+1, 1);
                }
                ans = 0;
                for(i=1; i<=n; ++i) {
                        ans += (LL)a[i]*(LL)b[i];
                }
                printf("%lld\n",ans);
        }
}
 

原文：http://blog.csdn.net/yew1eb/article/details/18217427