赶在期末考试之前把这道傻逼题调了出来。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 100500 using namespace std; long long n,m,a[maxn]; long long root,tot=0,ls[maxn<<2],rs[maxn<<2]; long long lazy[maxn<<2],add[maxn<<2],sum[maxn<<2],mi[maxn<<2],mx[maxn<<2]; long long x,y,z; bool vis[maxn<<2]; void pushup(long long now) { sum[now]=sum[ls[now]]+sum[rs[now]]; mx[now]=max(mx[ls[now]],mx[rs[now]]); mi[now]=min(mi[ls[now]],mi[rs[now]]); } void build(long long &now,long long left,long long right) { now=++tot;lazy[now]=0;add[now]=0; if (left==right) { sum[now]=mx[now]=mi[now]=a[left]; return; } long long mid=(left+right)>>1; build(ls[now],left,mid); build(rs[now],mid+1,right); pushup(now); } void pushdown(long long now,long long left,long long right) { long long mid=(left+right)>>1; if (vis[now]==true) { lazy[ls[now]]=lazy[rs[now]]=mx[ls[now]]=mx[rs[now]]=mi[ls[now]]=mi[rs[now]]=lazy[now]; sum[ls[now]]=(mid-left+1)*lazy[now]; sum[rs[now]]=(right-mid)*lazy[now]; lazy[now]=0;vis[now]=false;vis[ls[now]]=vis[rs[now]]=true; add[ls[now]]=0;add[rs[now]]=0; } if (add[now]!=0) { add[ls[now]]+=add[now];add[rs[now]]+=add[now]; sum[ls[now]]+=(mid-left+1)*add[now]; sum[rs[now]]+=(right-mid)*add[now]; mx[ls[now]]+=add[now];mx[rs[now]]+=add[now]; mi[ls[now]]+=add[now];mi[rs[now]]+=add[now]; add[now]=0; } } void modify(long long now,long long left,long long right,long long l,long long r,long long p,long long type) { pushdown(now,left,right); if ((left==l) && (right==r)) { if (type==1) { add[now]+=p;sum[now]+=(right-left+1)*p;mx[now]+=p;mi[now]+=p; return; } else { lazy[now]=p;add[now]=0;sum[now]=p*(right-left+1); mx[now]=mi[now]=p;vis[now]=true; return; } } long long mid=(left+right)>>1; if (r<=mid) modify(ls[now],left,mid,l,r,p,type); else if (l>=mid+1) modify(rs[now],mid+1,right,l,r,p,type); else { modify(ls[now],left,mid,l,mid,p,type); modify(rs[now],mid+1,right,mid+1,r,p,type); } pushup(now); } long long ask(long long now,long long left,long long right,long long l,long long r,long long type) { pushdown(now,left,right); if ((left==l) && (right==r)) { if (type==1) return sum[now]; else if (type==2) return mx[now]; else return mi[now]; } long long mid=(left+right)>>1; if (r<=mid) return ask(ls[now],left,mid,l,r,type); else if (l>=mid+1) return ask(rs[now],mid+1,right,l,r,type); else { if (type==1) { long long regis1=ask(ls[now],left,mid,l,mid,type); long long regis2=ask(rs[now],mid+1,right,mid+1,r,type); return regis1+regis2; } else if (type==2) return max(ask(ls[now],left,mid,l,mid,type),ask(rs[now],mid+1,right,mid+1,r,type)); else return min(ask(ls[now],left,mid,l,mid,type),ask(rs[now],mid+1,right,mid+1,r,type)); } } int main() { memset(vis,false,sizeof(vis)); scanf("%lld%lld",&n,&m); for (long long i=1;i<=n;i++) scanf("%lld",&a[i]); build(root,1,n); for (long long i=1;i<=m;i++) { char type[10]; scanf("%s",type); if (type[0]=='a') { scanf("%lld%lld%lld",&x,&y,&z); modify(root,1,n,x,y,z,1); } else if ((type[0]=='s') && (type[1]=='e')) { scanf("%lld%lld%lld",&x,&y,&z); modify(root,1,n,x,y,z,2); } else if ((type[0]=='s') && (type[1]=='u')) { scanf("%lld%lld",&x,&y); printf("%lld ",ask(root,1,n,x,y,1)); } else if ((type[0]=='m') && (type[1]=='a')) { scanf("%lld%lld",&x,&y); printf("%lld ",ask(root,1,n,x,y,2)); } else { scanf("%lld%lld",&x,&y); printf("%lld ",ask(root,1,n,x,y,3)); } } return 0; }