自写线段树,难点既每次节点的维护pushDOWN函数, add && set #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,(rt<<1|1) #define INF 1000000100 const int maxn = 1000010; int sum[21][maxn<<2],MAX[21][maxn<<2],MIN[21][maxn<<2],add[21][maxn<<2],val[21][maxn<<2]; void pushUP(int l,int r,int rt,int i){ sum[i][rt]=sum[i][rt<<1]+sum[i][rt<<1|1]; MIN[i][rt]=min(MIN[i][rt<<1],MIN[i][rt<<1|1]); MAX[i][rt]=max(MAX[i][rt<<1],MAX[i][rt<<1|1]); } void setpushDOWN(int l,int r,int rt,int m,int i){ if(l==r){ val[i][rt]=INF; return ; } val[i][rt<<1]=val[i][rt<<1|1]=val[i][rt]; sum[i][rt<<1]=(m-(m>>1))*val[i][rt]; sum[i][rt<<1|1]=((m>>1))*val[i][rt]; MAX[i][rt<<1]=val[i][rt]; MAX[i][rt<<1|1]=val[i][rt]; MIN[i][rt<<1]=val[i][rt]; MIN[i][rt<<1|1]=val[i][rt]; add[i][rt<<1]=add[i][rt<<1|1]=INF; val[i][rt]=INF; } void addpushDOWN(int l,int r,int rt,int M,int i){ if(l==r){ add[i][rt]=INF; return ; } int m=(l+r)>>1; if(val[i][rt<<1]!=INF){ setpushDOWN(lson,m-l+1,i); val[i][rt<<1]=INF; add[i][rt<<1]=add[i][rt]; } else{ if(add[i][rt<<1]!=INF) add[i][rt<<1]+=add[i][rt]; else add[i][rt<<1]=add[i][rt]; } if(val[i][rt<<1|1]!=INF){ setpushDOWN(rson,r-m,i); val[i][rt<<1|1]=INF; add[i][rt<<1|1]=add[i][rt]; } else{ if(add[i][rt<<1|1]!=INF) add[i][rt<<1|1]+=add[i][rt]; else add[i][rt<<1|1]=add[i][rt]; } sum[i][rt<<1]+=(M-(M>>1))*add[i][rt]; sum[i][rt<<1|1]+=((M>>1))*add[i][rt]; MAX[i][rt<<1]+=add[i][rt]; MAX[i][rt<<1|1]+=add[i][rt]; MIN[i][rt<<1]+=add[i][rt]; MIN[i][rt<<1|1]+=add[i][rt]; add[i][rt]=INF; } void pushDOWN(int l,int r,int rt,int m,int i){ if(val[i][rt]!=INF){ setpushDOWN(l,r,rt,m,i); } else if(add[i][rt]!=INF){ addpushDOWN(l,r,rt,m,i); } } void build(int l,int r,int rt,int i){ add[i][rt]=val[i][rt]=INF; if(l==r){ sum[i][rt]=MIN[i][rt]=MAX[i][rt]=0; return ; } int m=(l+r)>>1; build(lson,i); build(rson,i); pushUP(l,r,rt,i); } int ql,qr,addv; void update(int l,int r,int rt,int i){ pushDOWN(l,r,rt,r-l+1,i); if(ql<=l&&r<=qr){ add[i][rt]=addv; sum[i][rt]+=(r-l+1)*addv; MIN[i][rt]+=addv; MAX[i][rt]+=addv; return ; } int m=(l+r)>>1; if(ql<=m) update(lson,i); if(qr >m) update(rson,i); pushUP(l,r,rt,i); } int value; void Update(int l,int r,int rt,int i){ pushDOWN(l,r,rt,r-l+1,i); if(ql<=l&&r<=qr){ val[i][rt]=value; sum[i][rt]=(r-l+1)*value; MIN[i][rt]=value; MAX[i][rt]=value; return ; } int m=(l+r)>>1; if(ql<=m) Update(lson,i); if(qr >m) Update(rson,i); pushUP(l,r,rt,i); } int _sum,_min,_max; void query(int l,int r,int rt,int i){ pushDOWN(l,r,rt,r-l+1,i); if(ql<=l&&r<=qr){ _min=min(_min,MIN[i][rt]); _max=max(_max,MAX[i][rt]); _sum+=sum[i][rt]; return ; } int m=(l+r)>>1; if(ql<=m) query(lson,i); if(qr >m) query(rson,i); } void Show(int l,int r,int rt,int i){ if(l==r){ cout<<"L-->"<<" "<<l<<" "<<"R-->"<<" "<<r<<" "<<add[i][rt]<<" "<<sum[i][rt]<<endl; return ; } int m=(l+r)>>1; Show(lson,i); Show(rson,i); cout<<"L-->"<<" "<<l<<" "<<"R-->"<<" "<<r<<" "<<add[i][rt]<<" "<<sum[i][rt]<<endl; } int r,c,Q; int read(){ for(int i=1;i<=r;i++) build(1,c,1,i); } int main() { while(scanf("%d %d %d",&r,&c,&Q)!=EOF){ read(); while(Q--){ int cmd; int x1,x2,y1,y2; scanf("%d %d %d %d %d",&cmd,&x1,&y1,&x2,&y2); if(cmd==1){ scanf("%d",&addv); ql=y1; qr=y2; for(int i=x1;i<=x2;i++) update(1,c,1,i); } else if(cmd==2){ scanf("%d",&value); ql=y1; qr=y2; for(int i=x1;i<=x2;i++) Update(1,c,1,i); } else { _sum=0; _min=INF; _max=-INF; ql=y1; qr=y2; for(int i=x1;i<=x2;i++) query(1,c,1,i); printf("%d %d %d\n",_sum,_min,_max); } //Show(1,c,1,1); cout<<"_______________\n"; } // void show(); show(); } return 0; } void show(){ for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ ql=j,qr=j; _sum=0; _min=INF; _max=-INF; query(1,c,1,i); cout<<_sum<<" "; } cout<<endl; } cout<<"_______________\n"; }