扫描线
思想
以一条法线从下往上扫描整个图形，图形面积并即为 \(\sum\limits_{i=1}^{n-1} len_i \times \left(h_{i+1}-h_i\right)\)，其中 \(len_i\) 为当前扫描线长度，\(h_k\) 为编号为 \(k\) 的线段的 \(y\) 坐标。
图示
如图：
\(\texttt{Step 1:}\)
从头开始扫。
\(\texttt{Step 2:}\)
扫到第二条，计算浅蓝色部分面积。
\(\texttt{Step 3-4}\)
扫描线当前长度可以用线段树优化（区间修改）。
动态开点
【例题】：HDU6183 - Color it！
题意：给出以下操作：
- \(\texttt{0}\)，代表清空所有颜色。
- \(\texttt{1 x y c}\) 代表在坐标 \((x,y)\) 涂上第 \(c\) 种颜色。
- \(\texttt{2 x y1 y2}\) 代表统计 \(x\) 轴上 \((1,x)\) 和 \(y\) 轴上 $ (y1,y2)$ 的颜色数，一个点可以有多种颜色.
- \(\texttt{3}\) 代表结束。
数据保证 \(n,m \le 10^6,0\ge c \le 50,y1 \le y2\)。
思路
开 \(50\) 棵线段树维护当前颜色 \(y\) 坐标上最小的 \(x\)，查询 \((x,y1,y2)\) 时，看那个颜色的线段树 \((y1,y2)\) 区间的值是否 \(\le x\) 即可。
因为空间会爆炸，所以不能常规开线段树，用到什么区间就开那个区间的内存即可。
可持久化线段树 / 主席树
主席树即为可持久化权值线段树，即在保留历史版本的前提下更新线段树，分析可得，修改的节点是一条链且必然产生新的根，未修改的连到过去版本即可。
使用动态开点。
大概长这样：
第 \(i\) 棵主席树保存的是离散化后 \([1,i]\) 出现的次数。
区间查询时，运用前缀和的思想确定左右区间，递归求解。
所有笔记的代码：
画图软件：
- \(\text{Microsoft Whiteboard}\)
编辑器：
- \(\text{CP Editor / Dev-C++}\)