HDU 5792 World is Exploding 树状数组+枚举

时间:2024-07-19 23:04:26

题目链接:

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

World is Exploding

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)
#### 问题描述
>![](http://images2015.cnblogs.com/blog/809202/201608/809202-20160807150517450-1373867798.png)
#### 输入
> The input consists of multiple test cases.
> Each test case begin with an integer n in a single line.
>
> The next line contains n integers A1,A2⋯An.
> 1≤n≤50000
> 0≤Ai≤1e9

输出

For each test case,output a line contains an integer.

样例

sample input

4

2 4 1 3

4

1 2 3 4

sample output

1

0

题解

数据给的50000,枚举两个点是不可能了,但题目只是要四元组的个数,并没有问每个四元组长什么样,那么我们可以考虑预处理统计一些值出来,枚举一个点尝试一下。

我们预处理出四个数组:ls[i],lg[i],rs[i],rg[i]。分别表示i左边比它小的,比它大的;i右边比它小的,比它大的个数。然后我们每次枚举左下角的点去做,再扣去算出来是三个点(一个点算重了,注意:不可能有两个点都算重)的情况,就可以了。具体的统计公式看代码。

代码

#include<map>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define pb(v) push_back(v)
#define sz() size()
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++) using namespace std; typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII; const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8; //start---------------------------------------------------------------------- const int maxn = 5e4+10;
const int mod=21092013; int n; int ls[maxn],lg[maxn],rs[maxn],rg[maxn];
int arr[maxn],arr2[maxn];
VI ha;
int sumv[maxn];
void add(int x,int v){
while(x<=n){
sumv[x]+=v;
x+=x&(-x);
}
} int sum(int x){
int ret=0;
while(x>0){
ret+=sumv[x];
x-=x&(-x);
}
return ret;
} void init(){
ha.clear();
clr(ls,0);
clr(lg,0);
clr(rs,0);
clr(rg,0);
clr(sumv,0);
} int main() {
while(scanf("%d",&n)==1&&n){
init();
rep(i,0,n){
scanf("%d",&arr[i]);
arr2[i]=arr[i];
ha.pb(arr[i]);
}
sort(arr2,arr2+n);
sort(all(ha));
ha.erase(unique(all(ha)),ha.end());
LL sums=0;
rep(i,0,n){
int id=lower_bound(all(ha),arr[i])-ha.begin()+1;
ls[i]=sum(id-1); lg[i]=sum(n)-sum(id);
int p1=lower_bound(arr2,arr2+n,arr[i])-arr2;
int p2=upper_bound(arr2,arr2+n,arr[i])-arr2;
rs[i]=p1-ls[i]; rg[i]=n-p2-lg[i];
sums+=rs[i];
add(id,1);
}
LL ans=0;
rep(i,0,n){
ans+=rg[i]*(sums-rs[i]-lg[i]);
}
rep(i,0,n){
ans-=ls[i]*(rs[i]+lg[i]);
}
printf("%lld\n",ans);
}
return 0;
} //end-----------------------------------------------------------------------