hdu 5147 树状数组 - c++编程基础

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
2. Aa
3. Ac
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

/**
hdu5147 树状数组
解题思路：
        要统计四元组的数量我们可以通过枚举c，然后统计区间[1,c-1]有多少二元组(a,b)满足a
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; typedef long long LL; int C[100005],b[100005],c[100005],a[100005]; int n; int lowbit(int x) { return x&(-x); } int sum(int x) { int ret=0; while(x>0) { ret+=C[x]; x-=lowbit(x); } return ret; } void add(int x,int d) { while(x<=n) { C[x]+=d; x+=lowbit(x); } } int main() { int T; scanf(%d,&T); while(T--) { scanf(%d,&n); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); for(int i=1;i<=n;i++) scanf(%d,&a[i]); memset(C,0,sizeof(C)); for(int i=1;i<=n;i++) { b[i]=sum(a[i]); add(a[i],1); } memset(C,0,sizeof(C)); for(int i=n;i>=1;i--) { c[i]=sum(n)-sum(a[i])+c[i+1]; add(a[i],1); } LL ans=0; for(int i=2;i<=n-2;i++) { LL t1=b[i]; LL t2=c[i+1]; ans+=t1*t2; } printf(%I64d ,ans); } return 0; }