RMQ 区间最值问题

问题描述

对于长度为n的序列A，回答若干(q次)询问RMQ(A, i, j)。

RMQ(A, i, j)需要返回序列由A[i]、A[j]为端点，所构成的A的子段中的最大值。

可参考 [牛客 NC50443]

部分方法实现于这个 工具类 。

多数源码的run方法细节被隐藏，需要完整可执行程序可直接跳转至 标准 RMQ。

如若出现如 $<O_1，O_2>$ 这样的表达式，其意义是算法的预处理时间复杂度为 $O_1$，单次查询时间复杂度为 $O_2$。

朴素算法

public class Main { 
         public int RMQ(int[] A, int i, int j) { 
         int ans = Integer.MIN_VALUE; while (i <= j) ans = Math.max(ans, A[i++]); return ans; } } 

$<O(0)，O(|i-j|)>$

暴力的不谈。

线段树

public class Main { 
           public class RMQ { 
           Node root; RMQ(int[] A) { 
           this.root = building(A, 0, A.length - 1); } public int query(int i, int j) { 
           return query(root, i, j); } public int query(Node root, int start, int end) { 
           if (start <= root.start && end >= root.end) return root.val; int res = 0x, mid = root.start + root.end >> 1; if (start <= mid) res = query(root.left, start, end); if (end > mid) res = max(res, query(root.right, start, end)); return res; } private Node building(int A[], int start, int end) { 
           if (start == end) return new Node(end, end, A[end]); Node node = new Node(start, end); node.left = building(A, start, start + end >> 1); node.right = building(A, start + end + 2 >> 1, end); return node.fresh(); } private class Node { 
           int val, start, end; Node left, right; Node(int start, int end) { 
           this.start = start; this.end = end; } Node(int start, int end, int val) { 
           this.start = start; this.end = end; this.val = val; } Node fresh() { 
           this.val = max(getValue(this.left), getValue(this.right)); return this; } private int getValue(Node node) { 
           return node == null ? Integer.MIN_VALUE: node.val; } } } } 

$<O(n\log n)，O(\log n)>$

纯纯的模板，不谈。

单调栈

注意：这是个 离线 算法。

以序列A、查询Q为例：

我们将Q按右端点升序排列，遍历A，同时维护单调栈。

当遍历到的元素和待查询Q的右端点相同时，进行查询。

 forA[2]inA：

RMQ(2, 2) = 3，因为A[1]的下标越过了Q的左端点。

 —————–

 forA[4]inA：

RMQ(0, 4) = 7

 —————–

 forA[5]inA：

RMQ(3, 5) = 5，因为A[1]的下标越过了Q的左端点。

在这里，栈内元素也可以表示另一层含义。

以完成遍历后栈的状态来表述：

栈底元素A[1]代表原序列A[0, 1]的最大值。
栈顶元素A[5]代表原序列A[2, 5]的最大值。

正因如此，在完全压入查询子段包含的全部元素后，我们可以自底查找第一个映射原序列下标大于等于查询左端点的元素，这个元素就是子段的最值。

import java.util.*; public class Main { 
             public static void main(String[] args) { 
             new Main().run(); } public void run() { 
             answer = RMQ.of(A, Q); } public static class RMQ { 
             public static int[] of(int[] A, List<Query> Q) { 
             Queue<IndexQuery> query = new PriorityQueue(); int N = A.length, M = Q.size(); int[] stack = new int[N + 1]; int[] answer = new int[M]; for (int i = 0; i < M; i++) query.add(new IndexQuery(i, Q.get(i))); for (int i = 0, top = 0; i < N; i++) { 
             while (top > 0 && A[stack[top]] <= A[i]) top--; stack[++top] = i; if (query.isEmpty()) return answer; else while (!query.isEmpty() && query.peek().j == i) { 
             IndexQuery now = query.poll(); answer[now.index] = A[stack[lowerBound(stack, 1, top - 1, now.i)]]; } } return answer; } private static int lowerBound(int[] A, int start, int length, int key) { 
             while (length > 0) { 
             int half = length >> 1; if (key > A[start + half]) { 
             start += half + 1; length -= half + 1; } else length = half; } return start; } public static class Query { 
             int i, j; Query(int i, int j) { 
             this.i = i; this.j = j; } } private static class IndexQuery implements Comparable<IndexQuery> { 
             int index, i, j; IndexQuery(int index, Query query) { 
             this.index = index; if (query.i <= query.j) { 
             this.i = query.i; this.j = query.j; } else { 
             this.i = query.j; this.j = query.i; } } @Override public int compareTo(IndexQuery o) { 
             return this.j > o.j ? 1 : -1; } } } } 

虽然栈内每个元素最多进出一次，也就是我们整个栈的维护能在线性时间内完成，

但根据上述例子我们可以看到，自底向上查找时，我们会频繁的扫描“赖在”栈底的元素，当原序列A单调递减，且查询区间长度均摊为1时，就算查询是均匀分布的，整个查询操作的复杂度可能会达到 $O(n^2)$，最差情况下会将至$O(qn)$。

为了避免极端情况下，算法的性能得不到保障，推荐将该查找步骤采用二分查找的方式实现。

$<O(q\log qn)，O(0)>$

万用结构单调栈。

稀疏表

_{Sparse Table}

对于一个查询：

我们总是能用一个长度为2^K的区间、或将两个长度为2^k的区间叠加，来完全覆盖它。

如图所示，我们能将长度为5的子段查询规格化为两个长度为2^2的子段的子查询，

而长度为2^2的查询我们又能规划化为两个2^1的查询，

直至查询对应原序列单个元素。

也就是说，对于任意查询，我们都能化为：$$RMQ(i，j)=\max (RMQ(i，i+2^k)，RMQ(j-2^k，j))，k=\lfloor {\log }_2(j-i)\rfloor$$查询的速度，直接和查询长度为二的幂的子段的速度挂钩。

这里我们需要定义一下稀疏表所用到的ST的含义：

ST[i][k]指以i为左端点、长度为2^k的子段的最大值。

即 $ST[i][k]=\max (A[i，i+2^k))$。

由此我们很容易得出ST[i][0] = A[i]。

此外我们再给出一个倍增公式：$$ST[i][k]=\max (ST[i][k-1]，ST[i+2^{k-1}][k-1])，k\ge 1$$它能让我们在 $O(n\log n)$ 的时间复杂度下，完成长度为二的幂的子段的最值查询的初始化。

但同时，它也需要有 $O(n\log n)$ 的空间来存放预处理出的结果。

public class Main { 
               public static void main(String[] args) { 
               new Main().run(); } public void run() { 
               r = RMQ.of(A); r.query(i, j); } public static class RMQ { 
               public static RMQ of(int[] A) { 
               return new RMQ(A); } public int query(int i, int j) { 
               if (i > j) return query(j, i); int k = floorLog2(j - i); return max(ST[i][k], ST[j - (1 << k) + 1][k]); } private int[][] ST; RMQ(int[] A) { 
               int N = A.length, M = floorLog2(N); ST = new int[N][M + 1]; for (int i = 0; i < N; i++) ST[i][0] = A[i]; for (int k = 1; k <= M; k++) for (int i = 0; i + (1 << k - 1) < N; i++) ST[i][k] = max(ST[i][k - 1], ST[i + (1 << k - 1)][k - 1]); } } } 

稀疏表在处理RMQ问题时有点像动态规划，论其本质是倍增思想，也有叫什么逆二分、ST算法的。

稀疏表，它稀疏就稀疏在，预处理的问题并不是问题的全集，但预处理出的问题可以以极小的代价组合出问题的全集。

总之，好用。

$<O(n\log n)，O(1)>$

四毛子算法

_{Method of Four Russians}

相较于算法，它更像是一种思想，暴力分块思想。

拿稀疏表举例：

对于一个长度为N的序列A，我们将其分成长度为K的M块，并以长度为K的块为最小单元做倍增。

不难发现其时间复杂化度为 $O(\frac{K}{N}\log \frac{K}{N})$，我们取 $K=\frac{\log N}{2}$。此时 “块” 的稀疏表的初始化显然能在 $O(N)$ 的复杂度下完成。

对于块间的查询，现在我们能在 $<O(n)，O(1)>$ 的意义下完成。

这也是下面将要介绍的两个算法的理论依据。

那么现在的问题就是，查询发生在块内怎么办？

约束 RMQ

也有人称其为 $\pm 1RMQ$。

若长度为N序列A满足对任意 $i\in (2，N]$，都有 $\left|A_i-A_{i-1}\right|=1$，那么我们称其为约束序列。

那么对于约束序列的区间最值问题，我们称为约束RMQ。

由于约束序列的特殊性质，我们可以在不需要每个元素具体的值的情况，以很小的代价来表述它们的大小关系。

对于约束序列

我们不关心每个元素的具体值，只把注意力放在元素与其左元素的差值上，并直接忽略掉左端点元素，我们用 $1/0$ 表示 $A_i-A_{i-1}=1/-1$，并将其按二进制位从底到高保存到整形变量block当中。

于是对于上述序列A，我们有状态block = 0。

现在我们可以假设原序列左端点为任意值，例如将其设为0，再按block描述的大小关系将其重构，于是能得到序列

构建出的序列的区间最值与原序列的区间最值的位置一一映射(只要你对于最值出现多个的情况采取相同的措施)。

对于这样的序列，我们朴素的去枚举它的区间最值情况，时间复杂度在 $O(K^2)$ 即 $O(\frac{{\log }^{{}_2}N}{4})$，可能的block一共存在有 $2^{K-1}$ 种，枚举所以可能的block时间复杂度在 $O(\frac{\sqrt{2^{\log N-2}}{\log }^{{}_2}N}{4})$，整理可得知，对于块间查询的预处理，我们能在 $O(n)$ 意义下的时间复杂度下完成。

public class Main { 
                   public static void main(String[] args) { 
                   new Main().run(); } public void run() { 
                   rmq = PlusOrMinusOneRMQ .of(A); } public static class PlusOrMinusOneRMQ { 
                   int N, M, K; int[][] ST; int[][][] F; int[] A, block; public static PlusOrMinusOneRMQ of(int[] A) { 
                   return new PlusOrMinusOneRMQ.of(A, 0.5); } public static PlusOrMinusOneRMQ of(int[] A, double xK) { 
                   return new PlusOrMinusOneRMQ(A, xK); } PlusOrMinusOneRMQ(int[] A, double xK) { 
                   this.N = A.length; this.K = max(1, (int)(floorLog2(N) * xK)); this.M = N / K; if (N % K > 0) M++; block = new int[M]; F = new int[1 << K - 1][K][K]; ST = new int[M][floorLog2(M) + 1]; this.A = A; init(); } public int query(int i, int j) { 
                   if (i > j) return query(j, i); int B1 = i / K, B2 = j / K; int O1 = i % K, O2 = j % K; if (B1 == B2) return B1 * K + F[block[B1]][O1][O2]; int LM = F[block[B1]][O1][K - 1] + B1 * K, RM = F[block[B2]][0][O2] + B2 * K; int res = A[LM] < A[RM] ? LM : RM; if (B2 - B1 > 1) { 
                   int k = floorLog2(B2 - B1 - 1); int MLM = ST[B1 + 1][k], MRM = ST[B2 - (1 << k)][k]; int ans = A[MLM] < A[MRM] ? MLM : MRM; if (A[ans] < A[res]) res = ans; } return res; } private void init() { 
                   int min, now, block, offset; for (int i = 0; i < M; i++) { 
                   min = offset = i * K; block = 0; for (int k = 1; k < K && offset + k < N; k++) if (A[offset + k] < A[offset + k - 1]) { 
                   block |= 1 << k - 1; if (A[offset + k] < A[min]) min = offset + k; } this.block[i] = block; this.ST[i][0] = min; } for (int k = 1; k <= floorLog2(M); k++) for (int i = 0; i + (1 << k - 1) < M; i++) ST[i][k] = A[ST[i][k - 1]] < A[ST[i + (1 << k - 1)][k - 1]] ? ST[i][k - 1] : ST[i + (1 << k - 1)][k - 1]; for (int k = 0, m = 1 << K - 1; k < m; k++) for (int i = 0; i < K; i++) { 
                   F[k][i][i] = i; now = 0; min = 0; for (int j = i + 1; j < K; j++) { 
                   F[k][i][j] = F[k][i][j - 1]; if ((k & (1 << j - 1)) == 0) now++; else if (min > --now) { 
                   F[k][i][j] = j; min = now; } } } } } } 

因为看到有人说 $K=\log N\ast 1.5$ 算法的常数会更小。

在PlusOrMinusOneRMQ的构造方法中，设计了一个入参xK，用来控制K的系数。

建议范围 0.5 – 1. 5。

$<O(n)，O(1)>$

状压 RMQ

现在我们使用过单调栈求解了RMQ问题，又得知一个隐性条件 $K\le 64$，那么我们是否能将其结合起来，设计出一个高效的算法呢。

在使用单调栈求解RMQ时，不难发现，栈元素能自底向上构成原序列的子序列，也就是栈内元素对应原序列的下标是呈单调的，并且对于块间在最坏情况下，栈内元素不会多于 $64$。

综上，我们只用一个整形变量，就可以把块内遍历到某一元素的单调栈的状态压缩，在查询时，根据栈的状态返回结果。

对于单调栈的维护，显然能在 $O(n)$ 的复杂度下完成，对于根据状态的查询，通过一套不依赖输入的位运算，也可以做到在 $O(1)$ 复杂度的意义下完成。

还是以单调栈时所用数据为例，对于序列A的查询Q，需要对状态还原到如下栈：

枚举遍历A的元素时，我们将序列A的元素下标与整形二进制表示下低到高位相对应，当元素在栈内时，使当前位置 $1$，反之置 $0$，于是有状态序列

对于查询RMQ(2, 2)，我们将B[2]的低2位置0，此时从低位起，第一个1的位置，就映射着RMQ(2, 2)要查询到的结果的位置，即000100b的第2位。

对于查询RMQ(0, 4)，B[4]第一个1的位置，就映射着RMQ(0, 4)要查询到的结果的位置，即011010b的第1位。

对于查询RMQ(3, 5)，我们将B[5]的低3位置0，此时从低位起，第一个1的位置，就映射着RMQ(2, 2)要查询到的结果的位置，即b的第5位。

这个过程和单调栈查询的过程如出一辙，不过在这里，我们用了极小的代价保存了全部的栈状态，这也使得算法可以在线完成。

public class Main { 
                       public static class RMQ { 
                       int N, K; int[] A, B; int[][] ST; public static RMQ of(int[] A) { 
                       return RMQ.of(A, 0.5); }; public static RMQ of(int[] A, double xK) { 
                       return new RMQ(A, xK); }; RMQ(int[] A, double xK) { 
                       this.A = A; this.N = A.length; this.K = max(1, (int)(floorLog2(N) * xK)); int n = N / K + (N % K == 0 ? 0 : 1); ST = new int[n][floorLog2(n) + 1]; B = new int[N]; init(); } public int query(int i, int j) { 
                       if (i > j) return query(j, i); int ans = Integer.MIN_VALUE; int Si = i / K, Sj = j / K; if (Si == Sj) return A[i + countTrailingZero(B[j] >> i % K)]; if (Sj - Si > 1) { 
                       int k = floorLog2(Sj - Si - 1); ans = max(ST[Si + 1][k], ST[Sj - (1 << k)][k]); } return max( ans, A[Sj * K + countTrailingZero(B[j])], A[i + countTrailingZero(B[Si * K + K - 1] >> i % K)] ); } private void init() { 
                       int[] stack = new int[K + 1]; int top = 0, c = 0; for (int i = 0, k = 0; i < N; k = 0, top = 0) { 
                       while (k++ < K && i < N) { 
                       if (i > 0) B[i] = B[i - 1]; if (k == 1) B[i] = 0; while (top > 0 && A[i] > A[stack[top]]) B[i] ^= 1 << stack[top--] % K; stack[++top] = i; B[i++] |= 1 << k - 1; } ST[c++][0] = A[stack[1]]; } for (int k = 1; k <= floorLog2(ST.length); k++) for (int i = 0; i + (1 << k - 1) < ST.length; i++) ST[i][k] = max(ST[i][k - 1], ST[i + (1 << k - 1)][k - 1]); } } } 

对于上述根据状态查找的操作，我们可以通过一套计算量较小的方式解决。

首先对于低left位置0，低left位的值是不确定的，但left自身是已经给出的。

所以我们可以转为查询B[right] >> left的结果，在拿到结果后加上left的值。

而对于查找lowBit所在的位置，我们可以用 ${\log }_2(B_r\&-B_r)$ 的方式取得。

此时，压力来到了对数运算这边。

具体的更多细节请移步 countTrailingZero。

$<O(n)，O(1)>$

笛卡尔树

它具有堆的有序性，中序遍历可以输出原数列。

对于这样一棵树，我们要求它的每个节点由键值对 $(i，v)$ 组成，要求 $i(元素下标)$ 满足二叉搜索树性质、$v(元素值)$ 满足堆性质。

更进一步讲，给定一个长度为 $N$ 序列 $A$，找到其最值 $A_k$，将其设为根节点，再将序列拆分成 $A^{\prime }=A_1\sim A_{k-1}$ 、$A^{\prime \prime }=A_{k+1}\sim A_N$两段，将 $A_k$ 的左子树设为由 $A^{\prime }$ 迭代此过程的二叉树，将 $A_k$ 的右子树设为由 $A^{\prime \prime }$ 迭代此过程的二叉树，如此这般，我们便拿到了由序列 $A$ 构成的笛卡尔树。

由于我们没有改变元素位置，也就是在中序遍历下，元素的下标是还是按原序列递增的，因此 $keyi$ 满足二叉搜索树性质，又根节点总是子树(段)的最值，因此 $valuev$ 满足堆性质。

根据序列构建一棵笛卡尔树可以在线性时间内完成，我们使用单调栈维护树的堆性质，同时我们需要缓存堆顶弹出的元素来维护树的二叉搜索性质。

for (int i = 0; i < N; i++) { 
                         k = top; while (k > 0 && A[i] > A[stack[k]]) k--; if (k > 0) right[stack[k]] = i; if (k < top) left[i] = stack[k + 1]; stack[++k] = i; top = k; } 

需要注意的是，使用单调栈构建笛卡尔树，栈内元素的右子树的引用通常是会频繁变动的。

因此这里推荐使用数组暂存子树引用，而不是直接建边。

标准 RMQ

_{先规约成LCA 再规约成约束RMQ}

对于序列 $A$，我们构建出笛卡尔树 $T$，根据笛卡尔树的堆性质，区间最大值问题就能在线性时间内转为树上最近公共祖先问题。

代码量很大，这里就把完整代码放出来算了。

import java.io.InputStream; import java.io.IOException; import java.io.PrintWriter; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.Collection; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Main { 
                           public static void main(String[] args) { 
                           new Main().run(); } public void run() { 
                           InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); int N = in.readInt(), M = in.readInt(); int[] A = new int[N + 1]; for (int i = 1; i <= N; i++) A[i] = in.readInt(); RMQ r = RMQ.of(A); while (M-- > 0) out.println(r.query(in.readInt(), in.readInt())); out.flush(); } public static class RMQ { 
                           private int[] A; private LCA lca; public static RMQ of(int[] A) { 
                           return new RMQ(A); } RMQ(int[] A) { 
                           List<Edge> edges = new ArrayList(); int N = A.length; int top = 0, k; int[] left = new int[N]; int[] right = new int[N]; Arrays.fill(left, -1); Arrays.fill(right, - 1); int[] stack = new int[N + 1]; for (int i = 0; i < N; i++) { 
                           k = top; while (k > 0 && A[i] > A[stack[k]]) k--; if (k > 0) right[stack[k]] = i; if (k < top) left[i] = stack[k + 1]; stack[++k] = i; top = k; } for (int i = 0; i < N; i++) { 
                           if (left[i] != -1) edges.add(new Edge(i, left[i])); if (right[i] != -1) edges.add(new Edge(i, right[i])); } lca = new LCA(N, stack[1], edges); this.A = A; } public int query(int i, int j) { 
                           return A[lca.query(i, j)]; } private class Edge { 
                           int v, w; Edge(int v, int w) { 
                           this.v = v; this.w = w; } } private class LCA { 
                           private int clock; private PlusOrMinusOneRMQ rmq; private int[] table, euler, stamp; LCA(int N, int root, Collection<Edge> edges) { 
                           int M = edges.size(); table = new int[N + 1]; euler = new int[(M + 1 << 1) - 1]; stamp = new int[(M + 1 << 1) - 1]; List<Integer>[] graph = new List[N + 1]; for (int i = 0; i <= N; i++) graph[i] = new ArrayList(); for (Edge edge : edges) { 
                           graph[edge.v].add(edge.w); graph[edge.w].add(edge.v); } clock = 0; dfs(graph, root, root, 0); rmq = new PlusOrMinusOneRMQ(stamp); } public int query(int i, int j) { 
                           return euler[rmq.query(table[i], table[j])]; } void dfs(List<Integer>[] graph, int v, int fa, int depth) { 
                           table[v] = clock; euler[clock] = v; stamp[clock++] = depth; for (int w : graph[v]) { 
                           if (w == fa) continue; dfs(graph, w, v, depth + 1); euler[clock] = v; stamp[clock++] = depth; } } private class PlusOrMinusOneRMQ { 
                           int N, M, K; int[][] ST; int[][][] F; int[] A, block; PlusOrMinusOneRMQ(int[] A) { 
                           this(A, 0.5); } PlusOrMinusOneRMQ(int[] A, double xK) { 
                           this.N = A.length; this.K = max(1, (int)(floorLog2(N) * xK)); this.M = N / K; if (N % K > 0) M++; block = new int[M]; F = new int[1 << K - 1][K][K]; ST = new int[M][floorLog2(M) + 1]; this.A = A; init(); } public int query(int i, int j) { 
                           if (i > j) return query(j, i); int B1 = i / K, B2 = j / K; int O1 = i % K, O2 = j % K; if (B1 == B2) return B1 * K + F[block[B1]][O1][O2]; int LM = F[block[B1]][O1][K - 1] + B1 * K, RM = F[block[B2]][0][O2] + B2 * K; int res = A[LM] < A[RM] ? LM : RM; if (B2 - B1 > 1) { 
                           int k = floorLog2(B2 - B1 - 1); int MLM = ST[B1 + 1][k], MRM = ST[B2 - (1 << k)][k]; int ans = A[MLM] < A[MRM] ? MLM : MRM; if (A[ans] < A[res]) res = ans; } return res; } private void init() { 
                           int min, now, block, offset; for (int i = 0; i < M; i++) { 
                           min = offset = i * K; block = 0; for (int k = 1; k < K && offset + k < N; k++) if (A[offset + k] < A[offset + k - 1]) { 
                           block |= 1 << k - 1; if (A[offset + k] < A[min]) min = offset + k; } this.block[i] = block; this.ST[i][0] = min; } for (int k = 1; k <= floorLog2(M); k++) for (int i = 0; i + (1 << k - 1) < M; i++) ST[i][k] = A[ST[i][k - 1]] < A[ST[i + (1 << k - 1)][k - 1]] ? ST[i][k - 1] : ST[i + (1 << k - 1)][k - 1]; for (int k = 0, m = 1 << K - 1; k < m; k++) for (int i = 0; i < K; i++) { 
                           F[k][i][i] = i; now = 0; min = 0; for (int j = i + 1; j < K; j++) { 
                           F[k][i][j] = F[k][i][j - 1]; if ((k & (1 << j - 1)) == 0) now++; else if (min > --now) { 
                           F[k][i][j] = j; min = now; } } } } } } } static int[] FLOOR_LOG2_TABLE = { 
                           0, 0, 1, 26, 2, 23, 27, 32, 3, 16, 24, 30, 28, 11, 33, 13, 4, 7, 17, 35, 25, 22, 31, 15, 29, 10, 12, 6, 34, 21, 14, 9, 5, 20, 8, 19, 18 }; public static int floorLog2(int a) { 
                           return FLOOR_LOG2_TABLE[highBit(a) % 37]; } public static int highBit(int a) { 
                           a |= a >> 1; a |= a >> 2; a |= a >> 4; a |= a >> 8; a |= a >> 16; return a - (a >>> 1); } public static int max(int a, int b) { 
                           return a > b ? a : b; } public class InputReader { 
                           BufferedReader reader; StringTokenizer token; InputReader(InputStream in) { 
                           this.reader = new BufferedReader(new InputStreamReader(in)); } String read() { 
                           while (token == null || !token.hasMoreTokens()) { 
                           try { 
                           token = new StringTokenizer(reader.readLine()); } catch (IOException e) { 
                           e.printStackTrace(); } } return token.nextToken(); } int readInt() { 
                           return Integer.parseInt(read()); } } } 

洋洋洒洒二百行

THE END