题意:
一个Hotel有N个房间,一开始全部为空。
接下来有M个询问。
输入1,代表房间被占用,然后输入两个数代表房间被占用的房间号和数量。
输入2,代表房间被置空,输入两个数代表房间被清空的房间号和数量。
输入3,输出连续最长没有被占用的房间数量。
思路:
线段树。。。。。。。。
写了好久,一开始更新节点各种WA,写不出来,参考了一段别人的代码,加上自己的理解,终于A了。
最近做了几道线段树,感觉运用的时候还是要灵活,每个节点变量的更新还得多琢磨一下。
然后是这道题,因为要寻找最长的置空的区间,那么有些置空的区间并不是线段树的节点,这时要更新置空区间的最大值的时候就的把左子树的右值和右子树的左值加起来在比较大小。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 16005
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x)(x<<1|1)
using namespace std;
int n;
struct kdq
{
int l,r;
int in;//记录该区间是否被覆盖,0代表未覆盖,1代表部分覆盖,2代表完全覆盖
int maxl,max,maxr;//记录节点,左边的最大长度maxl,右边的最大长度maxr,和该节点区间的最大长度max
} tree[Max*4];
void build_tree(int l,int r,int u)//建树
{
tree[u].l=l;
tree[u].r=r;
tree[u].in=0;
if(l==r)
{
tree[u].max=tree[u].maxr=tree[u].maxl=1;
return ;
}
int mid=(l+r)/2;
build_tree(l,mid,LL(u));
build_tree(mid+1,r,RR(u));
tree[u].max=tree[u].maxl=tree[u].maxr=tree[LL(u)].max+tree[RR(u)].max;
}
void update(int u)//更新节点的最大值
{
if(!tree[LL(u)].in)//如果该节点的左子树未被覆盖
tree[u].maxl=tree[LL(u)].max+tree[RR(u)].maxl;//则该节点左边maxl的最大值为:左子树的最大值加上右子树的左边值
else
tree[u].maxl=tree[LL(u)].maxl;//否则该节点的左边值就等于左子树的左边值
if(!tree[RR(u)].in)//同理更新节点的右值
tree[u].maxr=tree[LL(u)].maxr+tree[RR(u)].max;
else
tree[u].maxr=tree[RR(u)].maxr;
//下面一步是更新节点的max。
int maxl=max(tree[u].maxl,tree[u].maxr);//找出节点左右值的最大值。
int maxm=tree[LL(u)].maxr+tree[RR(u)].maxl;//该节点左子树和右子树中间的值。
int maxr=max(tree[LL(u)].max,tree[RR(u)].max);//左右子树的最大值
int maxmax=max(max(maxl,maxm),maxr);
tree[u].max=maxmax;//更新最大值
if(tree[LL(u)].in==tree[RR(u)].in)
tree[u].in=tree[LL(u)].in;
}
void insert(int l,int r,int u)//插入
{
if(l==tree[u].l&&tree[u].r==r)//如果区间相等
{
tree[u].in=2;//则完全覆盖
tree[u].maxl=tree[u].maxr=tree[u].max=0;//长度为0
return ;
}
if(!tree[u].in)//如果没被覆盖
{
tree[u].in=1;
tree[LL(u)].in=0;
tree[RR(u)].in=0;
//更新左右子树的最大值为区间长度
tree[LL(u)].maxl=tree[LL(u)].maxr=tree[LL(u)].max=tree[LL(u)].r-tree[LL(u)].l+1;
tree[RR(u)].maxl=tree[RR(u)].max=tree[RR(u)].maxr=tree[RR(u)].r-tree[RR(u)].l+1;
}
//向下递归
int mid=(tree[u].l+tree[u].r)>>1;
if(r<=mid)
insert(l,r,LL(u));
else if(l>mid)
insert(l,r,RR(u));
else
{
insert(l,mid,LL(u));
insert(mid+1,r,RR(u));
}
update(u);//更新节点的最大值
}
void remove(int l,int r,int u)//同插入
{
if(l==tree[u].l&&tree[u].r==r)//如果相等
{
tree[u].in=0;//则全部移除,为0。
tree[u].maxl=tree[u].maxr=tree[u].max=tree[u].r-tree[u].l+1;//更新最大值为区间长度
return ;
}
if(tree[u].in==2)//如果该节点被完全覆盖
{
tree[u].in=1;
tree[LL(u)].in=2;
tree[RR(u)].in=2;
//更新左右子树的最大值为0.(完全覆盖)
tree[LL(u)].maxl=tree[LL(u)].max=tree[LL(u)].maxr=0;
tree[RR(u)].maxl=tree[RR(u)].max=tree[RR(u)].maxr=0;
}
//向下递归
int mid=(tree[u].l+tree[u].r)>>1;
if(r<=mid)
remove(l,r,LL(u));
else if(l>mid)
remove(l,r,RR(u));
else
{
remove(l,mid,LL(u));
remove(mid+1,r,RR(u));
}
update(u);//更新节点的最大值
}
int main()
{
int i,j,k,l,n,m;
scanf("%d%d",&n,&m);
int a,b;
build_tree(1,n,1);
while(m--)
{
scanf("%d",&k);
if(k==1)
{
scanf("%d%d",&a,&b);
insert(a,a+b-1,1);
}
else if(k==2)
{
scanf("%d%d",&a,&b);
remove(a,a+b-1,1);
}
else
printf("%d\n",tree[1].max);
}
return 0;
}
。。
更多详细信息请查看
java教程网 http://www.itchm.com/forum-59-1.html
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1739733
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
poj 2763 程序 线段树 LCA 2000MS AC
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1740501
POJ3468,线段树处理,注意longlongint
线段树、树状数组算法入门 加 poj解题报告 pdf文档
NULL 博文链接:https://128kj.iteye.com/blog/1746750
POJ题解 个人写法 线段树每个人都不一样
NULL 博文链接:https://200830740306.iteye.com/blog/603493
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
* 线段树:例如 poj2528、poj2828、poj2777、poj2886、poj2750。 * 静态二叉检索树:例如 poj2482、poj2352。 * 树状树组:例如 poj1195、poj3321。 * RMQ:例如 poj3264、poj3368。 * 并查集的高级应用:例如 ...
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论