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

             1 #include<bits/stdc++.h>
 2usingnamespace std;
 3 typedef longlong ll;
 4const 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)
10void 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}
16void change(ll u,ll x) {sum[u]-=(mx[u]-x)*nmx[u],mx[u]=lz[u]=x;}
17void pd(ll u) {
18if(~lz[u]) {
19if(mx[ls]>lz[u])change(ls,lz[u]);
20if(mx[rs]>lz[u])change(rs,lz[u]);
21         lz[u]=-1;
22    }
23}
24void upd(ll L,ll R,ll x,ll u=1,ll l=1,ll r=n) {
25if(l>R||r<L||mx[u]<=x)return;
26if(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) {
30if(l>R||r<L)return ~inf;
31if(l>=L&&r<=R)return mx[u];
32    pd(u);
33return 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) {
36if(l>R||r<L)return0;
37if(l>=L&&r<=R)return sum[u];
38    pd(u);
39return qrysum(L,R,ls,l,mid)+qrysum(L,R,rs,mid+1,r);
40}
41void build(ll u=1,ll l=1,ll r=n) {
42     lz[u]=-1;
43if(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}
46int main() {
47    ll T;
48for(scanf("%lld",&T); T--;) {
49         scanf("%lld%lld",&n,&m);
50for(ll i=1; i<=n; ++i)scanf("%lld",&a[i]);
51        build();
52while(m--) {
53            ll f,l,r,x;
54             scanf("%lld%lld%lld",&f,&l,&r);
55if(f==0)scanf("%lld",&x),upd(l,r,x);
56elseif(f==1)printf("%lld\n",qrymx(l,r));
57elseif(f==2)printf("%lld\n",qrysum(l,r));
58        }
59    }
60return0;
61 }