hdu 5147 Sequence II【树状数组/线段树】

Sequence II
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

?

Problem Description
Long long ago,there is a sequence A with length n. All numbers in this sequence is no smaller than 1 and no bigger than n,and all numbers are different in this sequence.
Please calculate how many quad (a,b,c,d) satisfy:

1≤a<b<c<d≤n
Aa<Ab
Ac<Ad
Input
The first line contains a single integer T,indicating the number of test cases.
Each test case begins with a line contains an integer n.
The next line follows n integers A1,A2,…,An.

[Technical Specification]
1 <= T <= 100
1 <= n <= 50000
1 <= Ai <= n

Output
For each case output one line contains a integer,the number of quad.

Sample Input
1
5
1 3 2 4 5

Sample Output
4

题意：有一个长度为n的数列A，数列中的每个数都在1到n之间，且数列中不存在两个相同的数。
请统计有多少四元组(a,d)满足：

1≤a<b<c<d≤n
Aa<Ab
Ac<Ad

思路：
这是道树状数组/线段树基础题。我们平时更新线段树或树状数组时都是按输入顺序从1到n更新，而还有某些题是需要你以他给定的数值大小的范围建树，把输入的数放到相对应的位置上（一般是对应位置标记），然后进行相关操作，本题即使如此。
我们讲一下树状数组的做法，线段树同理，只不过写起来麻烦一点。这道题我们按道理来说是需要每次确定四个数的，但明显会t，所以我们之多枚举一个数（这道题确定b或者确定c都可以，我们这里讲一下确定b的做法）。既然确定了b，我们就得想办法确定出b前面比它小的数和它后面满足Ac<Ad的个数，所以这里我们引入前缀和，后缀和来维护。对于刚开始而言，树状数组的所有1至n的点都是还没有被标记的，每当输入一个数时，比如输入5，我们就将它放在5的那个位置上（即更新树状数组把5的位置标记为1），这样我们去查询5前面有多少个数被标记过了，说明这些数是先被输入的，位置在这个数前面，这样子我们就维护出了一个在b前面比Ab小的数的个数的数组。
那接下来我们要如何确定b后面的那些呢？这里我们可以稍微算一下，对于输入的第i个数a[i]，我们已经算出了前面比它小的数pre[i]，那么对于i+1位置的数来说，比它大的数就是n-a[i]-(i-1-pre[i])，n-a[i]代表i这个位置后面还有多少个数，i-1-pre[i]代表i前面有多少个数比a[i]大，这样就可以算出i后面有多少个数比a[i]大。把这个后缀和维护出来，枚举b的位置把每个点的可能种类数加起来便可，注意答案可能爆int。

代码：

 1 #include "stdio.h"
 2 #include "string.h"
 3 const int N=1e5+5;  4 
 5 int t,n,a[N],c[N];  6 long long ans,pre[N],last[N];  7 
 8 int lowbit(int x)  9 { 10     return x&(-x); 11 } 12 
13 int update(int x) 14 { 15     for(int i=x;i<=n;i+=lowbit(i)) 16         c[i]++;                      ///标记该点
17 } 18 
19 int getsum(int x) 20 { 21     int sum=0; 22     for(int i=x;i>=1;i-=lowbit(i)) 23         sum+=c[i];                  ///算i位置前比a[i]小的数的个数
24     return sum; 25 } 26 
27 int main() 28 { 29     scanf("%d",&t); 30     while(t--) 31  { 32         ans=0; 33         memset(c,0,sizeof(c)); 34         memset(pre,sizeof(pre)); 35         memset(last,sizeof(last)); 36         scanf("%d",&n); 37         for(int i=1;i<=n;i++) 38  { 39             scanf("%d",&a[i]); 40             pre[i]=getsum(a[i]);           ///pre[i]代表比a[i]小的数的个数
41  update(a[i]); 42  } 43         for(int i=n;i>=1;i--) 44             last[i]=n-a[i]-(i-1-pre[i]);     ///算出i位置后面比a[i]大的数的个数
45         for(int i=n;i>=1;i--) 46             last[i]+=last[i+1];             ///累加即使i点后面满足Ac<Ad的这个数 47  for(int i=1;i<=n;i++) 48  ans+=(pre[i]*last[i+1]); ///枚举b点位置累加答案
49         printf("%lldn",ans); 50  } 51     return 0; 52 }