• 在线算法与离线算法

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

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

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< 


单点更新与批量查询

区间更新与批量查询

• C++兼容C，但C++不是C的超集。

• gcc与Visual C++分别代表两种编译器套装，各自都包含C编译器和C++编译器。

• gcc或Visual C++都根据源代码文件的扩展名*.c/*.cpp选择语言，但评测时的语言选项并非如此。
  提交代码时如需选择语言或编译器，(GNU) gcc=C语言，g++=C++；
  (Microsoft) C=C语言，(Microsoft) C++=C++.

• 可以把C语言代码当做C++代码提交。

C语言标准	gcc编译选项
ANSI C(C89)	-ansi
C99	-std=c99
C11	-std=c11

评测环境、选项会在OJ、正式比赛的文件上说明。

• 64位整数的输入输出
  __int64类型只能在Visual C++中使用。
  long long的输入输出格式符为%I64d或%lld，会出错？
  unsigned long long的输入输出格式符为%I64u或%llu，会出错？

• 输入若干组数据？
  利用scanf函数的返回值。
  利用gets函数的返回值。

• 变量的内存空间分配

  静态区： 保存自动全局变量和 static 变量（包括 static 全局和局部变量）。静态区的内容在总个程序的生命周期内都存在，由编译器在编译的时候分配。

  堆： 由 malloc 系列函数或 new 操作符分配的内存，其生命周期由 free 或 delete 决定。在没有释放之前一直存在，直到程序结束，其特点是使用灵活，空间比较大，但容易出错

  栈： 保存局部变量，栈上的内容只在函数的范围内存在，当函数运行结束，这些内容也会自动被销毁，其特点是效率高，但空间大小有限

匆忙而简捷地办完了年度招新活动，实现了第一次JNUOJ线上赛。

• 搭建OJ时不能实现预期中的多服务器并行处理，但评测效率已满足需求

• VJ始终无法使用，不知原BNUOJ开发者是否会继续维护

• 命题未免太强调难度了

---

A. 篱笆和人

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

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

/* 
 * 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< 

Java Code Template By Semprathlon

• 部分理论知识引用自维基百科

Input 输入

An enhanced InputReader supporting keeping reading data until the end of input while the number of input cases is unknown:
一个加强版的输入器 ，支持读到输入文件末尾的方式，用法类似java.util.Scanner但效率显著提高:

#Grids

Time Limit: 10000/5000 MS (Java/Others)
Memory Limit: 65535/65535 K (Java/Others)

##Problem Description

　　度度熊最近很喜欢玩游戏。这一天他在纸上画了一个2行N列的长方形格子。他想把1到2N这些数依次放进去，但是为了使格子看起来优美，他想找到使每行每列都递增的方案。不过画了很久，他发现方案数实在是太多了。度度熊想知道，有多少种放数字的方法能满足上面的条件？

##Input

　　第一行为数据组数T(1< =T<=100000)。
　　然后T行，每行为一个数N(1< =N<=1000000)表示长方形的大小。

##Output

　　对于每组数据，输出符合题意的方案数。由于数字可能非常大，你只需要把最后的结果对1000000007取模即可。

##Sample Input

2
1
3

##Sample Output

Case #1:
1
Case #2:
5

##Hint

对于第二组样例，共5种方案，具体方案为：

##Source

2014年百度之星程序设计大赛 - 初赛（第一轮）

---

引用维基百科的解释：

Cn is the number of standard Young tableaux whose diagram is a 2-by-n rectangle. In other words, it is the number of ways the numbers 1, 2, …, 2n can be arranged in a 2-by-n rectangle so that each row and each column is increasing. As such, the formula can be derived as a special case of the hook-length formula.

• 除法取模运算、Catalan数计算依赖于不同的推导，分别有多种不同写法，分别有不同的时间复杂度表现。

/**
 * Apr 3, 2016 9:54:01 PM
 * PrjName: hdu4828
 * @semprathlon
 */

import java.io.*;
import java.util.*;

public class Main {
    final static int maxn = 1000010, mod = 1000000007;
    static long inv[] = new long[maxn];
    static long a[] = new long[maxn];
    static long b[] = new long[maxn];
    static long C[] = new long[maxn];
    static long x, y;

    static void extgcd(long a, long b) {
        if (b == 0L) {
            x = 1L;
            y = 0L;
            return;
        }
        extgcd(b, a % b);
        long t = x;
        x = y;
        y = t - a / b * y;
    }

    static void get_inv(int maxn, long mod) {
        inv[1] = 1;
        for (int i = 2; i < maxn; i++) {
            // inv[i] = (mod - mod / i) * inv[(int) (mod % i)] % mod;

            inv[i] = (int) cal_inv(i, mod);
        }
    }

    static long cal_inv(long n, long mod) {
        extgcd(n, mod);
        return x < 0L ? (x + mod) % mod : x % mod;
    }

    static long pow_mod(long n, long m, long mod) {
        long res = 1L;
        n %= mod;
        while (m > 0L) {
            if ((m & 1L) > 0L)
                res = res * n % mod;
            n = n * n % mod;
            m >>= 1;
        }
        return res;
    }

    static long div_mod(long n, long m, long mod) {
        // return n * pow_mod(m, mod - 2, mod) % mod;
        // return n * pow_mod(m, phi(mod) - 1, mod) % mod;
        return n * inv[(int) m] % mod;
    }

    static void get_Catalan(int maxn) {
        a[1] = 2;
        b[1] = 1;
        C[1] = 1;
        for (int i = 2; i < maxn - 1; i++) {
            /*
             * a[i] = a[i - 1] * ((i << 1) - 1) % mod * (i << 1) % mod; a[i] =
             * div_mod(a[i], i, mod); a[i] = div_mod(a[i], i, mod); b[i] = b[i -
             * 1] * ((i << 1) - 1) % mod * (i << 1) % mod; b[i] = div_mod(b[i],
             * i + 1, mod); b[i] = div_mod(b[i], i - 1, mod); C[i] = a[i] -
             * b[i]; if (C[i] < 0) C[i] += mod;
             */
            C[i] = C[i - 1] * ((i << 2) - 2) % mod;
            C[i] = div_mod(C[i], i + 1, mod);
        }
    }

    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        get_inv(maxn, mod);
        get_Catalan(maxn);
        int T = in.nextInt(), cas = 0;
        while (T-- > 0) {
            int n = in.nextInt();
            out.println("Case #" + (++cas) + ":");
            out.println(C[n]);
        }
        out.flush();
        out.close();
    }

}

GCD

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

Problem Description

Given 5 integers: a, b, c, d, k, you’re to find x in a…b, y in c…d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor of x and y. Since the number of choices may be very large, you’re only required to output the total number of different number pairs.
Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same.

You can assume that a = c = 1 in all test cases.

Input

The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 3,000 cases.
Each case contains five integers: a, b, c, d, k, 0 < a <= b <= 100,000, 0 < c <= d <= 100,000, 0 <= k <= 100,000, as described above.

Output

For each test case, print the number of choices. Use the format in the example.

Sample Input

2
1 3 1 5 1
1 11014 1 14409 9

Sample Output

Case 1: 9
Case 2: 736427

Hint

For the first sample input, all the 9 pairs of numbers are (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5).

• 莫比乌斯反演，可比容斥原理节省工作量。
• 所需寻找的二元组中i==j时，仅算1对。

import java.io.*;
import java.util.*;
public class Main {
    final static int maxn=100010;
    static int[] pri,phi,fstp,miu;
    static void get_prime(){
        pri=new int[maxn];
        fstp=new int[maxn];
        phi=new int[maxn];
        miu=new int[maxn];
        phi[1]=1;
        miu[1]=1;
        for(int i=2;i0){
            in.nextInt();
            int n=in.nextInt();
            in.nextInt();
            int m=in.nextInt();
            int k=in.nextInt();
            if (k==0){
                out.println("Case "+(++cas)+": 0");
                continue;
            }
            n/=k;m/=k;
            if (n>m){
                int t=n;n=m;m=t;
            }
            long ans=0;
            for(int i=1;i<=n;i++)
                ans-=(long)miu[i]*(n/i)*(n/i);
            ans/=2;
            for(int i=1;i<=n;i++)
                ans+=(long)miu[i]*(n/i)*(m/i);
            out.println("Case "+(++cas)+": "+ans);
        }
        out.flush();
        out.close();
    }

}

#Junk-Mail Filter

Time Limit: 15000/8000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)

##Problem Description

Recognizing junk mails is a tough task. The method used here consists of two steps:

1. Extract the common characteristics from the incoming email.
2. Use a filter matching the set of common characteristics extracted to determine whether the email is a spam.

   We want to extract the set of common characteristics from the N sample junk emails available at the moment, and thus having a handy data-analyzing tool would be helpful. The tool should support the following kinds of operations:

a) “M X Y”, meaning that we think that the characteristics of spam X and Y are the same. Note that the relationship defined here is transitive, so
relationships (other than the one between X and Y) need to be created if they are not present at the moment.

b) “S X”, meaning that we think spam X had been misidentified. Your tool should remove all relationships that spam X has when this command is received; after that, spam X will become an isolated node in the relationship graph.

Initially no relationships exist between any pair of the junk emails, so the number of distinct characteristics at that time is N.
Please help us keep track of any necessary information to solve our problem.

##Input

There are multiple test cases in the input file.
Each test case starts with two integers, N and M (1 ≤ N ≤ 10^5 , 1 ≤ M ≤ 10^6), the number of email samples and the number of operations. M lines follow, each line is one of the two formats described above.
Two successive test cases are separated by a blank line. A case with N = 0 and M = 0 indicates the end of the input file, and should not be processed by your program.

##Output

For each test case, please print a single integer, the number of distinct common characteristics, to the console. Follow the format as indicated in the sample below.

##Sample Input

5 6
M 0 1
M 1 2
M 1 3
S 1
M 1 2
S 3

3 1
M 1 2

0 0

##Sample Output

Case #1: 3
Case #2: 2

#Source

2008 Asia Regional Hangzhou

• 要删除结点时，原结点的编号作废但保留位置，再给该结点新分配一个“马甲”。

/**
 * Mar 28, 2016 8:25:14 PM
 * PrjName: fzu2155
 * @semprathlon
 */
import java.io.*;
import java.util.*;

public class Main {
    final static int maxn = 2000010;
    static int[] f = new int[maxn];
    static int[] g = new int[maxn];

    static int n, m, cnt;
    static Set st = new HashSet();

    static int getf(int x) {
        if (f[x] == x)
            return x;
        f[x] = getf(f[x]);
        return f[x];
    }

    static boolean unite(int x, int y) {
        int a = getf(g[x]);
        int b = getf(g[y]);
        if (a == b)
            return false;
        f[a] = b;
        return true;
    }

    static void init() {
        cnt = n;
        for (int i = 0; i < n + m; i++)
            f[i] = i;
        for (int i = 0; i < n; i++)
            g[i] = i;
    }

    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int cas = 0;
        while (in.nextLine() != null) {
            n = in.nextInt();
            m = in.nextInt();
            if (n == 0 && m == 0)
                break;
            init();
            for (int i = 1; i <= m; i++) {
                String s = in.next();
                if (s.charAt(0) == 'M') {
                    int x = in.nextInt();
                    int y = in.nextInt();
                    unite(x, y);
                } else if (s.charAt(0) == 'S') {
                    int x = in.nextInt();
                    g[x] = cnt++;
                }
            }
            st.clear();
            for (int i = 0; i < n; i++)
                st.add(getf(g[i]));

            out.println("Case #" + (++cas) + ": " + st.size());
        }
        out.flush();
        out.close();
    }

}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String nextLine() {
        String tmp = null;
        try {
            tmp = reader.readLine();
            tokenizer = new StringTokenizer(tmp);
        } catch (IOException e) {
            throw new RuntimeException(e);
        } catch (NullPointerException e) {
            return null;
        }
        return tmp;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}