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
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);
}
}