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,b,c,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,0,sizeof(pre));
35 memset(last,0,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("%lld
",ans);
50 }
51 return 0;
52 }