hdu 5792 World is Exploding 2016 Multi-University 5

Problem：acm.hdu.edu.cn/showproblem.php?pid=5792

题意：给一个序列 V，问有多少个由下标组成的四元组（a，b，c，d），满足：a != b != c != d，a < b，c < d， Va < Vb，Vc > Vd

分析：可以考虑先把所有顺序数对的个数、逆序数对的个数找出来相乘，然后再去掉不符合下标大小关系的

数据范围是 [ 0，1e9 ]，不能直接开这么大的树状数组统计，但是在求顺序数对、逆序数对时，只需要用到元素间的相对大小关系这一个性质，可以把原序列的数改成小的，并保持它们之间的相对大小的关系，不影响答案，而元素个数最多 5万 个，改值后最大不超过50000，就可以用树状数组

可以用一个结构体数组记每一个元素的值、下标，然后升序排序，从小到大把值改成1、2、3…这些，并通过记录的下标把原数列记录的值也改了

先算好4个数组：

ls[ ]：ls[i] 表示 i 左边比 Vi 小的数的个数（left smaller）

lg[ ]：lg[i] 表示 i 左边比 Vi 大的数的个数（left greater）

rs[ ]：……（right smaller）

rg[ ]：……（right greater）

去重的问题：前面说的直接相乘会有多算，情况有：a = c，a = d，b = c，b = d 这4种

a = c 时，b与d同在右侧，但一个比Va小，一个比它大，故 b != d。ans -= rs[ i ] * rg[ i ] （0 <= i < n）

a = d 时，b与c不同侧，ans -= lg[ i ] * rg[ i ]

b = c 时，a与d不同侧，ans -= ls[ i ] * rs[ i ]

b = d 时，a于c同在左侧，一个比Vb小，一个比它大，故a != c。ans -= ls[ i ] * lg[ i ]

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 50000

typedef struct
{
	int v; // 原值
	int id; // 在原数组中的下标
	int nw; // 新值
}node;

node tmp[N]; // 用来排序、改值，并且修改in[]中的值
int bit[N+1]；// 树状数组
int in[N]; // 输入的数组
int lg[N],rg[N],ls[N],rs[N];

int cmp(const void *a, const void *b)
{
	node *c = a,*d = b;
	return c->v - d->v;
}

int sum(int x)
{
	int ans;
	for(ans=0; x>0; x-=x&-x)
	  ans += bit[x];
	return ans;
}

void add(int p,int top)
{
	for(;p<=top; p+=p&-p)
	  bit[p]++;
}

int main()
{
	int n,big;
	long long ans;
	long long prels,prers; // ls[]和rs[]的前缀和
	while( ~scanf("%d",&n) )
	{
		int i;
		for(i=0; i<n; i++)
		{
			scanf("%d",in + i);
			tmp[i].v = in[i];
			tmp[i].id = i;
		}
		qsort(tmp, n, sizeof( node ), cmp);
		for(in[ tmp[0].id ] = tmp[0].nw = 1,i=1; i<n; i++) // 最小元素的新值赋1
		  if(tmp[i].v == tmp[i-1].v) // 原值跟前面相等则新值也赋相等的值
		  	in[ tmp[i].id ] = tmp[i].nw = tmp[i-1].nw;
		  else // 否则就是前面的新值+1
		  	in[ tmp[i].id ] = tmp[i].nw = tmp[i-1].nw + 1;
		big = tmp[n-1].nw; // 改值后用到的最大的值
		// 算ls[]和lg[]
		memset(bit,0,sizeof(bit));
		for(i = prels = 0; i<n; i++)
		{
			ls[i] = sum( in[i]-1 );
			lg[i] = sum( big ) - sum( in[i] );
			prels += ls[i];
			add(in[i], big);
		}
		// 算rs[]和rg[]
		memset(bit,0,sizeof(bit));
		for(i=n-1, prers=0; ~i; i--)
		{
			rs[i] = sum( in[i]-1 );
			rg[i] = sum( big ) - sum( in[i] );
			prers += rs[i];
			add(in[i], big);
		}
		// 去重
		for(ans = prels * prers, i=0; i<n; i++)
		{
			ans -= (long long) rs[i] * rg[i]; // a = c
			ans -= (long long) lg[i] * rg[i]; // a = d
			ans -= (long long) ls[i] * rs[i]; // b = c
			ans -= (long long) ls[i] * lg[i]; // b = d
		}
		printf("%I64d\n",ans);
	}
	return 0;
}