记录编号 |
233229 |
评测结果 |
AAWWWWWWWW |
题目名称 |
三元数对 |
最终得分 |
20 |
用户昵称 |
liu_runda |
是否通过 |
未通过 |
代码语言 |
C++ |
运行时间 |
0.036 s |
提交时间 |
2016-03-04 11:10:28 |
内存使用 |
0.98 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int ori[30005];
int dict[30005];
int num[30005];
int c[30005];
int before[30005];
int buf[30005];
/*void merge(int l,int r,int mid){
// printf("m(%d %d)\n",l,r);
int i=l,j=mid,k=0;
while(i<mid&&j<r){
if(ori[num[i]]<ori[num[j]]){
buf[k++]=num[i++];
}else{
buf[k++]=num[j++];
}
}
while(j<r)buf[k++]=num[j++];
while(i<mid)buf[k++]=num[i++];
memcpy(num+l,buf,(r-l)*4);
// for(int x=l;x<r;++x)num[x]=buf[x];
}
void mergesort(int l,int r){
// printf("ms(%d %d)\n",l,r);
if(r-l<=1)return;
int mid=(l+r)>>1;
mergesort(l,mid);
mergesort(mid,r);
merge(l,r,mid);
}*/
void swap(int a,int b){
int tmp=num[a];
num[a]=num[b];
num[b]=tmp;
}
void quicksort(int l,int r){
// printf("qs(%d %d)",l,r);
if(r-l<=1)return;
int i=l+1,j=l+1;
while(j<r){
if(ori[num[j]]>ori[num[l]])j++;
else{
swap(i,j);
i++;j++;
}
}
// for(int i=l;i<r;++i)printf("%d ",num[i]);
// printf("\n");
if(i!=r&&i!=l+1)swap(l,i);
if(i==r){
swap(l,i-1);
i--;
}
else if(i==l+1)i--;
quicksort(l,i);
quicksort(i+1,r);
}
int lowbit(int x){
return x&-x;
}
void update1(int x){
for(int i=x;i<30005;i+=lowbit(i))c[i]++;
}
int sum1(int x){
int ans=0;
for(int i=x;i;i-=lowbit(i))ans+=c[i];
return ans;
}
void update2(int x){
for(int i=x;i;i-=lowbit(i))c[i]++;
}
int sum2(int x){
int ans=0;
for(int i=x;i<30005;i+=lowbit(i))ans+=c[i];
return ans;
}
int read(){
int x;char ch;
while(ch=getchar(),ch>'9'||ch<'0');
x=ch-48;
while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
return x;
}
int main(){
freopen("three.in","r",stdin);
freopen("three.out","w",stdout);
int n=read();
for(int i=1;i<=n;++i){
num[i]=i;
ori[i]=read();
}
quicksort(1,n+1);
// for(int i=1;i<=n;++i)printf("%d ",num[i]);
// printf("\n");
int cnt=3,old=-1;
for(int i=1;i<=n;++i){
if(ori[num[i]]!=old){
dict[num[i]]=++cnt;
old=ori[num[i]];
}else{
dict[num[i]]=cnt;
}
}
/// for(int i=1;i<=n;++i)printf("%d ",dict[i]);
// printf("\n");
for(int i=1;i<=n;++i){
update1(dict[i]);
before[i]=sum1(dict[i]-1);
}
memset(c,0,sizeof(c));
long long tot=0;
for(int i=n;i>=1;--i){
update2(dict[i]);
tot+=sum2(dict[i]+1)*before[i];
}
printf("%lld",tot);
fclose(stdin);fclose(stdout);
return 0;
}