当前位置：首页 -> 基础 -> c++编程基础

HDOJ 5147 Sequence II 树状数组

2015-01-24 05:39:28 · 作者: · 浏览: 3
标签: HDOJ 5147 Sequence


树状数组:

维护每一个数前面比它小的数的个数,和这个数后面比他大的数的个数

再枚举每个位置组合一下

Sequence II

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 121 Accepted Submission(s): 58

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

Source BestCoder Round #23 


/* ***********************************************
Author        :CKboss
Created Time  :2014年12月20日 星期六 21时38分00秒
File Name     :HDOJ5147.cpp
************************************************ */

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
             using namespace std; typedef long long int LL; const int maxn=55000; int a[maxn]; int n; LL sum1[maxn],sum2[maxn]; int t1[maxn],t2[maxn]; int lowbit(int x) { return x&(-x); } /// 1 找比当前数小的 2 找比当前数大的 void init() { memset(sum1,0,sizeof(sum1)); memset(sum2,0,sizeof(sum2)); memset(t1,0,sizeof(t1)); memset(t2,0,sizeof(t2)); } void add(int kind,int p) { if(kind==1) for(int i=p;i
             
              =1;i--) { int ss=sum(2,a[i]); sum2[i]=sum2[i+1]+ss; add(2,a[i]); } LL ans=0; for(int i=2;i<=n-1;i++) { /// X...i i+1...X ans+=sum1[i]*sum2[i+1]; } cout<