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.
1 5 1 3 2 4 5
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; }