bzoj4240 zkw版

复习一波zkw树                                                                     　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 很显然最后建出来的图不是单调序列就是一个类似凸包的玩意 所以贪心处理就好 用数据结构维护

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=300055;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int a[3*M],sum=1,n;
long long tot;
struct node{int id,h;}e[M];
bool cmp(node a,node b){return a.h>b.h;}
void add(int x){ for(x+=M;x;x>>=1) a[x]++;}
long long push_up(int l,int r){
    long long ans=0;
    for(l=l+M-1,r=r+M+1;r-l!=1;l>>=1,r>>=1){
        if(~l&1) ans+=a[l^1];
        if(r&1) ans+=a[r^1];
    }
    return ans;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) e[i].h=read(),e[i].id=i;
    sort(e+1,e+1+n,cmp);
    for(int i=1;i<=n;i++){
        if(e[i].h!=e[i-1].h) while(sum<i) add(e[sum++].id);
        long long w=push_up(1,e[i].id);
        tot+=min(w,sum-w-1);
    }
    printf("%lld
",tot);
    return 0;
}