程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 11992(Fast Matrix Operations-線段樹區間加&改)[Template:SegmentTree]

UVA 11992(Fast Matrix Operations-線段樹區間加&改)[Template:SegmentTree]

編輯:C++入門知識

UVA 11992(Fast Matrix Operations-線段樹區間加&改)[Template:SegmentTree]


 

Fast Matrix Operations

There is a matrix containing at most 106 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 109.

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


4 4 8
1 1 2 4 4 5
3 2 1 4 4
1 1 1 3 4 2
3 1 2 4 4
3 1 1 3 4
2 2 1 4 4 2
3 1 2 4 4
1 1 1 4 3 3

Output for the Sample Input

45 0 5
78 5 7
69 2 7
39 2 7

 

 

線段樹,"區間加"和"區間修改"操作

由於矩陣最多有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 (L0) 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;
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved