注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

二维线段树  

2013-07-17 21:33:27|  分类: 模板 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
我会告诉你
我个傻逼
几天前才会树套树的吗??

暑假认真刷刷白书吧
一个连入门都没达到的人
还谈什么比赛啊

Noi的day1完挂了,day2明天考,但是翻盘无力了,好在是同步赛
今年NOI的题解会补上的
然后暑假填的坑都会尽量写点什么

二维线段树,理解起来非常容易。
本来一个节点p代表[l,r]这么一段区间
现在一个节点(p1,p2)代表(lx,rx),(ly,ry)的一个矩形
我写了白书的那道例题,单点修改,矩形查询最值(我绝对不会写成极值的)
具体见代码&白书
修改主线段树操作的顺序非常重要

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 510
#define it tree[p1][p2]
using namespace std;
struct Seg_Tree2D
{
int minv,maxv;
friend Seg_Tree2D operator + (const Seg_Tree2D &a,const Seg_Tree2D &b)
{
Seg_Tree2D c;
c.minv=min(a.minv,b.minv);
c.maxv=max(a.maxv,b.maxv);
return c;
}
}tree[maxn<<2][maxn<<2];
int matrix[maxn][maxn],n,m;
void Build2(int p1,int p2,int l,int r,int a,int b)
{
if(a==b)
{
if(l==r)
it.minv=it.maxv=matrix[l][a];
else
it=tree[p1<<1][p2]+tree[p1<<1|1][p2];
}
else
{
int mid=(a+b)>>1;
Build2(p1,p2<<1,l,r,a,mid),Build2(p1,p2<<1|1,l,r,mid+1,b);
it=tree[p1][p2<<1]+tree[p1][p2<<1|1];
}
}
void Build1(int p1,int l,int r)
{
if(l==r)
{
Build2(p1,1,l,r,1,m);
return ;
}
int mid=(l+r)>>1;
Build1(p1<<1,l,mid),Build1(p1<<1|1,mid+1,r);
Build2(p1,1,l,r,1,m);
}
void Modify2(int p1,int p2,int l,int r,int a,int b,int y,int v)
{
if(a==b)
{
if(l==r)
it.minv=it.maxv=v;
else
it=tree[p1<<1][p2]+tree[p1<<1|1][p2];
}
else
{
int mid=(a+b)>>1;
if(y<=mid)
Modify2(p1,p2<<1,l,r,a,mid,y,v);
else
Modify2(p1,p2<<1|1,l,r,mid+1,b,y,v);
it=tree[p1][p2<<1]+tree[p1][p2<<1|1];
}
}
void Modify1(int p1,int l,int r,int x,int y,int v)
{
if(l==r)
{
Modify2(p1,1,l,r,1,m,y,v);
return ;
}
int mid=(l+r)>>1;
if(x<=mid)
Modify1(p1<<1,l,mid,x,y,v);
else
Modify1(p1<<1|1,mid+1,r,x,y,v);
Modify2(p1,1,l,r,1,m,y,v);
}
Seg_Tree2D Query2(int p1,int p2,int l,int r,int a,int b)
{
if(l==a&&r==b)
return it;
int mid=(l+r)>>1;
if(b<=mid)
return Query2(p1,p2<<1,l,mid,a,b);
else if(mid<a)
return Query2(p1,p2<<1|1,mid+1,r,a,b);
return Query2(p1,p2<<1,l,mid,a,mid)+Query2(p1,p2<<1|1,mid+1,r,mid+1,b);
}
Seg_Tree2D Query1(int p1,int l,int r,int ax,int ay,int bx,int by)
{
if(l==ax&&r==bx)
return Query2(p1,1,1,m,ay,by);
int mid=(l+r)>>1;
if(bx<=mid)
return Query1(p1<<1,l,mid,ax,ay,bx,by);
else if(mid<ax)
return Query1(p1<<1|1,mid+1,r,ax,ay,bx,by);
return Query1(p1<<1,l,mid,ax,ay,mid,by)+Query1(p1<<1|1,mid+1,r,mid+1,ay,bx,by);
}
void read()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&matrix[i][j]);
Build1(1,1,n);
}
void Query()
{
char task[10];
int q;
scanf("%d",&q);
Seg_Tree2D ans;
for(int i=1,a,b,c,d;i<=q;i++)
{
scanf("%s",task);
if(task[0]=='c')
{
scanf("%d %d %d",&a,&b,&c);
Modify1(1,1,n,a,b,c);
}
else
{
scanf("%d %d %d %d",&a,&b,&c,&d);
ans=Query1(1,1,n,a,b,c,d);
printf("%d %d\n",ans.maxv,ans.minv);
}
}
}
int main()
{
read();
Query();
return 0;
}


  评论这张
 
阅读(1355)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017