题目大意
FJ正在安排他的N头奶牛站成一排来拍照。（1<=N<=100,000)序列中的第i头奶牛的高度是h[i]，且序列中所有的奶牛的身高都不同。
就像他的所有牛的照片一样，FJ希望这张照片看上去尽可能好。他认为，如果L[i]和R[i]的数目相差2倍以上的话，第i头奶牛就是不平衡的。（L[i]和R[i]分别代表第i头奶牛左右两边比她高的数量）。
如果L[i]和R[i]中较大者比较小者的数量严格多两倍的话，这头奶牛也是不平衡的。FJ不希望他有太多的奶牛不平衡。
请帮助FJ计算不平衡的奶牛数量。
题目分析
显然，一上来我们有一个对于每个数都扫一遍的 O(N2) 做法，考虑如何优化。
我们自然想到不能简单地按照原序列直接处理，所以先我们先将所有的数据从大到小去排列，其中第k大的数在原本的奶牛序列中的序号为i,
一个 f[i] 数组来表示现在第i大的数有无被进行以下的处理过，若已进行，则为1，否则为0。
然后我们按原本的数组顺序来枚举奶牛，处理完后，这头奶牛所对应的 f[i] 就置为1，这样就能够保证当前 f[i] 为1的奶牛在原序列中一定在 f[i] 为0的奶牛的左边，
所以当前奶牛 i 左边比他高的奶牛都已经处理过了，而数量就是 f[1]~f[i-1]中1的数量（比他大还比他前），然后可以通过减法得出 i 右边比他高的牛的数量。
那么这其实就是一个单点修改+区间查询，用树状数组来维护 f数组 即可。
1 #include
2 using namespace std;
3 const int MAXN=2e5+10;
4
5 struct Node{
6 int h,id;
7 }a[MAXN];
8 inline bool cmp(Node x,Node y){
9 return x.h>y.h;
10 }
11
12 int n,l,r,ans;
13 int b[MAXN],BIT[MAXN];
14 inline int lowbit(int x){
15 return x&(-x);
16 }
17 inline void Update(int x,int v){
18 for(int i=x;i<=n;i+=lowbit(i))
19 BIT[i]+=v;
20 }
21 inline int Query(int x){
22 int res=0;
23 for(int i=x;i;i-=lowbit(i))
24 res+=BIT[i];
25 return res;
26 }
27 int main(){
28 scanf("%d",&n);
29 for(int i=1;i<=n;++i){
30 scanf("%d",&a[i].h);
31 a[i].id=i;
32 }
33 sort(a+1,a+n+1,cmp);
34 for(int i=1;i<=n;++i)
35 b[a[i].id]=i;
36 for(int i=1;i<=n;++i){
37 l=Query(b[i]);
38 r=b[i]-l-1;
39 if(l*2 40 Update(b[i],1); 41 } 42 printf("%d\n",ans); 43 return 0; 44 }
