首页 > 代码库 > (树状数组) HOJ 2275
(树状数组) HOJ 2275
Number sequence
| My Tags |
|---|
| Source : SCU Programming Contest 2006 Final | |||
| Time limit : 1 sec | Memory limit : 64 M | ||
Submitted : 1598, Accepted : 432
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.
InputThe first line is an integer N (N <= 50000). The second line contains N integer(s): A1, A2, ..., An(0 <= Ai <= 32768).
OutputThere is only one number, which is the the number of different collocation.
Sample Input51 2 3 4 1Sample Output
6
分别统计每个数左边小的，然后在逆序统计一下乘起来就好啊
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include<string>#include<algorithm>using namespace std;#define N 50010int n,a[N],c[N],lef[N];long long ans;int lowbit(int x){ return x&(-x);}void update(int pos,int m){ while(pos<N) { c[pos]+=m; pos+=lowbit(pos); }}int sum(int x){ int sum=0; while(x>0) { sum+=c[x]; x-=lowbit(x); } return sum;}int main(){ while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); ans=0; memset(c,0,sizeof(c)); memset(lef,0,sizeof(lef)); for(int i=1;i<=n;i++) { lef[i]=sum(a[i]-1); update(a[i],1); } memset(c,0,sizeof(c)); for(int i=n;i>=1;i--) { ans+=lef[i]*sum(a[i]-1); update(a[i],1); } printf("%lld\n",ans); } return 0;}
(树状数组) HOJ 2275
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。