概述
题目：https://vjudge.net/problem/HUST-1546
题意：给你n个0和1的数列，m次询问，询问包括俩种：第一种： 0 x,y代表输出[x,y]区间的最长连续1的个数，第二种：1,x,y代表将[x,y]区间反转，也就是将区间中的0变为1，1变为0；
算法：线段树；
思路：用线段树进行预处理，记录当前区间的最长俩序1的个数，当期最长连续1的个数取决于三个值，分别是俩个子区间的最长连续1的个数以及考虑两个子区间融合后对当期区间的最长连续1的个数的影响，因此还需要记录两个端点的颜色，以及从端点向另一个端点延伸的最长序列，同时考虑到对一个区间反转后，区间内的最长0和1的序列交换，所以还需要记录当前区间的最长连续0的个数，同时偶数次反转对区间无影响。父亲区间的左右端从子区间继承过来，但当一个区间全为同一序列时，端值需要考虑区间融合的影响。更新区间时用懒标记进行标记，减少运行时间，同时对改变后的区间还需要重新考虑对其父区间的贡献，如果当前区间非修改区间但被标记过，需要下发标记，更新子区间。查询时，同更新一样，非目标区间有懒标记则需下放。同时查询时需要考虑当前区间是否能和已查询区间融合。
代码：
https://paste.ubuntu.com/p/nbsd8JQtqF/
最后
以上就是高高紫菜为你收集整理的POJ-Black And White的全部内容，希望文章能够帮你解决POJ-Black And White所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![HDU 1542 Atlantis [离散化 + 扫描线 + 线段树]](/uploads/reation/bcimg3.png)
发表评论 取消回复