?

Fast Matrix Operations

There is a matrix containing at most 10⁶ elements divided into r rows and c columns. Each element has a location (x,y) where 1<=x<=r,1<=y<=c. Initially, all the elements are zero. You need to handle four kinds of operations:

1 x1 y1 x2 y2 v

Increment each element (x,y) in submatrix (x1,y1,x2,y2) by v (v>0)

2 x1 y1 x2 y2 v

Set each element (x,y) in submatrix (x1,y1,x2,y2) to v

3 x1 y1 x2 y2

Output the summation, min value and max value of submatrix (x1,y1,x2,y2)

In the above descriptions, submatrix (x1,y1,x2,y2) means all the elements (x,y) satisfying x1<=x<=x2 and y1<=x<=y2. It is guaranteed that 1<=x1<=x2<=r, 1<=y1<=y2<=c. After any operation, the sum of all the elements in the matrix does not exceed 10⁹.

Input

There are several test cases. The first line of each case contains three positive integers r, c, m, where m (1<=m<=20,000) is the number of operations. Each of the next m lines contains a query. There will be at most twenty rows in the matrix. The input is terminated by end-of-file (EOF). The size of input file does not exceed 500KB.

Output

For each type-3 query, print the summation, min and max.

Sample Input

Output for the Sample Input

?

?

线段树，"区间加"和"区间修改"操作

由于矩阵最多有20行,所以可以将每行合到一个序列上

?

?

?

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i
            
             =0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define MEM2(a,i) memset(a,i,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXR (20+1) #define MAXN (8000000+10) #define MAXQ (20000+10) typedef long long ll; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return (a-b+(a-b)/F*F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} class SegmentTree { ll a[MAXN],minv[MAXN],sumv[MAXN],maxv[MAXN],addv[MAXN],setv[MAXN]; int n; public: SegmentTree(){ } SegmentTree(int _n):n(_n){ } void mem(int _n) { n=_n; For(i,4*n+3) a[i]=minv[i]=sumv[i]=maxv[i]=addv[i]=0,setv[i]=-1; } void maintain(int o,int L,int R) { sumv[o]=maxv[o]=minv[o]=0; if (L
             
              0) sumv[o]=setv[o]*(R-L+1),minv[o]=maxv[o]=setv[o]; minv[o]+=addv[o];maxv[o]+=addv[o];sumv[o]+=addv[o]*(R-L+1); } int y1,y2,v; void update(int o,int L,int R) //y1,y2,v { if (y1<=L&&R<=y2) { addv[o]+=v; } else{ pushdown(o); int M=(R+L)>>1; if (y1<=M) update(Lson,L,M); else maintain(Lson,L,M); if (M< y2) update(Rson,M+1,R); else maintain(Rson,M+1,R); } maintain(o,L,R); } void update2(int o,int L,int R) { if (y1<=L&&R<=y2) { setv[o]=v;addv[o]=0; } else{ pushdown(o); int M=(R+L)>>1; if (y1<=M) update2(Lson,L,M); else maintain(Lson,L,M); //维护pushodown，再次maintain if (M< y2) update2(Rson,M+1,R); else maintain(Rson,M+1,R); } maintain(o,L,R); } void pushdown(int o) { if (setv[o]>=0) { setv[Lson]=setv[Rson]=setv[o]; addv[Lson]=addv[Rson]=0; setv[o]=-1; } if (addv[o]) { addv[Lson]+=addv[o]; addv[Rson]+=addv[o]; addv[o]=0; } } void query2(int o,int L,int R,ll add) { if (setv[o]>=0) { _sum+=(setv[o]+addv[o]+add)*(min(R,y2)-max(L,y1)+1); _min=min(_min,setv[o]+addv[o]+add); _max=max(_max,setv[o]+addv[o]+add); } else if (y1<=L&&R<=y2) { _sum+=sumv[o]+add*(R-L+1); _min=min(_min,minv[o]+add); _max=max(_max,maxv[o]+add); } else { int M=(L+R)>>1; if (y1<=M) query2(Lson,L,M,add+addv[o]); if (M< y2) query2(Rson,M+1,R,add+addv[o]); } } ll _min,_max,_sum; void add(ll v,int l,int r) { y1=l,y2=r;this->v=v; update(1,1,n); } void set(ll v,int l,int r) { y1=l,y2=r;this->v=v; update2(1,1,n); } ll ask(int l,int r,int b=0) { _sum=0,_min=INF,_max=-1; y1=l,y2=r; query2(1,1,n,0); switch(b) { case 1:return _sum; case 2:return _min; case 3:return _max; default:break; } } //先set后add }S; int main() { // freopen("uva11992.in","r",stdin); // freopen(".out","w",stdout); int R,n,Q; while (~scanf("%d%d%d",&R,&n,&Q)) { S.mem(R*n); int p,x1,y1,x2,y2; while(Q--) { scanf("%d%d%d%d%d",&p,&x1,&y1,&x2,&y2); ll v; if (p<=2) scanf("%lld",&v); if (p==1) { Fork(i,x1,x2) S.add(v,(i-1)*n+y1,(i-1)*n+y2); } else if (p==2) { Fork(i,x1,x2) S.set(v,(i-1)*n+y1,(i-1)*n+y2); } else { ll s=0,mi=INF,ma=-1; Fork(i,x1,x2) { S.ask((i-1)*n+y1,(i-1)*n+y2); s+=S._sum;mi=min(mi,S._min);ma=max(ma,S._max); } printf("%lld %lld %lld\n",s,mi,ma); } } } return 0; } 
             
            
           
          
         
        
       
      
     
    
   
  

?

?