cogs1533 [HNOI2002]营业额统计

啦啦啦啦

不维护区间的平衡树题都是树状数组+二分练手题！

不会的参考我的普通平衡树的多种神奇解法之BIT+二分答案

和上一篇博文完全一样2333

另外：goto语句只要不乱用还是挺好用的

// It is made by XZZ

#include<cstdio>

#include<algorithm>

using namespace std;

#define rep(a,b,c) for(rg int a=b;a<=c;a++)

#define drep(a,b,c) for(rg int a=b;a>=c;a--)

#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])

#define il inline

#define rg register

#define vd void

typedef long long ll;

const int maxn=(1<<15)+4;

int n;

//BIT begin

int t[maxn],tot;

#define lb(o) (o&-o)

il vd Appear(int p){++p;while(p<=tot)++t[p],p+=lb(p);}

il vd Disappear(int p){++p;while(p<=tot)--t[p],p+=lb(p);}

il int Query(int p){int ret=0;while(p)ret+=t[p],p-=lb(p);return ret;}

//BIT end.

il int pre(int p){

    int mid,l=1,r=p-1,k=Query(p);

    while(l<r){

        mid=(l+r)>>1;

        if(Query(mid+1)==k)r=mid;

        else l=mid+1;

    }return l;

}

il int nxt(int p){

    int mid,l=p+1,r=tot,k=Query(p+1);

    while(l<r){

        mid=(l+r)>>1;

        if(Query(mid+1)^k)r=mid;

        else l=mid+1;

    }return l;

}

int s[maxn];ll data[maxn];

bool yes[maxn];

int main(){

    scanf("%d",&n);

    rep(i,1,n){

        if(scanf("%d",&s[i])^1)s[i]=0;

        data[i]=s[i];

    }

    sort(data+1,data+n+1);

    tot=unique(data+1,data+n+1)-data-1;

    rep(i,1,n)s[i]=lower_bound(data+1,data+tot+1,s[i])-data;

    ll ans=data[s[1]];

    data[0]=-1e14;

    ++tot;

    Appear(s[1]);yes[s[1]]=1;

    rep(i,2,n){

        static int a,b;

        a=b=0;

        if(yes[s[i]])goto end;

        yes[s[i]]=1;

        if(Query(s[i]))a=pre(s[i]);

        if(Query(s[i])^(i-1))b=nxt(s[i]);

        ans+=min(abs(data[a]-data[s[i]]),abs(data[b]-data[s[i]]));

        end:Appear(s[i]);

    }

    printf("%lld\n",ans);

    return 0;

}

巴特西

cogs1533 [HNOI2002]营业额统计

cogs1533 [HNOI2002]营业额统计

啦啦啦啦

最新文章

热门文章