Luogu6106 [Ynoi2010] Self Adjusting Top Tree

发表于 分类于 ， ， 阅读次数：

题意：给出平面上 条互不相交的线段，每次询问给出一个矩形，求线段与矩形的交的长度和。

，时限 。

扫描线经典题。

首先考虑所有斜率为正的线段。为负的那些只需翻转 坐标。

这是个求和问题，贡献可减，我们把所有的询问容斥成前缀矩形。

我们发现，此时所有的线段与矩形的位置关系只有四种情况：

  1. 相离
  2. 完全包含
  3. 与上边界相交
  4. 与右边界相交

对于完全包含的线段，充要条件是：右上端点在矩形内。这是个经典二维偏序。

然后我们就只需要考虑相交的情况。

对于与上边界相交的情况，我们可以翻转坐标系的两轴。这样就只用考虑与右边界相交。

题目给出了一个非常特殊的条件：所有线段不相交。

这就表明，如果我们拿一条竖着的直线直线切这些线段，并从左往右移动（扫描），所得的交点的顺序不会改变。（否则意味着线段相交）

所以，我们可以按照 坐标进行扫描线，用平衡树按照 坐标维护这些线段。

每次查询的时候，和矩形右边界相交的线段，在平衡树上一定是一个前缀区间。

我们来思考如何统计在右边界左边的总长度。

我们先解出每条线段向右经过一单位所得的长度是多少，称之为单位线长。

然后维护单位线长，和从左端点延长到左边界的线段长度和。

我们用单位线长的前缀和乘以边界的 坐标，就能得到整条线的长度和，再减去延长线长度总和即可。

如图：

需要手写平衡树，我选择写 Leafy-Tree。

复杂度 ，常数较大。