首页 > 代码库 > bzoj3745: [Coci2015]Norma

bzoj3745: [Coci2015]Norma

2024-08-28 08:10:37   212人阅读

Description

技术分享

Input

第1行，一个整数N；
第2~n+1行，每行一个整数表示序列a。

Output

输出答案对10^9取模后的结果。

预处理每个位置的数作为最小/大值向左延伸的最大距离，线段树维护序列的前缀的后缀min和后缀max以及这个前缀的后缀对答案的贡献，在前缀末尾加入一个数可以快速维护。

#include<cstdio>typedef long long i64;const int N=500007,P=1000000000;char buf[N*20],*ptr=buf-1;int _(){    int x=0,c=*++ptr;    while(c<48)c=*++ptr;    while(c>47)x=x*10+c-48,c=*++ptr;    return x;}int _l,_r,_a,v1,v2,ans=0;inline int mod(int x){return x<P?x:x-P;}struct node{    node*l,*r;    int f1,f2,sz,L,R;    int s1,s2,s3,ss1,ss2,ss3;    void fil1(int x){        f1=x;        s1=i64(x)*sz%P;        ss1=(i64(sz)*(sz+1)>>1)%P*x%P;        s3=i64(x)*s2%P;        ss3=i64(x)*ss2%P;    }    void fil2(int x){        f2=x;        s2=i64(x)*sz%P;        ss2=(i64(sz)*(sz+1)>>1)%P*x%P;        s3=i64(x)*s1%P;        ss3=i64(x)*ss1%P;    }    void dn(){        if(f1)l->fil1(f1),r->fil1(f1),f1=0;        if(f2)l->fil2(f2),r->fil2(f2),f2=0;    }    void up(){        s1=mod(l->s1+r->s1);        s2=mod(l->s2+r->s2);        s3=mod(l->s3+r->s3);        ss1=(l->ss1+r->ss1+i64(l->s1)*r->sz)%P;        ss2=(l->ss2+r->ss2+i64(l->s2)*r->sz)%P;        ss3=(l->ss3+r->ss3+i64(l->s3)*r->sz)%P;    }    void set1(){        if(_l<=L&&R<=_r){            fil1(_a);            return;        }        dn();        int M=L+R>>1;        if(_l<=M)l->set1();        if(_r>M)r->set1();        up();    }    void set2(){        if(_l<=L&&R<=_r){            fil2(_a);            return;        }        dn();        int M=L+R>>1;        if(_l<=M)l->set2();        if(_r>M)r->set2();        up();    }    void get(){        if(R<=_r){            v2=(v2+ss3+i64(v1)*sz)%P;            v1=mod(v1+s3);            return;        }        dn();        int M=L+R>>1;        l->get();        if(_r>M)r->get();    }}ns[N*2],*np=ns,*rt;node*build(int L,int R){    node*w=np++;    w->L=L;w->R=R;    w->sz=R-L+1;    if(L!=R){        int M=L+R>>1;        w->l=build(L,M);        w->r=build(M+1,R);    }    return w;}int n,a[N],p1[N],p2[N],ss[N],sp=0;int main(){    fread(buf,1,sizeof(buf),stdin);    n=_();    for(int i=1;i<=n;++i)a[i]=_();    for(int i=n;i;--i){        while(sp&&a[ss[sp]]>a[i])p1[ss[sp--]]=i+1;        ss[++sp]=i;    }    while(sp)p1[ss[sp--]]=1;    for(int i=n;i;--i){        while(sp&&a[ss[sp]]<a[i])p2[ss[sp--]]=i+1;        ss[++sp]=i;    }    while(sp)p2[ss[sp--]]=1;    rt=build(1,n);    for(int i=1;i<=n;++i){        _l=p1[i];_r=i;_a=a[i];        rt->set1();        _l=p2[i];        rt->set2();        v1=v2=0;        rt->get();        ans=mod(ans+v2);    }    printf("%d",ans);    return 0;}

 

bzoj3745: [Coci2015]Norma


联系
我们