almost 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1062
分析:
很显然一条线段经过的时间会回到初始位置,因此可以启发我们把所有的时间都
对于一条线段我们有参数:插入时间,左边界,右边界,以及方向和颜色。因为每一条线段的颜色都不同,所以我们可以忽略颜色这个参数(然而我这个地方数组开小了竟然RE了一次)。
然而这么多条件我们是不好处理的。我们其实只要知道两个值,就是当线段左端点在处的时间以及此时右端点位置,记为
那么这样我们就只有两个变量了,将这两个变量变成坐标,形象化的表示成线段~,就可以尝试在二维平面上弄一些东西了。
考虑一个询问,令,那么询问其实就是将所有的其他线段平移到之后,~这条线段与多少条已知线段相交。这里的平移是指方向平移,因为线段会因时间变化而改变坐标,而变化速度是,所以是
那么我们可以考虑哪些已知线段是满足要求的。
对于每一条已知线段~,假设,那么要满足同理。
画成图的话(没有好的画图软件==,你自己画图可以理解得更好),能在的区域其实是一个不规则的平面区域,那么我们可以把它补全成一个平行四边形(我们用来补全的部分都是不包含点的部分,所以加上了也不会影响答案),问题就变成了询问这样一个平行四边形内有多少个
一个常见的技巧就是对其进行坐标变换,变成一个矩形之后就可以对其使用数据结构查询一个矩形内的和了(我用的二维树状数组),对于那些超界的部分我们要单独考虑。
还有一点要注意的就是当的时候,两边扩展出去的矩形的边界会重合,所以还要特判一下。
总之还是要膜现场大神。
bzoj1062.cpp

← bzoj1061:[Noi2008]志愿者招募 bzoj1063:[Noi2008]道路设计 →
 
comments powered by Disqus