【树状数组】【P3608】平衡的照片

Description

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计算不平衡的奶牛数量。

Input

第一行一个整数N。接下N行包括H[1]到H[n]，每行一个非负整数（不大于1,000，000，000)。

Output

请输出不平衡的奶牛数量。

Sample Input

Sample Output

Solution

考虑n²暴力做法显然是枚举每头牛，然后向左右枚举进行计数。

但是显然TLE。考虑优化。由于题目中要求求出比第i头牛大的牛，而事实上比第i头牛矮的牛是否处理是不影响i的答案的，于是我们发现了无后效性。

考虑排序后以身高降序作为阶段，这样每次处理时求出坐标在i左边和在i右边的比i高的牛的个数。由于以这些牛已经被计算过了，所以事实上我们需要求的就是i两侧已经被处理过的牛的个数。在每次查询完毕后，我们将当前牛标记为被处理过。记处理过为1，为处理过为0。那么显然这是一个单点修改，区间查询的数据结构问题。树状数组可破。

Code

#include<cstdio>
#include<algorithm>
#define maxn 100010
#define ci const int

inline void qr(int &x) {
    char ch=getchar(),lst=NULL;
    while(ch>'9'||ch<'0') lst=ch,ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(lst=='-') x=-x;
}

template <typename T>
inline T mmax(const T &a,const T &b) {if(a>b) return a;return b;}
template <typename T>
inline T mmin(const T &a,const T &b) {if(a<b) return a;return b;}
template <typename T>
inline T mabs(const T &a) {if(a>=0) return a;return -a;}

template <typename T>
inline void mswap(T &a,T &b) {T temp=a;a=b;b=temp;}

struct M {
    int num,v;
};
M MU[maxn];
inline bool cmp (const M &a,const M &b) {return a.v>b.v;}

int n,cnt;
int tree[maxn];
inline int lowbit(ci x) {return x&(-x);}

int ask(register int);
void add(register int);

int main() {
    qr(n);
    for(register int i=1;i<=n;++i) {qr(MU[i].v);MU[i].num=i;}
    std::sort(MU+1,MU+1+n,cmp);
    for(register int i=1;i<=n;++i) {
        int a=ask(MU[i].num),b=i-a-1;
        if(a<b) mswap(a,b);
        if(b*2<a) ++cnt;
        add(MU[i].num);
    }
    printf("%d
",cnt);
    return 0;
}

int ask(register int x) {
    register int ans=0;
    while(x>0) {
        ans+=tree[x];x-=lowbit(x);
    }
    return ans;
}

void add(register int x) {
    while(x<=n) {
        ++tree[x];
        x+=lowbit(x);
    }
}

Summary

register大法好，从此加入register邪教