Range Chmin Chmax Add Range Sum

maxminaddsum.cpp

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int LG=32-__builtin_clz(200000-1);
constexpr ll MX=4e18;

int N, M, Q, t, l, r; ll x;
struct node {
	ll sum, lz, mx, mx2, mn, mn2; int mxc, mnc;
	inline void input() { cin>>sum; mx=mn=sum; }
	inline node operator+(const node& rhs) const {
		node n;
		n.sum=sum+rhs.sum;
		n.lz=0;
		n.mx2=max(mx2, rhs.mx2);
		if(mx<rhs.mx) {
			n.mx=rhs.mx, n.mxc=rhs.mxc;
			n.mx2=max(n.mx2, mx);
		} else {
			n.mx=mx, n.mxc=mxc;
			if(mx==rhs.mx) n.mxc+=rhs.mxc;
			else n.mx2=max(n.mx2, rhs.mx);
		}
		n.mn2=min(mn2, rhs.mn2);
		if(mn>rhs.mn) {
			n.mn=rhs.mn, n.mnc=rhs.mnc;
			n.mn2=min(n.mn2, mn);
		} else {
			n.mn=mn, n.mnc=mnc;
			if(mn==rhs.mn) n.mnc+=rhs.mnc;
			else n.mn2=min(n.mn2, rhs.mn);
		}
		return n;
	}
	inline void chmx(ll m) {
		sum+=(m-mx)*mxc;
		mn=mn==mx ? m : mn;
		mn2=mn2==mx ? m : mn2;
		mx=m;
	}
	inline void chmn(ll m) {
		sum+=(m-mn)*mnc;
		mx=mx==mn ? m : mx;
		mx2=mx2==mn ? m : mx2;
		mn=m;
	}
	inline void down(const node& rhs, int d) {
		if(ll z=rhs.lz) sum+=z<<d, lz+=z, mx+=z, mx2+=z, mn+=z, mn2+=z;
		if(mx>rhs.mx) chmx(rhs.mx);
		if(mn<rhs.mn) chmn(rhs.mn);
	}
	inline bool apply(int d) {
		if(t==3) { x+=sum; return true; }
		if(t==2) { sum+=x<<d, lz+=x, mx+=x, mx2+=x, mn+=x, mn2+=x; return true; }
		if(t==0) {
			if(x>=mx) return true;
			if(x>mx2) { chmx(x); return true; }
		} else if(t==1) {
			if(x<=mn) return true;
			if(x<mn2) { chmn(x); return true; }
		}
		return false;
	}
};

vector<node> A(1<<LG+1, {0, 0, -MX, -MX, MX, MX, 1, 1});
void build() {
	for(int i=0; i<N; i++) A[1<<LG|i].input();
	for(int i=1<<LG; --i;) A[i]=A[i*2]+A[i*2+1];
}
void qry(int d=LG, int s=0, int i=1) {
	if(l<=s && s+(1<<d)<=r && A[i].apply(d)) return;
	int m=s|1<<--d;
	A[i*2].down(A[i], d);
	A[i*2+1].down(A[i], d);
	if(l<m) qry(d, s, i*2);
	if(r>m) qry(d, m, i*2+1);
	A[i]=A[i*2]+A[i*2+1];
}

int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>N>>Q;
	build();
	while(Q--) {
		cin>>t>>l>>r; x=0;
		if(t!=3) cin>>x;
		qry();
		if(t==3) cout<<x<<'\n';
	}
}

https://judge.yosupo.jp/submission/15043

• Time: 417 ms
• Memory: 29.66 MiB