【CH 4201】楼兰图腾【树状数组】

题目大意：

题目链接：http://contest-hunter.org:83/contest/0x40「数据结构进阶」例题/4201 楼兰图腾
求一个平面上的点能组成多少个$\bigwedge$和$\bigvee$

---

思路：

树状数组。
对于每个点，我们可以用树状数组求出以它为原点作平面直角坐标系，有多少个点在它的四个象限内。那么我们若以这个点作为$\bigvee$的最下面的点，那么能组成$\bigvee$的方法共有在第二象限的点的个数$\times$在第一象限的点得个数。
同理，$\bigwedge$就是第三象限的点得个数$\times$第四象限的点的个数。

---

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#define N 200001
using namespace std;

int n,lh[N],ll[N],rh[N],rl[N],a[N],c[N];
long long ansup,ansdown;

int ask(int x)  //询问
{
	int sum=0;
	for (;x;x-=x&(-x)) sum+=c[x];
	return sum;	
}

void add(int x)  //修改
{
	for (;x<=n;x+=x&(-x)) c[x]++;
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)  //求从左往右的每个点
	{
		scanf("%d",&a[i]);
		lh[i]=ask(a[i]-1);
		ll[i]=i-1-lh[i];
		add(a[i]);
	} 
	memset(c,0,sizeof(c));
	for (int i=n;i>=1;i--)  //求从右往左的每个点
	{
		rh[i]=ask(a[i]-1);
		rl[i]=n-i-rh[i];
		add(a[i]);
	} 
	for (int i=2;i<n;i++)
	{
		ansup+=(long long)lh[i]*rh[i];
		ansdown+=(long long)ll[i]*rl[i];
	}
	cout<<ansdown<<" "<<ansup<<endl;
	return 0;
}