bestcoder#23 1002 Sequence IIツリー配列+DP

7447 ワード

Sequence II
Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 652    Accepted Submission(s): 164
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 
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 <= 1001 <= n <= 500001 <= 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
 
#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

typedef long long ll;

using namespace std;

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 50005+100

const int inf=0x7fffffff;   //   

int a[maxn];

ll dp_qmin[maxn];

ll dp2[maxn],sum[maxn];

ll dp_hmax[maxn];

int n;

long long ans;



int lowbit(int x)

{

    return x&(-x);

}



void update(int x,ll val)

{

    while(x <= n)

    {

        sum[x] += val;

        x += lowbit(x);

    }

}



long long query(int x)

{

    long long s=0;

    while(x>0)

    {

        s += sum[x];

        x -= lowbit(x);

    }

    return s;

}



int main()

{

    //freopen("D.txt","r",stdin);

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        for(int i=1;i<=n;i++)

        {

            scanf("%d",&a[i]);

            dp_qmin[i]=0;

            dp2[i]=0;

            dp_hmax[i]=0;

            sum[i]=0;

        }

        for(int i=1;i<=n;i++){

            ll t=query(a[i]-1);

            dp_qmin[i]=t;

            dp_hmax[i]=(n-i)-(a[i]-1-t);

            //printf("i=%d dpmin=%lld dpmax=%lld
",i,dp_qmin[i],dp_hmax[i]);
update(a[i],1); } ll ans=0; ll sum1=0; sum1=dp_qmin[1]+dp_qmin[2]; for(int i=3;i<=n-1;i++) { ans+=sum1*dp_hmax[i]; sum1+=dp_qmin[i]; } printf("%I64d
",ans); } }