hdu 5147 Sequence II

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

http://acm.hdu.edu.cn/showproblem.php?pid=5147

题意：问有多少个这样的四元组(a,b,c,d),满足条件是 1<=a<b<c<d; Aa<Ab; Ac<Ad;

思路：用树状数组求，从右向左求在这个数之前形成多少个逆序数对记录在r数组里面，然后在从左向右求出在输入这个数之前形成多少个逆序数对存在l数组里面，然后枚举b就行；

#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 50001
#define ll long long
using namespace std; int t;
int n;
int a[maxn];
int c[maxn];
ll l[maxn],r[maxn],sum[maxn]; int lowbit(int x)
{
return x&-x;
} void insert(int x,int v)
{
while(x<maxn)
{
c[x]+=v;
x+=lowbit(x);
}
} ll getsum(int x)
{
ll ans=;
while(x>)
{
ans+=c[x];
x-=lowbit(x);
}
return ans;
} int main()
{
scanf("%d",&t);
while(t--)
{
memset(sum,,sizeof(sum));
memset(a,,sizeof(a));
scanf("%d",&n);
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
}
memset(c,,sizeof(c));
sum[n+]=;
for(int i=n; i>=; i--)
{
r[i]=getsum(n)-getsum(a[i]);
insert(a[i],);
sum[i]=sum[i+]+r[i];
}
memset(c,,sizeof(c));
for(int i=; i<=n; i++)
{
l[i]=getsum(a[i]-);
insert(a[i],);
}
ll ans=;
for(int i=; i<=n; i++)
{
ans+=(l[i]*sum[i+]);
}
printf("%lld\n",ans);
}
return ;
}