本文主要是介绍uva 11992 线段树对矩阵进行更新查询，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3143
把矩阵变成一行，然后计算位置，lrj给了线段树数组做法 但是我做的线段树空间过大，直接爆掉，所以换方法了
主要还是测试自己的线段树区间更新的模板
各种RE+WA之后AC，，，，，
做的时候出现的几个错误：
1、行和列弄错
2、build初始化的时候，mmin mmax 都初始化为0才对
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;#define lson(i) l , mid , (i)*2
#define rson(i) mid + 1 , r , ((i)*2 +1)
#define ll rt*2
#define rr (rt*2+1)const int INFMIN = 0xffffffff;
const int INFMAX = 1000000009;//0x80000000;
const int MAXN = 30001000;
struct Node{int l,r;int mmax,mmin,sum,add,s;/*s去标记是不是被set*/
};
Node nodes[MAXN];int mmax,mmin,sum;void PushUp(int rt){nodes[rt].mmax = max(nodes[ll].mmax,nodes[rr].mmax);nodes[rt].mmin = min(nodes[ll].mmin,nodes[rr].mmin);nodes[rt].sum = nodes[ll].sum + nodes[rr].sum;}void PushDown(int rt){//if(nodes[rt].add && flag == 1)if(nodes[rt].add){nodes[ll].add += nodes[rt].add;nodes[ll].mmin += nodes[rt].add;nodes[ll].mmax += nodes[rt].add;nodes[rr].add += nodes[rt].add;nodes[rr].mmin += nodes[rt].add;nodes[rr].mmax += nodes[rt].add;nodes[ll].sum += nodes[rt].add*(nodes[ll].r-nodes[ll].l+1);nodes[rr].sum += nodes[rt].add*(nodes[rr].r-nodes[rr].l+1);nodes[rt].add = 0;}//if(nodes[rt].s && flag == 2)if(nodes[rt].s){nodes[ll].s = nodes[rr].s=nodes[rt].s;nodes[ll].mmin = nodes[ll].mmax = nodes[rr].mmax = nodes[rr].mmin = nodes[rt].mmax;nodes[ll].sum = nodes[rt].mmin*(nodes[ll].r-nodes[ll].l+1);nodes[rr].sum = nodes[rt].mmin*(nodes[rr].r-nodes[rr].l+1);nodes[ll].add = nodes[rr].add = 0;//nodes[rt].s=0;}}void Build(int l,int r,int rt){nodes[rt].l=l;nodes[rt].r=r;nodes[rt].add =0;nodes[rt].s=0;nodes[rt].sum =0;nodes[rt].mmin=0;nodes[rt].mmax=0;if(l == r){//nodes[rt].mmin = nodes[rt].mmax = nodes[rt].sum =a[l];nodes[rt].mmin = nodes[rt].mmax = nodes[rt].sum =0;return ;}int mid = (nodes[rt].l+nodes[rt].r)/2;Build(lson(rt));Build(rson(rt));//PushUp(rt);}void Update(int l,int r,int add,int rt,int flag){
/
//printf("rt=%d l=%d r=%d add=%d flag =%d nodes[rt].l=%d nodes[rt].r=%d\n",rt,l,r,add,flag,nodes[rt].l,nodes[rt].r);if(l<=nodes[rt].l && nodes[rt].r<=r){if(flag == 1)/*increase*/{nodes[rt].mmax += add;nodes[rt].mmin += add;nodes[rt].add += add;nodes[rt].sum += add*(nodes[rt].r-nodes[rt].l+1);}else{nodes[rt].mmax = add;nodes[rt].mmin = add;nodes[rt].add=0;nodes[rt].s=1;nodes[rt].sum = add*(nodes[rt].r-nodes[rt].l+1);}return;}PushDown(rt);int mid = (nodes[rt].l+nodes[rt].r)/2;if(l<=mid)Update(l,r,add,ll,flag);if(r>mid)Update(l,r,add,rr,flag);PushUp(rt);}void Query(int l,int r,int rt)/*1表示mmin 2--mmax 3-sum*/{/
//printf("rt=%d l=%d r=%d nodes[rt].l=%d nodes[rt].r=%d\n",rt,l,r,nodes[rt].l,nodes[rt].r);///if(l<=nodes[rt].l && nodes[rt].r<=r){mmin = min(mmin,nodes[rt].mmin);mmax = max(mmax,nodes[rt].mmax);sum += nodes[rt].sum;return ;}PushDown(rt);int mid = (nodes[rt].l+nodes[rt].r)/2;if(l<=mid)Query(l,r,ll);if(r>mid)Query(l,r,rr);PushUp(rt);}void clr()/*每次查询之前使用*/{sum =0;mmin=INFMAX;mmax=INFMIN;}int main()
{//freopen("uva11992.txt","r",stdin);int r,c,m,v,flag,x1,y1,x2,y2;while(scanf("%d%d%d",&r,&c,&m)!=EOF){Build(1,r*c,1);while(m--){scanf("%d%d%d%d%d",&flag,&x1,&y1,&x2,&y2);if(flag<3){scanf("%d",&v);for(int i=x1;i<=x2;i++)/*此处注意*/{
///
//printf("i=%d\n",i);Update(y1+(i-1)*c,y2+(i-1)*c,v,1,flag);}}else{int anssum=0,ansmin=INFMAX,ansmax=INFMIN;for(int i=x1;i<=x2;i++){clr();Query(y1+(i-1)*c,y2+(i-1)*c,1);// printf("**min=%d\n",mmin);/anssum+=sum;ansmax=max(ansmax,mmax);ansmin=min(ansmin,mmin);}printf("%d %d %d\n",anssum,ansmin,ansmax);}}}return 0;
}
这篇关于uva 11992 线段树对矩阵进行更新查询的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
