接着举例说明在线/离线的不同工作方式对算法设计的影响。
JNUOJ1150 线段覆盖
给出数轴上N条线段，每条线段用两个数表示A,B $ (-10^9 \leq A \lt B \leq 10^9) $ ，表示从a到b的一条线段。
现在请你求出它们覆盖数轴上的多长距离。
空间中各个点的状态记录与增量记录
这里有了个现成的数轴的概念，数轴是个一维空间，上面的各个位置具有被覆盖与不被覆盖两种状态。
一条线段具有左端点和右端点两个属性，对左右端点之间各个位置产生状态改变。
可以用一维数组记录（有需要知道的）各个位置的状态。考虑到同一个位置会被多条线段覆盖，那么修改增量（改变量）记录以便最终一次性更新。如果线段端点散步范围不大的话就这么做了。
可是散布范围太大了，不论是评测机还是编译器都不会接受$ 10^9 $规模的数组。
压缩空间
并不是$ 10^9 $个位置都成为端点，可以作端点的位置至多$ 2N $个。
要像制造“空间扭曲”一样缩短这个数轴，缩短遥远的端点之间的虚拟距离。
现在把各个端点按照顺序映射到更紧密的空间上，也就是给每个位置按顺序分配一个虚拟ID。
这样状态存储的空间就被压缩了，同时能够获知虚拟点之间的真实距离。
#include
#include
#include
const int maxn=1000010;
int l[maxn],r[maxn],delta[maxn*2];
std::vector list;
int main(){
int n;
while(std::cin>>n){
list.clear();
std::fill(delta,delta+maxn*2,0);
for(int i=0;i>l[i]>>r[i];
list.push_back(l[i]);
list.push_back(r[i]);
}
std::sort(list.begin(),list.end());
list.erase(std::unique(list.begin(),list.end()),list.end());
for(int i=0;i0)
ans+=(i?list[i]-list[i-1]:0);
cur+=delta[i];delta[i]=cur;
}
std::cout<
- 合并请求的离线化处理
以上记录增量是拐弯抹角的解法，接下来说明“实用”的处理思路。
线段跟线段肯定是有办法合并的，尽量把能合并的线段合成一条后取长度。
每一轮合理的合并处理，可以从最左侧一条线段开始，向右逐个拼合，直到不能合并为止，取长度。反复进行这样的几轮处理。
const int maxn=1000010;
std::pair seg[maxn];
int main(){
int n;
while(std::cin>>n){
for(int i=0; i>l>>r;
seg[i]=std::make_pair(l,r);
}
std::sort(seg,seg+n);
int ans=0,l=seg[0].first,r=seg[0].second;
for(int i=0; i
一维线性的问题可以拓展到二维平面上，长度被面积代替。
JNUOJ1147 Atlantis
已知平面上n个矩形，每个矩形用左上角、右下角的坐标确定，求合并后的总面积。
- 降维思路
说的是二维，其实还是一维问题。矩形宽度（横向）视作线段宽度，高度（纵向）视作附加参数。
线段仍然拆分成左右端点，不过引入新的概念，改叫左事件、右事件。
- 步步为营
扫描线每到一处，就生成并处理该处平行于扫描线方向上的一系列事件。
struct Rectangle{
double x1,y1,x2,y2;
Rectangle(double _x1,double _y1,double _x2,double _y2):x1(_x1),x2(_x2),y1(_y1),y2(_y2) {}
};
//通过左上角、右下角的坐标确定一个矩形
vector rects;
vector ylist;
double unionArea(const vector& rects,vector& ylist){
if (rects.empty()) return 0;
typedef pair > Event;
vector events;
ylist.clear();
for(int i=0; i cnt(ylist.size()-1,0);
//处理事件
for(int i=0; i0)
cutLength+=ylist[j+1]-ylist[j];
res+=cutLength*(events[i+1].first-events[i].first);//乘上宽度值，得到面积
}
return res;
}
int main(int argc, char** argv){
ios::sync_with_stdio(false);
cout.setf(ios::fixed,ios::floatfield);
cout.precision(2);
//设置实数输出格式
int n,cas=0;
while((cin>>n),n){
rects.clear();
for(int i=0; i>x1>>y1>>x2>>y2;
rects.push_back(Rectangle(x1,y1,x2,y2));
}
cout<<"Test case #"<<++cas<