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

本文主要是介绍【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;
}

这篇关于【CH 4201】楼兰图腾【树状数组】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---