首页 > 代码库 > bzoj1062【noi2008】糖果雨
bzoj1062【noi2008】糖果雨
orz.....神tm数形结合题
题意:http://www.lydsy.com/JudgeOnline/problem.php?id=1062
插入线段,删除线段,查询区间内线段个数,线段随时间往复运动
sol: 线段肯定没法操作,考虑把线段化成点
首先显然因为2*len是一个周期,所以t%=2*len
因为线段有一个初始位置l,考虑将线段移动至l=0的位置,用时间和长度表示该线段
插入一个点时,该点的坐标为((t-l*d)%len,r-l)
删除一个点时,直接删除即可
对于查询操作,t时刻与[l,r]有交的线段如下图
先画出t=0时的图像,左右沿x=len对称,再右移t个单位,超过右边界的补到左边
....这样奇怪的图形也没法处理QAQ不过可以将其补成平行四边形
还是比较难搞QAQ,然而可以通过扭曲坐标系将其化成矩形
<len的点横坐标仍为t,纵坐标为t+Pi
>len的点横坐标仍为t,纵坐标为t﹣Pi
唔....然后就是平面加点,删点,查询子矩阵和QwQ用二维树状数组维护即可
bzoj1062【noi2008】糖果雨
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。