HDU - 5306 Gorgeous Sequence (吉司机线段树)

傷城~ 2021-11-27 06:31 204阅读 0赞

[题目链接][Link 1]

吉司机线段树裸题...

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 const ll N=1e6+10,inf=0x3f3f3f3f3f3f3f3f;
     5 ll n,m,a[N],mx[N<<2],se[N<<2],nmx[N<<2],lz[N<<2];
     6 ll sum[N<<2];
     7 #define ls (u<<1)
     8 #define rs (u<<1|1)
     9 #define mid ((l+r)>>1)
    10 void pu(ll u) {
    11     sum[u]=sum[ls]+sum[rs];
    12     mx[u]=max(mx[ls],mx[rs]),se[u]=min(mx[ls],mx[rs]);
    13     se[u]=se[u]==mx[u]?max(se[ls],se[rs]):max(se[u],max(se[ls],se[rs]));
    14     nmx[u]=(mx[ls]==mx[u]?nmx[ls]:0)+(mx[rs]==mx[u]?nmx[rs]:0);
    15 }
    16 void change(ll u,ll x) {sum[u]-=(mx[u]-x)*nmx[u],mx[u]=lz[u]=x;}
    17 void pd(ll u) {
    18     if(~lz[u]) {
    19         if(mx[ls]>lz[u])change(ls,lz[u]);
    20         if(mx[rs]>lz[u])change(rs,lz[u]);
    21         lz[u]=-1;
    22     }
    23 }
    24 void upd(ll L,ll R,ll x,ll u=1,ll l=1,ll r=n) {
    25     if(l>R||r<L||mx[u]<=x)return;
    26     if(l>=L&&r<=R&&se[u]<x) {change(u,x); return;}
    27     pd(u),upd(L,R,x,ls,l,mid),upd(L,R,x,rs,mid+1,r),pu(u);
    28 }
    29 ll qrymx(ll L,ll R,ll u=1,ll l=1,ll r=n) {
    30     if(l>R||r<L)return ~inf;
    31     if(l>=L&&r<=R)return mx[u];
    32     pd(u);
    33     return max(qrymx(L,R,ls,l,mid),qrymx(L,R,rs,mid+1,r));
    34 }
    35 ll qrysum(ll L,ll R,ll u=1,ll l=1,ll r=n) {
    36     if(l>R||r<L)return 0;
    37     if(l>=L&&r<=R)return sum[u];
    38     pd(u);
    39     return qrysum(L,R,ls,l,mid)+qrysum(L,R,rs,mid+1,r);
    40 }
    41 void build(ll u=1,ll l=1,ll r=n) {
    42     lz[u]=-1;
    43     if(l==r) {sum[u]=mx[u]=a[l],se[u]=~inf,nmx[u]=1; return;}
    44     build(ls,l,mid),build(rs,mid+1,r),pu(u);
    45 }
    46 int main() {
    47     ll T;
    48     for(scanf("%lld",&T); T--;) {
    49         scanf("%lld%lld",&n,&m);
    50         for(ll i=1; i<=n; ++i)scanf("%lld",&a[i]);
    51         build();
    52         while(m--) {
    53             ll f,l,r,x;
    54             scanf("%lld%lld%lld",&f,&l,&r);
    55             if(f==0)scanf("%lld",&x),upd(l,r,x);
    56             else if(f==1)printf("%lld\n",qrymx(l,r));
    57             else if(f==2)printf("%lld\n",qrysum(l,r));
    58         }
    59     }
    60     return 0;
    61 }

转载于:https://www.cnblogs.com/asdfsag/p/10776040.html

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=5306