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


题意: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;
}