。。。调了三个晚上的模板题，各种千奇百怪的错误全都出现过了一遍QWQ
题目大意：区间增减(add)，区间修改为一个数(set)，区间求和(sum)，区间最大值(max)，区间最小值(min)。
tips:set优先级大于add，一个节点进行set操作要将add的lazy清除，一个结点进行add操作要将set的lazy下传，对于一个结点set和add的lazy不能同时存在，查询的时候先下传set的lazy再下传add的lazy。
好像codevs的评测姬有点奇怪，本地开四倍不会RE，评测姬会，只好开八倍了QAQ
代码如下：
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; struct poi{int x,l,r;long long sum,delta1,delta2,max,min;bool en;}a[810000]; int n,m; long long x,y,z; char ch[100]; long long calcsum(int x){return a[x].en?a[x].delta1*(a[x].r-a[x].l+1):a[x].sum+a[x].delta2*(a[x].r-a[x].l+1);} long long calcmax(int x){return a[x].en?a[x].delta1:a[x].max+a[x].delta2;} long long calcmin(int x){return a[x].en?a[x].delta1:a[x].min+a[x].delta2;} void build(int x,int l,int r) { a[x].l=l;a[x].r=r;a[x].en=a[x].delta1=a[x].delta2=0; if(l==r)scanf("%lld",&a[x].sum),a[x].max=a[x].min=a[x].sum; else { build(x*2,l,(l+r)>>1);build(x*2+1,((l+r)>>1)+1,r); a[x].sum=a[x*2].sum+a[x*2+1].sum; a[x].max=max(a[x*2].max,a[x*2+1].max); a[x].min=min(a[x*2].min,a[x*2+1].min); } } void down1(int x) { a[x*2].en=a[x*2+1].en=1;a[x*2].delta1=a[x*2+1].delta1=a[x].delta1; a[x].max=calcmax(x);a[x].min=calcmin(x);a[x].sum=calcsum(x);a[x].en=0; a[x*2].delta2=a[x*2+1].delta2=0; } void down2(int x) { a[x].sum+=a[x].delta2*(a[x].r-a[x].l+1);a[x].max+=a[x].delta2;a[x].min+=a[x].delta2; if(a[x*2].en)down1(x*2);if(a[x*2+1].en)down1(x*2+1); a[x*2].delta2+=a[x].delta2;a[x*2+1].delta2+=a[x].delta2;a[x].delta2=0; } void update1(int x,int l,int r,long long delta) { if(a[x].en&&a[x].l)down1(x); if(l<=a[x].l&&a[x].r<=r)a[x].en=1,a[x].delta1=delta,a[x].delta2=0,a[x].sum=a[x].delta1*(a[x].r-a[x].l+1); else { if(a[x].delta2)down2(x); if(l<=(a[x].l+a[x].r)>>1)update1(x*2,l,r,delta); if(r>(a[x].l+a[x].r)>>1)update1(x*2+1,l,r,delta); a[x].sum=calcsum(x*2)+calcsum(x*2+1); a[x].max=max(calcmax(x*2),calcmax(x*2+1)); a[x].min=min(calcmin(x*2),calcmin(x*2+1)); } } void update2(int x,int l,int r,long long delta) { if(a[x].en&&a[x].l)down1(x); if(l<=a[x].l&&a[x].r<=r)a[x].delta2+=delta; else { if(a[x].delta2)down2(x); if(l<=(a[x].l+a[x].r)>>1)update2(x*2,l,r,delta); if(r>(a[x].l+a[x].r)>>1)update2(x*2+1,l,r,delta); a[x].sum=calcsum(x*2)+calcsum(x*2+1); a[x].max=max(calcmax(x*2),calcmax(x*2+1)); a[x].min=min(calcmin(x*2),calcmin(x*2+1)); } } long long querysum(int x,int l,int r) { long long ret=0; if(l<=a[x].l&&a[x].r<=r)ret=calcsum(x); else { if(a[x].en&&a[x].l)down1(x); if(a[x].delta2)down2(x); if(l<=(a[x].l+a[x].r)>>1)ret+=querysum(x*2,l,r); if(r>(a[x].l+a[x].r)>>1)ret+=querysum(x*2+1,l,r); } return ret; } long long querymax(int x,int l,int r) { long long ret=-100000000; if(l<=a[x].l&&a[x].r<=r)ret=calcmax(x); else { if(a[x].en&&a[x].l)down1(x); if(a[x].delta2)down2(x); if(l<=(a[x].l+a[x].r)>>1)ret=max(ret,querymax(x*2,l,r)); if(r>(a[x].l+a[x].r)>>1)ret=max(ret,querymax(x*2+1,l,r)); } return ret; } long long querymin(int x,int l,int r) { long long ret=100000000; if(l<=a[x].l&&a[x].r<=r)ret=calcmin(x); else { if(a[x].en&&a[x].l)down1(x); if(a[x].delta2)down2(x); if(l<=(a[x].l+a[x].r)>>1)ret=min(ret,querymin(x*2,l,r)); if(r>(a[x].l+a[x].r)>>1)ret=min(ret,querymin(x*2+1,l,r)); } return ret; } int main() { scanf("%d %d",&n,&m); build(1,1,n); for(int i=1;i<=m;i++) { getchar(); scanf("%s",ch); if(ch[0]==‘a‘) { scanf("%lld %lld %lld",&x,&y,&z); update2(1,x,y,z); } if(ch[1]==‘e‘) { scanf("%lld %lld %lld",&x,&y,&z); update1(1,x,y,z); } if(ch[1]==‘u‘) { scanf("%lld %lld",&x,&y); printf("%lld\n",querysum(1,x,y)); } if(ch[1]==‘a‘) { scanf("%lld %lld",&x,&y); printf("%lld\n",querymax(1,x,y)); } if(ch[1]==‘i‘) { scanf("%lld %lld",&x,&y); printf("%lld\n",querymin(1,x,y)); } } }
原文：http://www.cnblogs.com/Sakits/p/6411855.html
