这个题目的意思是
有一个矩阵,给你三个操作
分别是给一个子矩阵加一个值
或者将一个子矩阵的每个元素赋成一个值
再就是查询一个子矩阵的所有元素的和,最大值,最小值
因为是一个矩阵,我们可以针对每一行构造一个线段树
然后再对r行的结果再处理
所以这就是线段树的成段更新
那么这个线段树就有五个函数是很重要的
更新加的操作
更新赋值的操作
三个查询操作
其实难点主要在更新操作
因为既有赋值,又有加操作,所以弄清逻辑关系
如果当前区间有赋值标记,又有加标记,那显然是赋值标记优先的,因为你怎么加了,来个赋值就给你弄没了
想清楚这点很重要,然后在pushdown的时候,把两个标记都pushdown下去,并把孩子的sum,min,max处理,因为pushup的时候要用
pushup就很简单啦,直接网上pushup就OK
再就是pushdown的位置要弄清
如果当前更新区间已经符合要求,就没要pushdown了,直接update就好了,因为我们是对区间进行操作
如果没必要涉及到子区间,就别去动,容易出错。
在这里我要吐槽一下:UVA这么牛的网站怎么这么卡啊,还有这题的范围说的太宽泛了
最多有10^6个元素,最有20行,也就是说一行最多可以10^6个元素啊,尼玛*4就爆了啊
强烈吐槽
下面是我的代码:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxn = 20+5; struct node { int sum; int mins; int maxs; int add; int set; }; node tree[maxn][1<<17]; int r,c,m; void build(int num,int l,int r,int rt) { tree[num][rt].add=tree[num][rt].maxs = tree[num][rt].mins = tree[num][rt].sum = 0; tree[num][rt].set = -1; if(l==r) return; int m = (l+r)>>1; build(num,lson); build(num,rson); } void pushdown(int num,int l,int r,int rt) { int m=(l+r)>>1; if(tree[num][rt].set>=0) { tree[num][rt<<1].set = tree[num][rt<<1|1].set=tree[num][rt].set; tree[num][rt<<1].add = tree[num][rt<<1|1].add=0; tree[num][rt<<1].mins = tree[num][rt<<1].maxs = tree[num][rt].set; tree[num][rt<<1|1].maxs = tree[num][rt<<1|1].mins = tree[num][rt].set; tree[num][rt<<1].sum = (m-l+1)*tree[num][rt].set; tree[num][rt<<1|1].sum = (r-m)*tree[num][rt].set; tree[num][rt].set=-1; } if(tree[num][rt].add>0) { tree[num][rt<<1].add +=tree[num][rt].add; tree[num][rt<<1|1].add +=tree[num][rt].add; tree[num][rt<<1].mins+=tree[num][rt].add; tree[num][rt<<1].maxs+=tree[num][rt].add; tree[num][rt<<1|1].maxs+=tree[num][rt].add; tree[num][rt<<1|1].mins+=tree[num][rt].add; tree[num][rt<<1].sum+=(m-l+1)*tree[num][rt].add; tree[num][rt<<1|1].sum+=(r-m)*tree[num][rt].add; tree[num][rt].add=0; } } void pushup(int num,int rt) { tree[num][rt].sum = tree[num][rt<<1].sum+tree[num][rt<<1|1].sum; tree[num][rt].maxs = max(tree[num][rt<<1].maxs,tree[num][rt<<1|1].maxs); tree[num][rt].mins = min(tree[num][rt<<1].mins,tree[num][rt<<1|1].mins); } void update_add(int num,int l,int r,int rt,int L,int R,int v) { if(L<=l && r<=R) { tree[num][rt].sum+=(r-l+1)*v; tree[num][rt].mins+=v; tree[num][rt].maxs+=v; tree[num][rt].add+=v; return; } pushdown(num,l,r,rt); int m = (l+r)>>1; if(L<=m) update_add(num,lson,L,R,v); if(R>m) update_add(num,rson,L,R,v); pushup(num,rt); } void update_set(int num,int l,int r,int rt,int L,int R,int v) { if(L<=l && r<=R) { tree[num][rt].sum=(r-l+1)*v; tree[num][rt].mins=v; tree[num][rt].maxs=v; tree[num][rt].add=0; tree[num][rt].set=v; return; } //这里一定要不是查询区间了再往下推,而不能直接往下推,即pushdown不能放到前面去 pushdown(num,l,r,rt); int m = (l+r)>>1; if(L<=m) update_set(num,lson,L,R,v); if(R>m) update_set(num,rson,L,R,v); pushup(num,rt); } int query_sum(int num,int l,int r,int rt,int L,int R) { if(L<=l && r<=R) return tree[num][rt].sum; pushdown(num,l,r,rt); int ret = 0; int m = (l+r)>>1; if(L<=m) ret+=query_sum(num,lson,L,R); if(R>m) ret+=query_sum(num,rson,L,R); pushup(num,rt); return ret; } int query_min(int num,int l,int r,int rt,int L,int R) { if(L<=l && r<=R) return tree[num][rt].mins; pushdown(num,l,r,rt); int ret = 1000000000; int m = (l+r)>>1; if(L<=m) ret = min(ret,query_min(num,lson,L,R)); if(R>m) ret = min(ret,query_min(num,rson,L,R)); pushup(num,rt); return ret; } int query_max(int num,int l,int r,int rt,int L,int R) { if(L<=l && r<=R) return tree[num][rt].maxs; pushdown(num,l,r,rt); int ret = -1000000000; int m = (l+r)>>1; if(L<=m) ret = max(ret,query_max(num,lson,L,R)); if(R>m) ret = max(ret,query_max(num,rson,L,R)); pushup(num,rt); return ret; } int main() { while(~scanf("%d%d%d",&r,&c,&m)) { for(int i=1;i<=r;i++) build(i,1,c,1); int q,x1,y1,x2,y2,v; while(m--) { int asum=0; int amax = -1000000000; int amin = 1000000000; scanf("%d%d%d%d%d",&q,&x1,&y1,&x2,&y2); if(q!=3) scanf("%d",&v); if(q==1) { //printf("q1\n"); for(int i=x1;i<=x2;i++)//更新x个树 { update_add(i,1,c,1,y1,y2,v); } //printf("q1 done\n"); } else if(q==2) { for(int i=x1;i<=x2;i++)//更新x个树 { update_set(i,1,c,1,y1,y2,v); } } else { //printf("q\n"); for(int i=x1;i<=x2;i++) { asum+=query_sum(i,1,c,1,y1,y2); //printf("q s\n"); int t1 = query_min(i,1,c,1,y1,y2); //printf("q min\n"); int t2 = query_max(i,1,c,1,y1,y2); //printf("q max\n"); if(amin>t1) amin=t1; if(amax<t2) amax=t2; } printf("%d %d %d\n",asum,amin,amax); } } } return 0; }