• 在线算法与离线算法

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

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

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< 


单点更新与批量查询

区间更新与批量查询

Turing Tree

Time Limit: 6000/3000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)

Problem Description

After inventing Turing Tree, 3xian always felt boring when solving problems about intervals, because Turing Tree could easily have the solution. As well, wily 3xian made lots of new problems about intervals. So, today, this sick thing happens again…

Now given a sequence of N numbers A1, A2, …, AN and a number of Queries(i, j) (1≤i≤j≤N). For each Query(i, j), you are to caculate the sum of distinct values in the subsequence Ai, Ai+1, …, Aj.

Input

The first line is an integer T (1 ≤ T ≤ 10), indecating the number of testcases below.
For each case, the input format will be like this:

• Line 1: N (1 ≤ N ≤ 30,000).
• Line 2: N integers A1, A2, …, AN (0 ≤ Ai ≤ 1,000,000,000).
• Line 3: Q (1 ≤ Q ≤ 100,000), the number of Queries.
• Next Q lines: each line contains 2 integers i, j representing a Query (1 ≤ i ≤ j ≤ N).

Output

For each Query, print the sum of distinct values of the specified subsequence in one line.

Sample Input

2
3
1 1 4
2
1 2
2 3
5
1 1 2 1 3
3
1 5
2 4
3 5

Sample Output

1
5
6
3
6

Author

3xian@GDUT

• 离线化
• 从左到右处理原数列
• 对询问排序

不再是难题。

/* 
 * File:   main.cpp
 * Author: semprathlon
 *
 * Created on March 25, 2016, 4:02 PM
 */
#include 
#include 
#include 
#include 
#include 

这是一场炼狱般的较量。无心游玩，艰苦奋斗。

现场发挥	已解决题目
L - Huatuo’s Medicine	A - Secrete Master Plan
A - Secrete Master Plan	C - The Battle of Chibi
H - Sudoku	D - Pick The Sticks
D - Pick The Sticks(封榜后)	G - Ancient Go
H - Sudoku
Ranklist	L - Huatuo’s Medicine