题意
一个旅馆有n个房间,有m次操作,每次操作可以是 1,从第a个房间开始的连续b个房间全部住满 2:从a开始的b个房间全部清空 3:查询n个房间中最长连续空房间的长度。
思路
对于每个节点,记录这个节点的sta:状态,val:最长连续空房 lmx:区间内左侧连续空房间数 rmx:区间内右侧连续空房间数。并用子节点的值来更新父节点。
更新节点时,记得用子节点的状态更新当前节点的sta值,否则父节点更新时会出错。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int nMax = 1000000; struct{ int l,r,val,lmx,rmx,sta; //0empty 1full -1mix }node[3*nMax]; void gao(int u){ if(node[u].sta == 0){ node[u].val = node[u].lmx = node[u].rmx = node[u].r - node[u].l + 1; }else{ node[u].val = node[u].lmx = node[u].rmx =0; } } void build(int l ,int r ,int u){ node[u].l = l; node[u].r = r; node[u].sta = 0; gao(u); if(l == r){ return; } int m = (l+r)>>1; build(l ,m ,u*2); build(m+1 ,r ,u*2 + 1); } void update(int left ,int right ,int ope ,int u){ int l = node[u].l; int r = node[u].r; if(l == left && r == right){ node[u].sta = ope; gao(u); return; } if(node[u].sta == ope)return ; if(node[u].sta != -1){ node[2*u].sta = node[2*u+1].sta = node[u].sta; gao(u*2),gao(u*2+1); node[u].sta = -1; } int m = (l + r)>>1; if(right <= m){ update(left ,right ,ope ,u*2); }else{ if(left >= m + 1){ update(left ,right ,ope ,u*2+1); }else{ update(left ,m ,ope ,u*2); update(m+1,right ,ope ,u*2+1); } } if(node[u*2].sta == 0){ node[u].lmx = node[u*2].val + node[u*2+1].lmx; }else{ node[u].lmx = node[u*2].lmx; } if(node[u*2+1].sta == 0){ node[u].rmx = node[u*2+1].val + node[u*2].rmx; }else{ node[u].rmx = node[u*2+1].rmx; } node[u].val = max(node[u*2].val,node[u*2+1].val); node[u].val = max(node[u].val,node[u*2].rmx+node[u*2+1].lmx); if(node[u*2].sta == node[u*2+1].sta){ node[u].sta = node[u*2].sta; } } int main(){ int n ,m ,ope ,a ,b ; while(scanf("%d%d",&n,&m)!=EOF){ build(1 ,n ,1); while(m--){ scanf("%d",&ope); if(ope == 1){ scanf("%d%d",&a,&b); update(a ,a + b -1 ,1 ,1); } if(ope == 2){ scanf("%d%d",&a,&b); update(a ,a + b -1 ,0 ,1); } if(ope == 3){ printf("%d\n",node[1].val); } } } return 0; }
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1739733
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
NULL 博文链接:https://128kj.iteye.com/blog/1740501
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
NULL 博文链接:https://128kj.iteye.com/blog/1739064
线段树、树状数组算法入门 加 poj解题报告 pdf文档
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
poj 2763 程序 线段树 LCA 2000MS AC
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ题解 个人写法 线段树每个人都不一样
NULL 博文链接:https://128kj.iteye.com/blog/1746750
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
NULL 博文链接:https://128kj.iteye.com/blog/1733777
poj分类poj分类poj分类poj分类
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论