2 条题解
-
0
#include <bits/stdc++.h> #define il inline #define ui unsigned int #define ll long long #define ull unsigned ll #define lll __int128 #define db double #define ldb long double #define pii pair<int, int> #define vi vector<int> #define vpii vector<pii> #define fir first #define sec second #define gc getchar #define pc putchar #define mst(a, x) memset(a, x, sizeof a) #define pb push_back #define lb lower_bound #define ub upper_bound #define pct __builtin_popcount using namespace std; const int N = 5e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7; const ll INFll = 0x3f3f3f3f3f3f3f3f; il int rd() { int x = 0, f = 1; char ch = gc(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = gc(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = gc(); } return x * f; } il ll rdll() { ll x = 0; int f = 1; char ch = gc(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = gc(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = gc(); } return x * f; } il void wr(int x) { if (x < -2147483647) { printf("-2147483648"); return; } if (x < 0) { pc('-'), wr(-x); return; } if (x < 10) { pc(x + '0'); return; } wr(x / 10), pc(x % 10 + '0'); } il void wrll(ll x) { if (x < -9223372036854775807) return (void)printf("-9223372036854775808"); if (x < 0) return pc('-'), wrll(-x); if (x < 10) return (void)pc(x + '0'); wrll(x / 10), pc(x % 10 + '0'); } il void wr(int x, char *s) { wr(x), printf("%s", s); } il void wrll(ll x, char *s) { wrll(x), printf("%s", s); } il int vmod(int x) { return x >= MOD ? x - MOD : x; } il int vadd(int x, int y) { return vmod(x + y); } il int vsub(int x, int y) { return vmod(x - y + MOD); } il int vmul(int x, int y) { return 1LL * x * y % MOD; } int n, m, a[N]; struct SGT { #define ls (id << 1) #define rs (id << 1 | 1) #define mid (l + r >> 1) #define smt(id) tr[id].smt #define mx(id) tr[id].mx #define mxc(id) tr[id].mxc #define mxs(id) tr[id].mxs #define mxt(id) tr[id].mxt #define mn(id) tr[id].mn #define mnc(id) tr[id].mnc #define mns(id) tr[id].mns #define mnt(id) tr[id].mnt #define sm(id) tr[id].sm struct nd { int smt, mx, mxc, mxs, mxt, mn, mnc, mns, mnt; ll sm; } tr[N << 2]; void pu(int id) { sm(id) = sm(ls) + sm(rs); if (mx(ls) > mx(rs)) { mx(id) = mx(ls); mxc(id) = mxc(ls); mxs(id) = max(mxs(ls), mx(rs)); } else if (mx(ls) < mx(rs)) { mx(id) = mx(rs); mxc(id) = mxc(rs); mxs(id) = max(mx(ls), mxs(rs)); } else { mx(id) = mx(ls); mxc(id) = mxc(ls) + mxc(rs); mxs(id) = max(mxs(ls), mxs(rs)); } if (mn(ls) < mn(rs)) { mn(id) = mn(ls); mnc(id) = mnc(ls); mns(id) = min(mns(ls), mn(rs)); } else if (mn(ls) > mn(rs)) { mn(id) = mn(rs); mnc(id) = mnc(rs); mns(id) = min(mn(ls), mns(rs)); } else { mn(id) = mn(ls); mnc(id) = mnc(ls) + mnc(rs); mns(id) = min(mns(ls), mns(rs)); } } void ad(int &x, int k) { if (x != INF && x != -INF) x += k; } void apd(int id, int len, int k) { sm(id) += 1LL * len * k; ad(mx(id), k); ad(mxs(id), k); ad(mxt(id), k); ad(mn(id), k); ad(mns(id), k); ad(mnt(id), k); ad(smt(id), k); } void mxpd(int id, int k) { if (mn(id) > k) return; sm(id) += 1LL * (k - mn(id)) * mnc(id); mxt(id) = k; if (mn(id) == mx(id)) mx(id) = k; if (mn(id) == mxs(id)) mxs(id) = k; mnt(id) = max(mnt(id), k); mn(id) = k; } void mnpd(int id, int k) { if (mx(id) < k) return; sm(id) += 1LL * (k - mx(id)) * mxc(id); mnt(id) = k; if (mx(id) == mn(id)) mn(id) = k; if (mx(id) == mns(id)) mns(id) = k; mxt(id) = min(mxt(id), k); mx(id) = k; } void pd(int id, int l, int r) { if (smt(id)) { apd(ls, mid - l + 1, smt(id)); apd(rs, r - mid, smt(id)); } if (mxt(id) != -INF) { mxpd(ls, mxt(id)); mxpd(rs, mxt(id)); } if (mnt(id) != INF) { mnpd(ls, mnt(id)); mnpd(rs, mnt(id)); } smt(id) = 0; mxt(id) = -INF; mnt(id) = INF; } void bld(int id, int l, int r) { if (l == r) { return tr[id] = {0, a[l], 1, -INF, -INF, a[l], 1, INF, INF, a[l]}, void(); } bld(ls, l, mid); bld(rs, mid + 1, r); pu(id); mxt(id) = -INF; mnt(id) = INF; } void aupd(int id, int l, int r, int L, int R, int k) { if (L <= l && r <= R) return apd(id, r - l + 1, k); pd(id, l, r); if (L <= mid) aupd(ls, l, mid, L, R, k); if (R > mid) aupd(rs, mid + 1, r, L, R, k); pu(id); } void mxupd(int id, int l, int r, int L, int R, int k) { if (mn(id) >= k) return; if (L <= l && r <= R && mns(id) > k) return mxpd(id, k); if (l == r) return; pd(id, l, r); if (L <= mid) mxupd(ls, l, mid, L, R, k);; if (R > mid) mxupd(rs, mid + 1, r, L, R, k); pu(id); } void mnupd(int id, int l, int r, int L, int R, int k) { if (mx(id) <= k) return; if (L <= l && r <= R && mxs(id) < k) return mnpd(id, k); if (l == r) return; pd(id, l, r); if (L <= mid) mnupd(ls, l, mid, L, R, k); if (R > mid) mnupd(rs, mid + 1, r, L, R, k); pu(id); } ll sqry(int id, int l, int r, int L, int R) { if (L <= l && r <= R) return sm(id); pd(id, l, r); ll res = 0; if (L <= mid) res += sqry(ls, l, mid, L, R); if (R > mid) res += sqry(rs, mid + 1, r, L, R); return res; } int mxqry(int id, int l, int r, int L, int R) { if (L <= l && r <= R) return mx(id); pd(id, l, r); int res = -INF; if (L <= mid) res = max(res, mxqry(ls, l, mid, L, R)); if (R > mid) res = max(res, mxqry(rs, mid + 1, r, L, R)); return res; } int mnqry(int id, int l, int r, int L, int R) { if (L <= l && r <= R) return mn(id); pd(id, l, r); int res = INF; if (L <= mid) res = min(res, mnqry(ls, l, mid, L, R)); if (R > mid) res = min(res, mnqry(rs, mid + 1, r, L, R)); return res; } } T; void QwQ() { n = rd(); for (int i = 1; i <= n; i++) a[i] = rd(); m = rd(); T.bld(1, 1, n); for (int op, l, r; m--;) { op = rd(), l = rd(), r = rd(); if (op == 1) T.aupd(1, 1, n, l, r, rd()); else if (op == 2) T.mxupd(1, 1, n, l, r, rd()); else if (op == 3) T.mnupd(1, 1, n, l, r, rd()); else if (op == 4) wrll(T.sqry(1, 1, n, l, r), "\n"); else if (op == 5) wr(T.mxqry(1, 1, n, l, r), "\n"); else wr(T.mnqry(1, 1, n, l, r), "\n"); } } signed main() { int T = 1; while (T--) QwQ(); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:11:01
#include<bits/stdc++.h> #define il inline #define ui unsigned int #define ll long long #define ull unsigned ll #define lll __int128 #define db double #define ldb long double #define pii pair<int,int> #define vi vector<int> #define vpii vector<pii> #define fir first #define sec second #define gc getchar #define pc putchar #define mst(a,x) memset(a,x,sizeof a) #define pb push_back #define lb lower_bound #define ub upper_bound #define pct __builtin_popcount using namespace std; const int N=5e5+10,INF=0x3f3f3f3f,MOD=1e9+7; const ll INFll=0x3f3f3f3f3f3f3f3f; il int rd() {int x=0,f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;} il ll rdll() {ll x=0; int f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;} il void wr(int x) {if(x<-2147483647) {printf("-2147483648"); return;} if(x<0) {pc('-'),wr(-x); return;} if(x<10) {pc(x+'0'); return;} wr(x/10),pc(x%10+'0');} il void wrll(ll x) {if(x<-9223372036854775807) return (void)printf("-9223372036854775808"); if(x<0) return pc('-'),wrll(-x); if(x<10) return (void)pc(x+'0'); wrll(x/10),pc(x%10+'0');} il void wr(int x,char *s) {wr(x),printf("%s",s);} il void wrll(ll x,char *s) {wrll(x),printf("%s",s);} il int vmod(int x) {return x>=MOD?x-MOD:x;} il int vadd(int x,int y) {return vmod(x+y);} il int vsub(int x,int y) {return vmod(x-y+MOD);} il int vmul(int x,int y) {return 1ll*x*y%MOD;} int n,m,a[N]; struct SGT { #define ls (id<<1) #define rs (id<<1|1) #define mid (l+r>>1) #define smt(id) tr[id].smt #define mx(id) tr[id].mx #define mxc(id) tr[id].mxc #define mxs(id) tr[id].mxs #define mxt(id) tr[id].mxt #define mn(id) tr[id].mn #define mnc(id) tr[id].mnc #define mns(id) tr[id].mns #define mnt(id) tr[id].mnt #define sm(id) tr[id].sm struct nd {int smt,mx,mxc,mxs,mxt,mn,mnc,mns,mnt; ll sm;} tr[N<<2]; void pu(int id) { sm(id)=sm(ls)+sm(rs); if(mx(ls)>mx(rs)) mx(id)=mx(ls),mxc(id)=mxc(ls),mxs(id)=max(mxs(ls),mx(rs)); else if(mx(ls)<mx(rs)) mx(id)=mx(rs),mxc(id)=mxc(rs),mxs(id)=max(mx(ls),mxs(rs)); else mx(id)=mx(ls),mxc(id)=mxc(ls)+mxc(rs),mxs(id)=max(mxs(ls),mxs(rs)); if(mn(ls)<mn(rs)) mn(id)=mn(ls),mnc(id)=mnc(ls),mns(id)=min(mns(ls),mn(rs)); else if(mn(ls)>mn(rs)) mn(id)=mn(rs),mnc(id)=mnc(rs),mns(id)=min(mn(ls),mns(rs)); else mn(id)=mn(ls),mnc(id)=mnc(ls)+mnc(rs),mns(id)=min(mns(ls),mns(rs)); } void ad(int &x,int k) {x!=INF&&x!=-INF&&(x+=k);} void apd(int id,int len,int k) {sm(id)+=1ll*len*k,ad(mx(id),k),ad(mxs(id),k),ad(mxt(id),k),ad(mn(id),k),ad(mns(id),k),ad(mnt(id),k),ad(smt(id),k);} void mxpd(int id,int k) { if(mn(id)>k) return; sm(id)+=1ll*(k-mn(id))*mnc(id),mxt(id)=k; if(mn(id)==mx(id)) mx(id)=k; if(mn(id)==mxs(id)) mxs(id)=k; mnt(id)=max(mnt(id),k),mn(id)=k; } void mnpd(int id,int k) { if(mx(id)<k) return; sm(id)+=1ll*(k-mx(id))*mxc(id),mnt(id)=k; if(mx(id)==mn(id)) mn(id)=k; if(mx(id)==mns(id)) mns(id)=k; mxt(id)=min(mxt(id),k),mx(id)=k; } void pd(int id,int l,int r) { if(smt(id)) apd(ls,mid-l+1,smt(id)),apd(rs,r-mid,smt(id)); if(mxt(id)!=-INF) mxpd(ls,mxt(id)),mxpd(rs,mxt(id)); if(mnt(id)!=INF) mnpd(ls,mnt(id)),mnpd(rs,mnt(id)); smt(id)=0,mxt(id)=-INF,mnt(id)=INF; } void bld(int id,int l,int r) { if(l==r) return tr[id]={0,a[l],1,-INF,-INF,a[l],1,INF,INF,a[l]},void(); bld(ls,l,mid),bld(rs,mid+1,r),pu(id),mxt(id)=-INF,mnt(id)=INF; } void aupd(int id,int l,int r,int L,int R,int k) { if(L<=l&&r<=R) return apd(id,r-l+1,k); pd(id,l,r),L<=mid?aupd(ls,l,mid,L,R,k):void(),R>mid?aupd(rs,mid+1,r,L,R,k):void(),pu(id); } void mxupd(int id,int l,int r,int L,int R,int k) { if(mn(id)>=k) return; if(L<=l&&r<=R&&mns(id)>k) return mxpd(id,k); if(l==r) return; pd(id,l,r),L<=mid?mxupd(ls,l,mid,L,R,k):void(),R>mid?mxupd(rs,mid+1,r,L,R,k):void(),pu(id); } void mnupd(int id,int l,int r,int L,int R,int k) { if(mx(id)<=k) return; if(L<=l&&r<=R&&mxs(id)<k) return mnpd(id,k); if(l==r) return; pd(id,l,r),L<=mid?mnupd(ls,l,mid,L,R,k):void(),R>mid?mnupd(rs,mid+1,r,L,R,k):void(),pu(id); } ll sqry(int id,int l,int r,int L,int R) { if(L<=l&&r<=R) return sm(id); pd(id,l,r); return (L<=mid?sqry(ls,l,mid,L,R):0)+(R>mid?sqry(rs,mid+1,r,L,R):0); } int mxqry(int id,int l,int r,int L,int R) { if(L<=l&&r<=R) return mx(id); pd(id,l,r); return max(L<=mid?mxqry(ls,l,mid,L,R):-INF,R>mid?mxqry(rs,mid+1,r,L,R):-INF); } int mnqry(int id,int l,int r,int L,int R) { if(L<=l&&r<=R) return mn(id); pd(id,l,r); return min(L<=mid?mnqry(ls,l,mid,L,R):INF,R>mid?mnqry(rs,mid+1,r,L,R):INF); } }T; void QwQ() { n=rd(); for(int i=1;i<=n;i++) a[i]=rd(); m=rd(),T.bld(1,1,n); for(int op,l,r;m--;) { op=rd(),l=rd(),r=rd(); if(op==1) T.aupd(1,1,n,l,r,rd()); else if(op==2) T.mxupd(1,1,n,l,r,rd()); else if(op==3) T.mnupd(1,1,n,l,r,rd()); else if(op==4) wrll(T.sqry(1,1,n,l,r),"\n"); else if(op==5) wr(T.mxqry(1,1,n,l,r),"\n"); else wr(T.mnqry(1,1,n,l,r),"\n"); } } signed main() { int T=1; while(T--) QwQ(); }
- 1
