• 在线算法与离线算法

  假设举办江大程序设计校赛时要提供代码打印服务，通常情况下并发请求量并不大。
  我们的系统每接收到一条打印请求，就立即响应并指示打印机打出代码，这就是在线算法的工作策略。
  但在关键时刻可能会有大量请求蜂拥而来，服务器临时“宕机”了一下不能立即回应；请求就在缓冲池里堆积了起来。管理员看不下去了，马上出手打印了一大叠代码纸。这就好比是另一种工作策略——离线算法。

接着举例说明在线/离线的不同工作方式对算法设计的影响。

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< 


单点更新与批量查询

区间更新与批量查询

• 计算当前扫描线上“进出”矩形的次数，乘上对应“事件”的边长。

/* 
 * File:   main.cpp
 * Author: semprathlon
 *
 * Created on April 26, 2016, 7:18 PM
 */

#include 
#include 
#include 
#include 
#include 

using namespace std;

struct Rectangle{
    int x1,y1,x2,y2;
    Rectangle(){}
    Rectangle(int _x1,int _y1,int _x2,int _y2):x1(_x1),x2(_x2),y1(_y1),y2(_y2){}
};

vector rects;

bool cmp(const int& a,const int& b){
    if (abs(a-b)<1e-5)
        return 0;
    return a-b<0;
}

int unionPerimeterY(const vector& rects){
    if (rects.empty()) return 0;
    typedef pair > Event;
    vector events;
    vector ys;
    for(int i=0;iy2) swap(y1,y2);
            sum[y1]+=delta;
            sum[y2]-=delta;
        
            int cnt=0,tmp=0;
            for(int j=0;j& rects){
    if (rects.empty()) return 0;
    typedef pair > Event;
    vector events;
    vector xs;
    for(int i=0;ix2) swap(x1,x2);
            sum[x1]+=delta;
            sum[x2]-=delta;
        
            int cnt=0,tmp=0;
            for(int j=0;j>n){
        if (!n) break;
        rects.clear();
        for(int i=0;i>x1>>y1>>x2>>y2;
            rects.push_back(Rectangle(x1,y1,x2,y2));
        }
        cout< 

• 应将线段树存储区间对应于矩形边的区段。

/*
 * File:   main.cpp
 * Author: semprathlon
 *
 * Created on April 9, 2016, 10:19 AM
 */

#include 
#include 
#include 
#include 
#include 

using namespace std;

struct Rectangle{
    double x1,y1,x2,y2;
    Rectangle(){}
    Rectangle(double _x1,double _y1,double _x2,double _y2):x1(_x1),x2(_x2),y1(_y1),y2(_y2){}
};

vector rects;
vector ys;

struct SegTree{
    SegTree *lchild,*rchild;
    int l,r,m;
    double s;
    int w;
    SegTree(){}
    SegTree(int _l,int _r):l(_l),r(_r){
        m=(l+r)>>1;w=0;s=0;
        if (l0)
        s=lchild->s+rchild->s;
    }
    void down(){
        if (w>0){
            lchild->w+=w;
            rchild->w+=w;
            if (lchild->w)
                lchild->s=ys[lchild->r+1]-ys[lchild->l];
            if (rchild->w)
                rchild->s=ys[rchild->r+1]-ys[rchild->l];
            s=w=0;
        }
    }
    void modify(int x,int y,int v){
        if (l==r){
            w+=v;
            if (w>0)
                s=ys[r+1]-ys[l];
            else
                s=0;
            return;
        }
        if (x==l&&r==y){
            w+=v;
            if (w>0){
                s=ys[r+1]-ys[l];
                return;
            }
            else
                s=0;
        }
        down();
        if (x<=m)
            lchild->modify(x,min(m,y),v);
        if (y>m)
            rchild->modify(max(m+1,x),y,v);
        up();
    }
    double query(int x,int y){
        //cout<<"q "<0?s:0;
        if (x==l&&r==y&&w>0){
            return s;
        }
        down();
        double res=0;
        if (x<=m) res+=lchild->query(x,min(m,y));
        if (y>m) res+=rchild->query(max(m+1,x),y);
        up();
        return res;
    }
} *T;

bool cmp(const double& a,const double& b){
    if (abs(a-b)<1e-5)
        return 0;
    return a-b<0;
}

double unionArea(const vector& rects){
    if (rects.empty()) return 0;
    typedef pair > Event;
    vector events;
    ys.clear();
    for(int i=0;i cnt(ys.size()-1,0);
    for(int i=0;iy2) swap(y1,y2);
        T->modify(y1,y2-1,delta);
        //for(int j=0;jquery(j,j);
            //cout<query(j,j)<query(0,ys.size()-2);
//        cout<>n){
        if (!n) break;
        rects.clear();
        for(int i=0;i>x1>>y1>>x2>>y2;
            rects.push_back(Rectangle(x1,y1,x2,y2));
        }
        cout<<"Test case #"<<++cas<