Sequence II
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 375 Accepted Submission(s): 173
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.1≤a<b<c<d≤n
2.Aa<Ab
3.Ac<Ad
Please calculate how many quad (a,b,c,d) satisfy:
1.
2.
3.
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 integersA1,A2,…,An .
[Technical Specification]
1 <= T <= 100
1 <= n <= 50000
1 <=Ai
<= n
Each test case begins with a line contains an integer n.
The next line follows n integers
[Technical Specification]
1 <= T <= 100
1 <= n <= 50000
1 <=
<= 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
/* HDU 5147 树状数组 */ #include<iostream> #include<stdio.h> using namespace std; #define N 50010 int c[N],f[N],g[N],a[N]; int n; //所有大于x的加上d void add(int x,int d) { while(x<=n) { c[x]+=d; x+=x&(-x); } } //统计小于x的个数 int sum(int x) { int ans=0; while(x>0) { ans+=c[x]; x-=x&(-x); } return ans; } int main() { int t,i; __int64 ans,s; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); memset(c,0,sizeof(c)); for(i=1;i<=n;i++) { add(a[i],1); f[i]=sum(a[i])-1;//左边小于a[i]的个数 } memset(c,0,sizeof(c)); for(i=n;i>=1;i--) { add(a[i],1); g[i]=n-i+1-sum(a[i]);//右边大于a[i]的个数 } ans=0; s=0; for(i=1;i<=n;i++) { ans+=s*g[i];//与左边的相乘 s+=f[i];//统计右边的和 } printf("%I64d\n",ans); } return 0; }