首页 > 代码库 > bestcoder#23 1002 Sequence II 树状数组+DP

bestcoder#23 1002 Sequence II 树状数组+DP

2024-08-09 03:12:01   211人阅读

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<b<c<d≤n
2. Aa<Ab
3. Ac<Ad
 
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
151 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+100const 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\n",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\n",ans);    }}

 

 
 

bestcoder#23 1002 Sequence II 树状数组+DP


联系
我们