程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 5147 樹狀數組

hdu 5147 樹狀數組

編輯:C++入門知識

hdu 5147 樹狀數組


 

 

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
4
/**
hdu5147 樹狀數組
解題思路:
        要統計四元組的數量我們可以通過枚舉c,然後統計區間[1,c-1]有多少二元組(a,b)滿足a
#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;
}



 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved