1. 前言

線段樹系列文章：

• 線段樹學習筆記。
• 線段樹學習筆記 - 練習題（1）。

前一篇做了幾道線段樹的題目，這篇文章就繼續看下線段樹的相關題目，還是一樣，學習視頻：算法講解112【擴展】線段樹專題3-線段樹維護更多類型的信息，題目都是左神視頻上的，思路也可以看這個視頻。

2. P3870 [TJOI2009] 開關

P3870 [TJOI2009] 開關。

題目描述

現有 $n$ 盞燈排成一排，從左到右依次編號為：$1$，$2$，……，$n$。然后依次執行 $m$ 項操作。

操作分為兩種：

1. 指定一個區間 $[a,b]$，然后改變編號在這個區間內的燈的狀態（把開著的燈關上，關著的燈打開）；
2. 指定一個區間 $[a,b]$，要求你輸出這個區間內有多少盞燈是打開的。

燈在初始時都是關著的。

輸入格式

第一行有兩個整數 $n$ 和 $m$，分別表示燈的數目和操作的數目。

接下來有 $m$ 行，每行有三個整數，依次為：$c$、$a$、$b$。其中 $c$ 表示操作的種類。

• 當 $c$ 的值為 $0$ 時，表示是第一種操作。
• 當 $c$ 的值為 $1$ 時，表示是第二種操作。

$a$ 和 $b$ 則分別表示了操作區間的左右邊界。

輸出格式

每當遇到第二種操作時，輸出一行，包含一個整數，表示此時在查詢的區間中打開的燈的數目。

輸入輸出樣例 #1

輸入 #1

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

輸出 #1

1
2

說明/提示

數據規模與約定

對于全部的測試點，保證 $2\le n\le 10^5$，$1\le m\le 10^5$，$1\le a,b\le n$，c∈{0,1}c\in\{0,1\}c∈{0,1}。

思路：

這道題就是范圍重置和范圍查詢，初始值為 0 表示燈是關上的，1 表示燈打開了，其實就是范圍重置維護累加和，那么如果到了一個范圍能不能在 O(1) 時間內懶更新完這個范圍的累加和呢？答案是可以的，比如這個范圍長度是 n，假設現在 light[i] = m，那么翻轉過后 light[i] = n - m，所以是可以 O(1) 時間懶更新的，下面看下 code。

import java.io.*;public class Main {public static int MAXN = 100001;public static int[] light = new int[MAXN << 2];// 懶更新數組, 如果為 true 就表示這個范圍內的值要翻轉了public static boolean[] reverse = new boolean[MAXN << 2];public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int n = (int) in.nval;in.nextToken();int m = (int) in.nval;build(1, n, 1);for (int i = 1, op, jobl, jobr; i <= m; i++) {in.nextToken();op = (int) in.nval;in.nextToken();jobl = (int) in.nval;in.nextToken();jobr = (int) in.nval;if (op == 0) {reverse(jobl, jobr, 1, n, 1);} else {out.println(query(jobl, jobr, 1, n, 1));}}out.flush();out.close();br.close();}private static int query(int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {return light[i];} else {int ans = 0;int mid = l + ((r - l) >> 1);down(i, mid - l + 1, r - mid);if (jobl <= mid) {ans += query(jobl, jobr, l, mid, i << 1);}if (jobr > mid) {ans += query(jobl, jobr, mid + 1, r, i << 1 | 1);}return ans;}}private static void reverse(int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {lazy(i, r - l + 1);} else {int mid = l + ((r - l) >> 1);down(i, mid - l + 1, r - mid);if (jobl <= mid) {reverse(jobl, jobr, l, mid, i << 1);}if (jobr > mid) {reverse(jobl, jobr, mid + 1, r, i << 1 | 1);}up(i);}}private static void down(int i, int ln, int rn) {if (reverse[i]) {lazy(i << 1, ln);lazy(i << 1 | 1, rn);reverse[i] = false;}}private static void lazy(int i, int n) {light[i] = n - light[i];// 假設子數組是 true, 那么再次翻轉就是 !reverse[i]// 不能直接設置為 falsereverse[i] = !reverse[i];}private static void build(int l, int r, int i) {if (l == r) {light[i] = 0;} else {int mid = l + ((r - l) >> 1);build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);up(i);}reverse[i] = false;}private static void up(int i) {light[i] = light[i << 1] + light[i << 1 | 1];}
}

3. P2184 貪婪大陸

P2184 貪婪大陸。

題目背景

面對螞蟻們的瘋狂進攻，小 FF 的 Tower defence 宣告失敗……人類被螞蟻們逼到了 Greed Island 上的一個海灣。現在，小 FF 的后方是一望無際的大海，前方是變異了的超級螞蟻。小 FF 還有大好前程，他可不想命喪于此， 于是他派遣手下最后一批改造 SCV 布置地雷以阻擋螞蟻們的進攻。

題目描述

小 FF 最后一道防線是一條長度為 $n$ 的戰壕，小 FF 擁有無數多種地雷，而 SCV 每次可以在 $[L,R]$ 區間埋放同一種不同于之前已經埋放的地雷。由于情況已經十萬火急，小 FF 在某些時候可能會詢問你在 $[L^{\prime },R^{\prime }]$ 區間內有多少種不同的地雷，他希望你能盡快的給予答復。

輸入格式

第一行為兩個整數 $n$ 和 $m$，$n$ 表示防線長度，$m$ 表示 SCV 布雷次數及小 FF 詢問的次數總和。

接下來有 $m$ 行，每行三個整數 $q,l,r$：

• 若 $q=1$，則表示 SCV 在 $[l,r]$ 這段區間布上一種地雷；
• 若 $q=2$，則表示小 FF 詢問當前 $[l,r]$ 區間總共有多少種地雷。

輸出格式

對于小 FF 的每次詢問，輸出一個答案（單獨一行），表示當前區間地雷總數。

輸入輸出樣例 #1

輸入 #1

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

輸出 #1

1
2

說明/提示

數據規模與約定

• 對于 $30\%$ 的數據，$0\le n$，$m\le 1000$。
• 對于 $100\%$ 的數據，$0\le n$，$m\le 10^5$。

思路：

這道題就是兩個操作，放地雷和查地雷數，注意這里就不是范圍更新了，比如 [1，4] 區間現在放了地雷 1，[3，6] 區間放了地雷 2，那么最終 [3，4] 區間地雷數就是 2，也就是說地雷數是疊加的，而不是被覆蓋的關系。

那么能不能每一次都區間 + 1 然后維護最大值呢，這樣是可以表示這個區間的地雷數，但是最后查詢的時候還是沒辦法查出來總的地雷數。還是上面的例子，比如 [1，4] 區間現在放了地雷 1，[3，6] 區間放了地雷 2，[2，2] 區間放了地雷 3，最終結果如下。

然后我們要查詢 [1，6] 范圍的地雷數，結果是 3，但是如果維護的最大值，那最大值就是 2，也就是 [2，4] 這個區間的最大值是 2，但是根據這個最大值是沒辦法算出總地雷數的，所以得另外想個辦法，既然維護整個區間是不行的，那么能不能維護左右邊界來求地雷總數呢，我們可以用 left 和 right 兩個數組來維護地雷的左右邊界，left[i] 表示這個范圍的地雷左邊界總數，right[i] 表示這個范圍的地雷右邊界總數，更新的時候不用范圍更新了，因為就算是范圍更新也是 [l，l] 更新和 [r，r] 更新，也就是單點更新了，所以直接深入到葉子節點去更新，然后再維護累加和，整體時間復雜度是 $O(n?lo{g}_{2}n)$。

那么查詢要如何查詢呢，來看下下面的圖。

上面圖一共埋了 4 個地雷，范圍是從 1-8，比如我們要求 [3，7] 這個范圍內一共有多少地雷，首先求出來 [1，r] 這個范圍包含了多少個地雷的左邊界，然后再求出 [1，2] 包含了多少地雷的右邊界，一相減就求出結果了，總結來說就是加入 [l，r] 范圍先求出 [1，r] 范圍有多少地雷的左邊界，然后求出 [1，l - 1] 范圍有多少地雷的右邊界，再相減。

這樣求出來的結果是 4，那么為什么可以這么求，首先要明確什么地雷會落在 [l，r] 范圍。

可以看到，這兩種可以就可以概括了，就是下面兩種：

• 左邊界 < l，右邊界 >= l
• l < 左邊界 < r

所以可以看到，匯總以下，最終要落在 [l，r] 范圍的地雷左邊界肯定是要 <= r 的，于是第一步就是求出 [1，r] 這個范圍的有多少個地雷的左邊界，然后右邊界肯定是不能小于 l 的，如果小于 l 就落不到這個區間了，所以求出來右邊界 <= l - 1 的地雷數，然后相減就行了，下面看下 code。

import java.io.*;public class Main {public static int MAXN = 100001;public static int[] left = new int[MAXN << 2];public static int[] right = new int[MAXN << 2];public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int n = (int) in.nval;in.nextToken();int m = (int) in.nval;build(1, n, 1);for (int i = 1; i <= m; i++) {in.nextToken();int op = (int) in.nval;in.nextToken();int jobl = (int) in.nval;in.nextToken();int jobr = (int) in.nval;if (op == 1) {add(0, jobl, 1, n, 1);add(1, jobr, 1, n, 1);} else {// [1, r] 的左邊界 - [1, l-1] 的右邊界地雷數int cl = query(0, 1, jobr, 1, n, 1);int cr = jobl == 1 ? 0 : query(1, 1, jobl - 1, 1, n, 1);out.println(cl - cr);}}out.flush();out.close();br.close();}public static int query(int type, int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {return type == 0 ? left[i] : right[i];}int res = 0;int mid = l + ((r - l) >> 1);if (jobl <= mid) {res += query(type, jobl, jobr, l, mid, i << 1);}if (jobr > mid) {res += query(type, jobl, jobr, mid + 1, r, i << 1 | 1);}return res;}public static void add(int type, int jobi, int l, int r, int i) {// 更新直接到葉子節點更新，不需要懶更新了，數據量不大if (l == r) {if (type == 0) {left[i]++;} else {right[i]++;}} else {int mid = l + ((r - l) >> 1);if (jobi <= mid) {add(type, jobi, l, mid, i << 1);}if (jobi > mid) {add(type, jobi, mid + 1, r, i << 1 | 1);}up(i);}}private static void up(int i) {left[i] = left[i << 1] + left[i << 1 | 1];right[i] = right[i << 1] + right[i << 1 | 1];}private static void build(int l, int r, int i) {if (l == r) {left[i] = right[i] = 0;} else {int mid = l + ((r - l) >> 1);build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);}}}

4. P1438 無聊的數列

P1438 無聊的數列

題目背景

無聊的 YYB 總喜歡搞出一些正常人無法搞出的東西。有一天，無聊的 YYB 想出了一道無聊的題：無聊的數列。。。

題目描述

維護一個數列 $a_i$，支持兩種操作：

• 1 l r K D：給出一個長度等于 $r?l+1$ 的等差數列，首項為 $K$，公差為 $D$，并將它對應加到 $[l,r]$ 范圍中的每一個數上。即：令 $a_l=a_l+K,a_{l+1}=a_{l+1}+K+D\dots a_r=a_r+K+(r?l)\times D$。

• 2 p：詢問序列的第 $p$ 個數的值 $a_p$。

輸入格式

第一行兩個整數數 $n,m$ 表示數列長度和操作個數。

第二行 $n$ 個整數，第 $i$ 個數表示 $a_i$。

接下來的 $m$ 行，每行先輸入一個整數 $opt$。

若 $opt=1$ 則再輸入四個整數 $lrKD$；

若 $opt=2$ 則再輸入一個整數 $p$。

輸出格式

對于每個詢問，一行一個整數表示答案。

輸入輸出樣例 #1

輸入 #1

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

輸出 #1

6

說明/提示

數據規模與約定

對于 $100\%$ 數據，$0\le n,m\le 10^5,?200\le a_i,K,D\le 200,1\le l\le r\le n,1\le p\le n$。

思路：

這個就是要加一個等差數列，而且比較特殊的一點就是這里第 2 個操作不是范圍查詢，只是單點查詢，因此這里可以對差分數組構造線段樹，那么對于第一個操作，首項為 k，公差為 d 的等差數列，假設 k = 2，d = 3，假設 l = 2，r = 5，那么添加的等差數列就是 2，2 + 3，2 + 3 * 2， 2 + 33，2 + 34。

對于線段樹維護差分數組的范圍增加還是比較容易的，首先就是在 [2，2] 的位置 + 2，然后在 [3，5] 范圍 + 3，最后別忘了在 6 位置減去總和，也就是減去 2 + (3 * 4)，這是差分數組的性質決定的，比如要在原數組 [l，r] 范圍 + v，那么對于差分數組的修改就是 d[l] + v，d[r + 1] - v，這樣求前綴和的時候求出來原數組的 [l，r] 范圍就都是 v 了，對于線段數也是，由于差分數組這個范圍增加到 r 這個區間一共加了 2 + (3 * 4)，因此 r + 1 位置減去 2 + (3 * 4) 抵消影響，這樣線段樹 query 求 [1，p] 的范圍總和就是下標 p 的原數組值了。

import java.io.*;public class Main {public static int MAXN = 100001;public static long[] diff = new long[MAXN];public static long[] sum = new long[MAXN << 2];public static long[] add = new long[MAXN << 2];public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int n = (int) in.nval;in.nextToken();int m = (int) in.nval;int pre = 0, cur = 0;for (int i = 1; i <= n; i++) {in.nextToken();cur = (int) in.nval;diff[i] = cur - pre;pre = cur;}build(1, n, 1);for (int i = 1; i <= m; i++) {in.nextToken();int op = (int) in.nval;if (op == 1) {in.nextToken();int jobl = (int) in.nval;in.nextToken();int jobr = (int) in.nval;in.nextToken();long k = (long) in.nval;in.nextToken();long d = (long) in.nval;long e = k + d * (jobr - jobl);add(jobl, jobl, k, 1, n, 1);if (jobl < jobr) {add(jobl + 1, jobr, d, 1, n, 1);}if (jobr + 1 <= n) {add(jobr + 1, jobr + 1, -e, 1, n, 1);}} else {in.nextToken();int p = (int) in.nval;out.println(query(1, p, 1, n, 1));}}out.flush();out.close();br.close();}private static long query(int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {return sum[i];}long ans = 0;int mid = l + ((r - l) >> 1);down(i, mid - l + 1, r - mid);if (jobl <= mid) {ans += query(jobl, jobr, l, mid, i << 1);}if (jobr > mid) {ans += query(jobl, jobr, mid + 1, r, i << 1 | 1);}return ans;}private static void build(int l, int r, int i) {if (l == r) {sum[i] = diff[l];} else {int mid = l + ((r - l) >> 1);build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);up(i);}add[i] = 0;}private static void up(int i) {sum[i] = sum[i << 1] + sum[i << 1 | 1];}public static void add(int jobl, int jobr, long jobv, int l, int r, int i) {if (jobl <= l && r <= jobr) {lazy(i, jobv, r - l + 1);} else {int mid = l + ((r - l) >> 1);down(i, mid - l + 1, r - mid);if (jobl <= mid) {add(jobl, jobr, jobv, l, mid, i << 1);}if (jobr > mid) {add(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);}up(i);}}private static void down(int i, int ln, int rn) {if (add[i] != 0) {lazy(i << 1, add[i], ln);lazy(i << 1 | 1, add[i], rn);add[i] = 0;}}private static void lazy(int i, long v, int cnt) {sum[i] += v * cnt;add[i] += v;}}

5. P1471 方差

P1471 方差。

題目背景

滾粗了的 HansBug 在收拾舊數學書，然而他發現了什么奇妙的東西。

題目描述

蒟蒻 HansBug 在一本數學書里面發現了一個神奇的數列，包含 $N$ 個實數。他想算算這個數列的平均數和方差。

輸入格式

第一行包含兩個正整數 $N,M$，分別表示數列中實數的個數和操作的個數。

第二行包含 $N$ 個實數，其中第 $i$ 個實數表示數列的第 $i$ 項。

接下來 $M$ 行，每行為一條操作，格式為以下三種之一：

操作 $1$：1 x y k ，表示將第 $x$ 到第 $y$ 項每項加上 $k$，$k$ 為一實數。
操作 $2$：2 x y ，表示求出第 $x$ 到第 $y$ 項這一子數列的平均數。
操作 $3$：3 x y ，表示求出第 $x$ 到第 $y$ 項這一子數列的方差。

輸出格式

輸出包含若干行，每行為一個實數，即依次為每一次操作 $2$ 或操作 $3$ 所得的結果（所有結果四舍五入保留 $4$ 位小數）。

輸入輸出樣例 #1

輸入 #1

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

輸出 #1

3.0000
2.0000
0.8000

說明/提示

關于方差：對于一個有 $n$ 項的數列 $A$，其方差 $s^2$ 定義如下：
$$s^2=\frac{1}{n}\sum _{i=1}^n{\left(A_i?\overline{A}\right)}^2$$
其中 $\overline{A}$ 表示數列 $A$ 的平均數，$A_i$ 表示數列 $A$ 的第 $i$ 項。

數據規模：

數據點	$N$	$M$	備注
$1～3$	$N\le 8$	$M\le 15$	-
$4～7$	$N\le 10^5$	$M\le 10^5$	不包含操作 $3$
$8～10$	$N\le 10^5$	$M\le 10^5$	-

思路：

首先為了維護平均數，我們可以維護一個累加和信息，求平均數的時候就用累加和 / 區間長度就可以了，那么如何表示方差呢，下面來推導下。

• ${\sum }_{i=1}^n(A_i?\bar{A}{)}^2=(A_1^2+{\bar{A}}^2?2?A_1?\bar{A})+(A_2^2+{\bar{A}}^2?2?A_2?\bar{A})+...+(A_n^2+{\bar{A}}^2?2?A_n?\bar{A})=(A_1^2+A_2^2+...+A_n^2)?2?\bar{A}?(A_1+A_2+...+A_n)+n?{\bar{A}}^2={\sum }_{i=1}^n{A}_i^2?n?{\bar{A}}^2$
• $\frac{{\sum }_{i=1}^n(A_i?\bar{A}{)}^2}{n}=\frac{{\sum }_{i=1}^n{A}_i^2}{n}?{\bar{A}}^2$

所以這里我們用兩個數組，一個維護累加和，求平均數就用 (sum1 / size) * (sum1 / size)，然后再維護一個平方累加和，求第一部分就直接用 sum2 / size，最終結果就是 $\frac{sum2}{size}?\frac{sum{1}^2}{siz{e}^2}$。

那么要維護平方累加和，能不能在 O(1) 時間內懶更新完成呢，也是沒問題的，如果沒有累加和數組那肯定不能 O(1) 懶更新完，但是有了累加和，就可以化簡下了，假設現在平方累加和是 sum2[i]，比如是 [l，r] 區間的累加和，可以寫成：$(A_1^2+A_2^2+...+A_n^2)$，那么現在這個范圍的每一個數字都加上 k，最終平方累加和變成了：

• $((A_1+k{)}^2+(A_2+k{)}^2+...+(A_n+k{)}^2)$

再化簡下變成了：

• $(A_1^2+A_2^2+...+A_n^2)+2?k?(A_1+A_2+...+A_k)+n?k^2$

那前面的 $(A_1^2+A_2^2+...+A_n^2)$ 就是原來的 sum2[i]，然后 $2?k?(A_1+A_2+...+A_k)$ 就是 2 * k * sum[i]，sum[i] 就是區間累加和，然后最后的 $n?k^2$ 也可以 O(1) 時間完成，所以整體都可以在 O(1) 時間內完成，不過要注意一下，由于更新 sum2 需要依賴 sum1，所以需要先更新 sum2 再更新 sum1，然后其他的就跟之前的差不多了，下面看 code。

import java.io.*;
import java.util.StringTokenizer;public class Main {public static int MAXN = 100001;public static double[] arr = new double[MAXN];public static double[] sum1 = new double[MAXN << 2];public static double[] sum2 = new double[MAXN << 2];public static double[] add = new double[MAXN << 2];public static void main(String[] args) {Kattio kattio = new Kattio();int n = kattio.nextInt();int m = kattio.nextInt();for (int i = 1; i <= n; i++) {arr[i] = kattio.nextDouble();}build(1, n, 1);double jobv = 0.0;for (int i = 1, op, jobl, jobr; i <= m; i++) {op = kattio.nextInt();if (op == 1) {jobl = kattio.nextInt();jobr = kattio.nextInt();jobv = kattio.nextDouble();add(jobl, jobr, jobv, 1, n, 1);} else if (op == 2) {jobl = kattio.nextInt();jobr = kattio.nextInt();double res = query(sum1, jobl, jobr, 1, n, 1);kattio.println(String.format("%.4f", res / (jobr - jobl + 1)));} else if (op == 3) {jobl = kattio.nextInt();jobr = kattio.nextInt();double r1 = query(sum1, jobl, jobr, 1, n, 1);double r2 = query(sum2, jobl, jobr, 1, n, 1);int c = jobr - jobl + 1;kattio.println(String.format("%.4f", r2 / c - (r1 / c) * (r1 / c)));}}kattio.flush();kattio.close();}private static double query(double[] sum, int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {return sum[i];}int mid = l + ((r - l) >> 1);down(i, mid - l + 1, r - mid);double res = 0;if (jobl <= mid) {res += query(sum, jobl, jobr, l, mid, i << 1);}if (jobr > mid) {res += query(sum, jobl, jobr, mid + 1, r, i << 1 | 1);}return res;}private static void add(int jobl, int jobr, double jobv, int l, int r, int i) {if (jobl <= l && r <= jobr) {lazy(i, jobv, r - l + 1);} else {int mid = l + ((r - l) >> 1);down(i, mid - l + 1, r - mid);if (jobl <= mid) {add(jobl, jobr, jobv, l, mid, i << 1);}if (jobr > mid) {add(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);}up(i);}}private static void down(int i, int ln, int rn) {if (add[i] != 0) {lazy(i << 1, add[i], ln);lazy(i << 1 | 1, add[i], rn);add[i] = 0;}}private static void lazy(int i, double v, int cnt) {sum2[i] += 2 * sum1[i] * v + v * v * cnt;sum1[i] += cnt * v;add[i] += v;}private static void build(int l, int r, int i) {if (l == r) {sum1[i] = arr[l];sum2[i] = arr[l] * arr[l];} else {int mid = l + ((r - l) >> 1);build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);up(i);}add[i] = 0;}private static void up(int i) {sum1[i] = sum1[i << 1] + sum1[i << 1 | 1];sum2[i] = sum2[i << 1] + sum2[i << 1 | 1];}public static class Kattio extends PrintWriter {private BufferedReader r;private StringTokenizer st;public Kattio() {this(System.in, System.out);}public Kattio(InputStream i, OutputStream o) {super(o);r = new BufferedReader(new InputStreamReader(i));}public Kattio(String intput, String output) throws IOException {super(output);r = new BufferedReader(new FileReader(intput));}public String next() {try {while (st == null || !st.hasMoreTokens())st = new StringTokenizer(r.readLine());return st.nextToken();} catch (Exception e) {}return null;}public int nextInt() {return Integer.parseInt(next());}public double nextDouble() {return Double.parseDouble(next());}public long nextLong() {return Long.parseLong(next());}}}

不過這個 code 會超過空間限制。

視頻里面給了 C++ 版本，用這個版本的可以過，所以直接用視頻里面的 C++ 代碼就行，但是上面的 java 邏輯是對的，照著翻譯成 C++ 也沒問題。

如有錯誤，歡迎指出！！！