大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
Number sequence
Given a number sequence which has N element(s), please calculate the number of different collocation for three number Ai, Aj, Ak, which satisfy that Ai < Aj > Ak and i < j < k.
Input
The first line is an integer N (N <= 50000). The second line contains N integer(s): A1, A2, …, An(0 <= Ai <= 32768).
Output
There is only one number, which is the the number of different collocation.
Sample Input
5
1 2 3 4 1
Sample Output
6
题目就是统计序列中Ai < Aj > Ak（i < j < k）的个数。能够从前往后统计每一个元素之前小于它的数的个数，在从后往前统计每一个元素之后小于它的数的个数。然后乘积加和就可以。用树状数组轻松搞定！
！
AC代码例如以下：
#include<iostream>
#include<cstdio>
#include<cstring>
#define M 50010
using namespace std;
int c[M],num[M];
int l[M],n;
int lowbit(int a)
{
return a&-a;
}
void add(int a,int b)
{
while (a<M)
{
c[a]+=b;
a+=lowbit (a);
}
}
int sum(int a)
{
int ans=0;
while(a>0)
{
ans+=c[a];
a-=lowbit(a);
}
return ans;
}
int main ()
{
int i,j;
int a,b;
while(~scanf("%d",&n))
{
memset(c,0,sizeof c);
memset(num,0,sizeof num);
for(i=1;i<=n;i++)
{
scanf("%d",&num[i]);
l[i]=sum(num[i]-1);
add(num[i],1);
}
memset(c,0,sizeof c);
long long ans=0;
for(i=n;i>=1;i--)
{
ans=ans+(long long)sum(num[i]-1)*l[i];
add(num[i],1);
}
printf("%lld\n",ans);
}
return 0;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/117267.html原文链接：https://javaforall.net
