首页 > 代码库 > uva 11992 线段树对矩阵进行更新查询
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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。