首页 > 代码库 > 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】糖果雨