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

题目链接

吉司机线段树裸题...

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const ll N=1e6+,inf=0x3f3f3f3f3f3f3f3f;

 ll n,m,a[N],mx[N<<],se[N<<],nmx[N<<],lz[N<<];

 ll sum[N<<];

 #define ls (u<<1)

 #define rs (u<<1|1)

 #define mid ((l+r)>>1)

 void pu(ll u) {

     sum[u]=sum[ls]+sum[rs];

     mx[u]=max(mx[ls],mx[rs]),se[u]=min(mx[ls],mx[rs]);

     se[u]=se[u]==mx[u]?max(se[ls],se[rs]):max(se[u],max(se[ls],se[rs]));

     nmx[u]=(mx[ls]==mx[u]?nmx[ls]:)+(mx[rs]==mx[u]?nmx[rs]:);

 }

 void change(ll u,ll x) {sum[u]-=(mx[u]-x)*nmx[u],mx[u]=lz[u]=x;}

 void pd(ll u) {

     if(~lz[u]) {

         if(mx[ls]>lz[u])change(ls,lz[u]);

         if(mx[rs]>lz[u])change(rs,lz[u]);

         lz[u]=-;

     }

 }

 void upd(ll L,ll R,ll x,ll u=,ll l=,ll r=n) {

     if(l>R||r<L||mx[u]<=x)return;

     if(l>=L&&r<=R&&se[u]<x) {change(u,x); return;}

     pd(u),upd(L,R,x,ls,l,mid),upd(L,R,x,rs,mid+,r),pu(u);

 }

 ll qrymx(ll L,ll R,ll u=,ll l=,ll r=n) {

     if(l>R||r<L)return ~inf;

     if(l>=L&&r<=R)return mx[u];

     pd(u);

     return max(qrymx(L,R,ls,l,mid),qrymx(L,R,rs,mid+,r));

 }

 ll qrysum(ll L,ll R,ll u=,ll l=,ll r=n) {

     if(l>R||r<L)return ;

     if(l>=L&&r<=R)return sum[u];

     pd(u);

     return qrysum(L,R,ls,l,mid)+qrysum(L,R,rs,mid+,r);

 }

 void build(ll u=,ll l=,ll r=n) {

     lz[u]=-;

     if(l==r) {sum[u]=mx[u]=a[l],se[u]=~inf,nmx[u]=; return;}

     build(ls,l,mid),build(rs,mid+,r),pu(u);

 }

 int main() {

     ll T;

     for(scanf("%lld",&T); T--;) {

         scanf("%lld%lld",&n,&m);

         for(ll i=; i<=n; ++i)scanf("%lld",&a[i]);

         build();

         while(m--) {

             ll f,l,r,x;

             scanf("%lld%lld%lld",&f,&l,&r);

             if(f==)scanf("%lld",&x),upd(l,r,x);

             else if(f==)printf("%lld\n",qrymx(l,r));

             else if(f==)printf("%lld\n",qrysum(l,r));

         }

     }

     return ;

 }