HDOJ 2492 Ping Pong 树状数组维护信息

自己开了一个线段树和树状数组的专题还是有用的，自己第一次独立搞出来了这种类型的题

题意：n个人，每个人有一个排名，我们需要找到的是对于i<j<k的，ai<aj<ak或者ai>aj>ak的所有可能情况，n的范围到2e4

首先对排名，我有一个疑问是：题中的rank是1到n的一个排列吗？如果是，那么为什么rank的值会到1e5呢？

不懂，所以按照POJ 1990 MooFest  的搞法，首先离散处理一发，那么先处理成了一个1到n的排列了

有了这个，就好搞了啊！

因为，getsum（a【i】）就是第i个数左边的比a【i】小的数有多少个

然后，我们需要根据这个值来推出，令：

l1=第i个数左边的比a【i】小的数有多少个

l2=第i个数左边的比a【i】大的数有多少个

r1=第i个数右边的比a【i】小的数有多少个

r2=第i个数右边的比a【i】大的数有多少个

那么对于第i个数，这个人作为裁判的情况呢：就是l1*r2+l2*r1

l1是根据树状数组维护来维护的，getsum（a【i】）

l2可以根据l1来求，因为左边总共的数有i-1个，因为经过了离散化，其他每个数不是比a【i】大就是比a【i】小，那么l2=i-1-l1

r1也可以根据l1来求，因为比a【i】小的数，总共有a【i】-1个，要么在左边，要么在右边，所以r1=a【i】-1-l1

r2可以根据l2来求，比a【i】大的数，总共有n-a【i】个，要么在左边，要么在右边，所以r2=n-a【i】-l2

所以，分析到这儿，代码如下：

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+50;
int n,t;
int c[maxn],a[maxn];

struct node{
	int v,order;
}in[maxn];

int lowbit(int x){
	return x&(-x);
}

void addnum(int x,int add){
	while(x<=n){
		c[x]+=add;
		x+=lowbit(x);
	}
}

int getsum(int x){
	int ret=0;
	while(x){
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}

int cmp(node a,node b){
	return a.v<b.v;
}

int main(){
	//freopen("input.txt","r",stdin);
	__int64 ans;
	scanf("%d",&t);
	while(t--){
		memset(c,0,sizeof(c));
		ans=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&in[i].v);
			in[i].order=i;
		}
		sort(in+1,in+n+1,cmp);
		for(int i=1;i<=n;i++) a[in[i].order]=i;
		for(int i=1;i<=n;i++){
			int l1=getsum(a[i]);
			int l2=i-1-l1;
			int r1=a[i]-1-l1;
			int r2=n-a[i]-l2;
			ans+=(long long)l1*r2+(long long)l2*r1;
			addnum(a[i],1);
		}
		printf("%I64d\n",ans);
	}
	return 0;
}