hdu 4000 Fruit Ninja 树状数组

浏览数：23 / 时间：2015年06月08日

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4000

Recently, dobby is addicted in the Fruit Ninja. As you know, dobby is a free elf, so unlike other elves, he could do whatever he wants.But the hands of the elves are somehow strange, so when he cuts the fruit, he can only make specific move of his hands. Moreover, he can only start his hand in point A, and then move to point B,then move to point C,and he must make sure that point A is the lowest, point B is the highest, and point C is in the middle. Another elf, Kreacher, is not interested in cutting fruits, but he is very interested in numbers.Now, he wonders, give you a permutation of 1 to N, how many triples that makes such a relationship can you find ? That is , how many (x,y,z) can you find such that x < z < y ?

题意描述：给出n个数1～n的随机排列，找出这样的三元组（x,y,z）的个数：x<y<z && an[x]<an[z]<an[y]。

算法分析：对于每个x，求出x后面比an[x]大的数的个数，那么我们可以得到x**（小中大和小大中）的个数，之后在往数列后面遍历的时候，减去原来小中大的情况即可。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #define inf 0x7fffffff
 8 using namespace std;
 9 typedef long long LL;
10 const int maxn=100000+10;
11 const int MOD=100000007;
12 
13 int n,an[maxn];
14 LL x[maxn];
15 
16 int lowbit(int u) {return u&(-u); }
17 void add(int i,int dd)
18 {
19     while (i<=maxn)
20     {
21         x[i] += dd;
22         i += lowbit(i);
23     }
24 }
25 LL sum(int i)
26 {
27     LL ret=0;
28     while (i>0)
29     {
30         ret += x[i];
31         i -= lowbit(i);
32     }
33     return ret;
34 }
35 
36 int main()
37 {
38     int t,ncase=1;scanf("%d",&t);
39     while (t--)
40     {
41         scanf("%d",&n);
42         for (int i=1 ;i<=n ;i++) scanf("%d",&an[i]);
43         memset(x,0,sizeof(x));
44         LL ans=0;
45         for (int i=1 ;i<=n ;i++)
46         {
47             add(an[i],1);
48             LL temp1=sum(an[i]-1);
49             LL temp2=n-an[i]-((i-1)-temp1);
50             ans -= temp1*temp2;
51             if (temp2>=2) ans += (temp2-1)*temp2/2;
52         }
53         printf("Case #%d: %I64d\n",ncase++,ans%MOD);
54     }
55     return 0;
56 }