题目链接：

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-----------------------------------------------------------------------

巴特西

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

题目链接：

World is Exploding

输出

样例

题解

代码

最新文章

热门文章