首页 > 代码库 > HDU 4819 Mosaic --二维线段树(树套树)
HDU 4819 Mosaic --二维线段树(树套树)
题意： 给一个矩阵，每次查询一个子矩阵内的最大最小值，然后更新子矩阵中心点为(Max+Min)/2.
解法： 由于是矩阵，且要求区间最大最小和更新单点，很容易想到二维的线段树，可是因为之前没写过二维的线段树，所以没跳出来。后来熟悉了一下，原来很多细节地方都没有考虑到。
这里build,update,query都分为两个函数，第一个为Y轴的(sub_update)，第二个为X轴的(update)，不仅每个sub_update或sub_build后面要加Y轴的pushup函数，而且每个update或build函数最后也要进行pushup，只不过是X轴的pushup，写成 sub_build(rt,-1,1,n,1) 或 sub_update(rt,-1,1,n,1);
二维线段树就是这里比较费解一点，我感觉， 其他地方还比较好理解。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#define Mod 1000000007#define lll __int64using namespace std;#define N 100007struct sub_seg{ lll maxi,mini;};struct seg{ sub_seg st[810<<2];}tt[810<<2];int n;lll Max,Min;void pushup(int xrt,int rt){ tt[xrt].st[rt].maxi = max(tt[xrt].st[rt<<1].maxi,tt[xrt].st[rt<<1|1].maxi); tt[xrt].st[rt].mini = min(tt[xrt].st[rt<<1].mini,tt[xrt].st[rt<<1|1].mini);}void sub_build(int xrt,int posY,int l,int r,int rt){ if(l == r) { if(posY != -1) { scanf("%I64d",&tt[xrt].st[rt].maxi); tt[xrt].st[rt].mini = tt[xrt].st[rt].maxi; } else { tt[xrt].st[rt].maxi = max(tt[xrt<<1].st[rt].maxi,tt[xrt<<1|1].st[rt].maxi); tt[xrt].st[rt].mini = min(tt[xrt<<1].st[rt].mini,tt[xrt<<1|1].st[rt].mini); } return; } int mid = (l + r) >> 1; sub_build(xrt,posY, l,mid, 2*rt); sub_build(xrt,posY, mid+1,r, 2*rt+1); pushup(xrt,rt); //pushup Y}void build(int l, int r, int rt){ if(l == r) { sub_build(rt,l,1,n,1); return; } int mid = (l + r) >> 1; build(l,mid,2*rt); build(mid+1,r,2*rt+1); sub_build(rt,-1,1,n,1); //pushup X}void sub_update(int xrt,int pos,int y,int l,int r,int val,int rt){ if(l == r) { if(pos!=-1) tt[xrt].st[rt].maxi = tt[xrt].st[rt].mini = val; else { tt[xrt].st[rt].maxi = max(tt[xrt<<1].st[rt].maxi,tt[xrt<<1|1].st[rt].maxi); tt[xrt].st[rt].mini = min(tt[xrt<<1].st[rt].mini,tt[xrt<<1|1].st[rt].mini); } return; } int mid = (l+r) >> 1 ; if(y <= mid) sub_update(xrt, pos, y, l,mid, val, rt<<1) ; else sub_update(xrt, pos, y, mid+1,r, val, rt<<1|1) ; pushup(xrt,rt); //pushup Y维}void update(int x,int y,int l,int r,int val,int rt) //单点更新{ if(l == r) { sub_update(rt,l,y,1,n,val,1); return; } int mid = (l+r) >> 1; if(x<=mid) update(x,y, l,mid, val, rt<<1); else update(x,y, mid+1,r, val, rt<<1|1); sub_update(rt,-1,y,1,n,val,1); //pushup X维}void sub_query(int xrt,int aa,int bb,int l,int r,int rt){ if(aa <= l && bb >= r) { Max = max(Max,tt[xrt].st[rt].maxi); Min = min(Min,tt[xrt].st[rt].mini); return; } int mid = (l+r)>>1; if(aa<=mid) sub_query(xrt,aa,bb,l,mid, rt<<1); if(bb>mid) sub_query(xrt,aa,bb,mid+1,r, rt<<1|1);}void query(int l,int r,int aa,int bb,int L1,int R1,int rt){ if(aa <= l && bb >= r) { sub_query(rt,L1,R1,1,n,1); return; } int mid = (l+r)>>1; if(aa <= mid) query(l,mid,aa,bb,L1,R1, rt<<1); if(bb > mid) query(mid+1,r,aa,bb,L1,R1, rt<<1|1);}int main(){ int t,i,j,m,x,y,L,cs = 1; scanf("%d",&t); while(t--) { scanf("%d",&n); build(1,n,1); scanf("%d",&m); printf("Case #%d:\n",cs++); while(m--) { scanf("%d%d%d",&x,&y,&L); int Lx = max(1,x-L/2); int Ly = max(1,y-L/2); int Rx = min(n,x+L/2); int Ry = min(y+L/2,n); Max = -1, Min = Mod; query(1,n,Lx,Rx,Ly,Ry,1); lll mid = (Max+Min)/2LL; printf("%I64d\n",mid); update(x,y,1,n,mid,1); } } return 0;}
HDU 4819 Mosaic --二维线段树(树套树)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。