USACO 2019-2020賽季題解（Jan）

USACO競賽2020-2021新賽季第一場即將開始，為(wei) 方便同學了解題目思路，準備了四期《USACO題解》專(zhuan) 題，本期進入第二期解題思路提供 2019-2020賽季各級別晉級題目題解參考，希望能為(wei) 同學們(men) 提供有用的幫助。

1
Task1題目：

Bessie 和她的妹妹 Elsie 正在 Farmer John 的漿果園裏采漿果。Farmer John 的漿果園裏有 N 棵漿果樹（1≤N≤1000）；樹 i 上有 Bi個(ge) 漿果（1≤ Bi≤1000）。Bessie 有 K 個(ge) 籃子（1≤K≤1000，K 為(wei) 偶數）。每個(ge) 籃子裏可以裝同一棵樹上采下的任意多個(ge) 漿果，但是不能裝來自於(yu) 不同的樹上的漿果，因為(wei) 它們(men) 的口味可能不同。籃子裏也可以不裝漿果。Bessie 想要使得她得到的漿果數量最大。但是，Farmer John 希望 Bessie 與(yu) 她的妹妹一同分享，所以 Bessie 必須將漿果數量較多的 K/2 個(ge) 籃子給 Elsie。這表示 Elsie 很有可能最後比 Bessie 得到更多的漿果，這十分不公平，然而姐妹之間往往就是這樣。 幫助 Bessie 求出她最多可以得到的漿果數量。

測試點性質：測試點 1-4 滿足 K≤10。測試點 5-11 沒有額外限製。

輸入格式（文件名：berries.in）：輸入的第一行包含空格分隔的整數 N 和 K。第二行包含 N 個(ge) 空格分隔的整數  B1, B2,…, BN。 輸出格式（文件名：berries.out）：輸出一行，包含所求的答案。

輸入樣例：5 43 6 8 4 2

輸出樣例：8如果 Bessie 在l一個(ge) 籃子裏裝樹 2 的 6 個(ge) 漿果l兩(liang) 個(ge) 籃子裏每個(ge) 裝樹 3 的 4 個(ge) 漿果l一個(ge) 籃子裏裝樹 4 的 4 個(ge) 漿果那麽(me) 她能夠得到兩(liang) 個(ge) 各裝有 4 個(ge) 漿果的籃子，總共 8 個(ge) 漿果。

解析：假設 Elsie 拿的籃子裏麵果子數最小值為(wei) m，那麽(me) 最好情況是她拿的籃子裏全都是 m 個(ge) 果子。

Task 2題目：

Farmer John 欠了 Bessie N 加侖(lun) 牛奶（1≤N≤1012）。他必須在 K 天內(nei) 將牛奶給 Bessie。但是，他不想將牛奶太早拿出手。另一方麵，他不得不在還債(zhai) 上有所進展，所以他必須每天給 Bessie 至少 M 加侖(lun) 牛奶（1≤M≤1012）。以下是 Farmer John 決(jue) 定償(chang) 還 Bessie 的方式。

首先他選擇一個(ge) 正整數 X。然後他每天都重複以下過程：假設 Farmer John 已經給了 Bessie G 加侖(lun) ，計算 N−GX 向下取整。令這個(ge) 數為(wei) Y。如果 Y 小於(yu) M，令 Y 等於(yu) M。給 Bessie Y 加侖(lun) 牛奶。求 X 的最大值，使得 Farmer John 按照上述過程能夠在 K 天後給 Bessie 至少 N 加侖(lun) 牛奶 （1≤K≤1012）。

測試點性質：測試點 2-4 滿足 K≤105。測試點 5-11 沒有額外限製。

輸入格式（文件名：loan.in）：輸入僅(jin) 有一行，包含三個(ge) 空格分隔的正整數 N、K 和 M，滿足 K⋅M<N。

輸出格式（文件名：loan.out）：輸出最大的正整數 X，使得按照上述過程 Farmer John 會(hui) 給 Bessie 至少 N 加侖(lun) 牛奶。

輸入樣例：10 3 3

輸出樣例：2在這個(ge) 測試用例中，當 X=2 時 Farmer John 第一天給 Bessie 5 加侖(lun) ，後兩(liang) 天每天給 Bessie M=3 加侖(lun) 。注意這個(ge) 問題涉及到的整數規模需要使用 64 位整數類型（例如，C/C++ 中的“long long”）。

解析：很明顯，可以通過二分xx的方式將極值問題轉化為(wei) 判定性問題。暴力的方法是直接模擬每一天還的牛奶量，複雜度O(k logn)，能過四個(ge) 點。考慮優(you) 化二分的判定函數。我們(men) 將還的過程分為(wei) 兩(liang) 部分。前一部分每次還的牛奶量都大於(yu) M，後一部分則等於(yu) M。容易發現，在前一部分的某些情況下，會(hui) 有連續幾天還同樣的牛奶量。考慮從(cong) 這個(ge) 方向去優(you) 化複雜度。

Task 3題目：

Farmer John 的奶牛們(men) 已經厭倦了他對她們(men) 每天早上排好序離開牛棚的要求。她們(men) 剛剛完成了量子物理學的博士學位，準備將這一過程搞快點。今天早上，如同往常一樣，Farmer John 的 N 頭編號為(wei) 1…N 的奶牛（1≤N≤105），分散在牛棚中 N 個(ge) 編號為(wei) 1…N 的不同位置，奶牛 i 位於(yu) 位置 pi。但是今天早上還出現了 M 個(ge) 編號為(wei) 1…M 的蟲洞（1≤M≤105），其中蟲洞 i 雙向連接了位置 ai 和 bi，寬度為(wei) wi（1≤ai,bi≤N,ai≠bi,1≤wi≤109）。

在任何時刻，兩(liang) 頭位於(yu) 一個(ge) 蟲洞兩(liang) 端的奶牛可以選擇通過蟲洞交換位置。奶牛們(men) 需要反複進行這樣的交換，直到對於(yu) 1≤i≤N，奶牛 i 位於(yu) 位置 i。奶牛們(men) 不想被蟲洞擠壞。幫助她們(men) 最大化被她們(men) 用來排序的蟲洞寬度的最小值。保證奶牛們(men) 有可能排好序。

測試點性質：測試點 3-5 滿足 N,M≤1000。測試點 6-10 沒有額外限製。

輸入格式（文件名：wormsort.in）：輸入的第一行包含兩(liang) 個(ge) 整數 N 和 M。第二行包含 N 個(ge) 整數 p1,p2,…,pN。保證 p 是 1…N 的一個(ge) 排列。 對於(yu) 1 到 M 之間的每一個(ge) i，第 i+2 行包含整數 ai、bi 和 wi。

輸出格式（文件名：wormsort.out）：輸出一個(ge) 整數，為(wei) 在排序過程中奶牛必須擠進的蟲洞的最小寬度的最大值。如果奶牛們(men) 不需要用任何蟲洞來排序，輸出 −1。

輸入樣例：4 43 2 1 41 2 91 3 72 3 102 4 3

輸出樣例：9以下是一個(ge) 僅(jin) 用寬度至少為(wei) 9 的蟲洞給奶牛排序的可能方案：奶牛 1 和奶牛 2 使用第三個(ge) 蟲洞交換位置。奶牛 1 和奶牛 3 使用第一個(ge) 蟲洞交換位置。奶牛 2 和奶牛 3 使用第三個(ge) 蟲洞交換位置。

輸入樣例：4 11 2 3 44 2 13

輸出樣例：-1給奶牛們(men) 排序不需要使用任何蟲洞。解析：

這題思路還是比較簡單的。

注意到"最大化被她們(men) 用來排序的蟲洞寬度的最小值"，很容易想到二分答案。

又因為(wei) 要使"奶牛 i 位於(yu) 位置 i"，所以考慮用並查集維護。

首先對所有蟲洞按寬度從(cong) 大到小排序，接著二分所用的蟲洞寬度的最小值，
判斷函數中將可使用的蟲洞連接的兩(liang) 個(ge) 位置編號合並，最後判斷是否所有 錯位的奶牛所在的編號 都與(yu) 她們(men) 自己的編號 在一個(ge) 集合裏就行了（可以用類似基礎的冒泡排序的思想證明：對於(yu) 一個(ge) 覆蓋了 一些錯位的奶牛的編號及這些奶牛們(men) 所在地編號的集合（可將其轉化為(wei) 在一條鏈上），每次都可以通過若幹次操作將一個(ge) 編號為(wei) 鏈首編號的奶牛傳(chuan) 送到鏈首，再將其從(cong) 集合中刪去，多次這樣操作就可以使這個(ge) 集合裏所有的奶牛回到原位）。

最後輸出答案。

複雜度O(nlogn)

2
Task 1題目：

Bessie 正在安排前往牛尼亞(ya) 的一次出差，那裏有 N（2≤N≤1000）個(ge) 編號為(wei) 1…N 的城市，由 M （1≤M≤2000）條單向的道路連接。Bessie 每次訪問城市 i 都可以賺到 mi 哞尼（0≤mi≤1000）。從(cong) 城市 1 出發，Bessie 想要賺到盡可能多的錢，最後回到城市 1。為(wei) 了避免爭(zheng) 議，m1=0。沿著兩(liang) 個(ge) 城市之間的道路移動需要消耗一天。出差的準備工作十分費錢；旅行 T 天需要花費 C✖T2 錢（1≤C≤1000）。Bessie 在一次出差中最多可以賺到多少錢？注意有可能最優(you) 方案是 Bessie 不訪問城市 1 之外的任何城市，在這種情況下結果應當為(wei) 0。

輸入格式（文件名：time.in）：輸入的第一行包含三個(ge) 整數N、M 和 C。第二行包含 N 個(ge) 整數 m1,m2,…mN。以下 M 行每行包含兩(liang) 個(ge) 空格分隔的整數 a 和 b（a≠b），表示從(cong) 城市 a 到城市 b 的一條單向道路。

輸出格式（文件名：time.out）：輸出一行，包含所求的答案。

輸入樣例：3 3 10 10 201 22 33 1

輸出樣例：24最優(you) 的旅行方案是 1→2→3→1→2→3→1。Bessie 總共賺到了 10+20+10+20−1✖62=24 。解析：題目意思就是給你一個(ge) 有向圖，你在上麵走獲得 mi ，沒經過一個(ge) 點可以獲得sum2(走過的邊數)*C

解決(jue) ：考慮DP我們(men) 設f i,j表示第i天到達城市j的最大收益。轉移很簡單f i,j=max{fi-1,lasj}+mj,fi,j}}對於(yu) lasj 的處理我們(men) 隻需要反向建有向邊即可，答案就是max{fi,1-i2*C}但是這樣i的枚舉(ju) 範圍無法確定，但是我們(men) 發現i≤1000即可，因為(wei) max{mi}*day-day2*C≤1

Task 2題目：

Farmer John 相信他在算法設計上實現了一個(ge) 重大突破：他聲稱他發現了一個(ge) 3SUM 問題的近似線性時間算法，這是一個(ge) 有名的算法問題，尚未發現比運行速度比平方時間明顯更優(you) 的解法。3SUM 問題的一個(ge) 形式是：給定一個(ge) 整數數組 s1,…,sm，計算不同索引組成的無序三元對 i,j,k 的數量，使得 si+sj+sk=0。為(wei) 了測試 Farmer John 的斷言，Bessie 提供了一個(ge) N 個(ge) 整數組成的數組 A（1≤N≤5000）。Bessie 還會(hui) 進行 Q 次詢問（1≤Q≤105），每個(ge) 詢問由兩(liang) 個(ge) 索引 1≤ai≤bi≤N 組成。對於(yu) 每個(ge) 詢問，Farmer John 必須在子數組 A[ai…bi] 上求解 3SUM 問題。不幸的是，Farmer John 剛剛發現了他的算法中的一個(ge) 錯誤。他很自信他能修複這個(ge) 算法，但同時，他請你幫他先通過 Bessie 的測試！

測試點性質：測試點 2-4 滿足 N≤500。測試點 5-7 滿足 N≤2000。測試點 8-15 沒有額外限製。

輸入格式（文件名：threesum.in）：輸入的第一行包含兩(liang) 個(ge) 空格分隔的整數 N 和 Q。第二行包含空格分隔的數組 A 的元素 A1,…,AN。以下 Q 行每行包含兩(liang) 個(ge) 空格分隔的整數 ai 和 bi，表示一個(ge) 詢問。保證對於(yu) 每個(ge) 數組元素 Ai 有 −106≤Ai≤106。

輸出格式（文件名：threesum.out）：輸出包含 Q 行，第 i 行包含一個(ge) 整數，為(wei) 第 i 個(ge) 詢問的結果。注意你需要使用 64 位整數型來避免溢出。

輸入樣例：7 32 0 -1 1 -2 3 31 52 41 7

輸出樣例：214對於(yu) 第一個(ge) 詢問，所有的三元對為(wei) (A1,A2,A5) 和 (A2,A3,A4)。

解析：發現n≤5000，那麽(me) 我們(men) 自然想到O(n2)O(1)回答詢問。先考慮一個(ge) 更簡單的問題，如果f[i][j]表示在區間[l,r][l,r]中，滿足k∈(l,r),a[k]+a[l]+a[r]=0的k的數量，那麽(me) 我們(men) 是可以枚舉(ju) 左右端點，用一個(ge) 桶做到O(n2)預處理f的。

那麽(me) f與(yu) 最後的答案是什麽(me) 關(guan) 係呢？最後要求的是：在一段區間內(nei) ，左右端點不強製選的方案數。這隱隱約約的有點像是f數組的一個(ge) 前綴和。我們(men) 可以考慮先求出s[l][r表示左端點在[1,l]內(nei) ，右端點在[1,r]內(nei) 的總方案數。這就真的是f的二位前綴和了。

可以這麽(me) 理解，把f[l][r]對應到平麵上的一個(ge) 點，那麽(me) s[l][r]就是從(cong) (1,1)到(l,r)的這個(ge) 矩形中所有點的和。這樣我們(men) 也就可以在O(n2)的時間內(nei) 求出s。同樣的，最後的答案實際上是區間左右端點都在[l,r]內(nei) 總答案。對應到平麵上也就是左上角為(wei) (l,l)，右下角為(wei) (r,r)的矩形中所有點的和。這樣就可以通過s來O(1)求答案了。

Task 3題目：

Bessie 在一個(ge) 僅(jin) 允許沿平行於(yu) 坐標軸方向移動的二維方陣中。她從(cong) 點 (0,0) 出發，想要到達 (N,N)（1≤N≤109）。為(wei) 了幫助她達到目的，在方陣中有 P（1≤P≤105）個(ge) 跳板。每個(ge) 跳板都有其固定的位置 (x1,y1)，如果 Bessie 使用它，會(hui) 落到點 (x2,y2)。Bessie 是一個(ge) 過程導向的奶牛，所以她僅(jin) 允許她自己向上或向右行走，從(cong) 不向左或向下。類似地，每個(ge) 跳板也設置為(wei) 不向左或向下。Bessie 需要行走的距離至少是多少？

測試點性質：測試點 2-5 滿足 P≤1000。測試點 6-15 沒有額外限製。

輸入格式（文件名：boards.in）：輸入的第一行包含兩(liang) 個(ge) 空格分隔的整數 N 和 P。以下 P 行每行包含四個(ge) 整數 x1、y1、x2、y2，其中 x1≤x2 且 y1≤y2。所有跳板的位置和目標位置均不相同。

輸出格式（文件名：boards.out）：輸出一個(ge) 整數，為(wei) Bessie 到達點 (N,N) 需要行走的最小距離。

輸入樣例：3 20 1 0 21 2 2 3

輸出樣例：3Bessie 的最佳路線為(wei) ：Bessie 從(cong) (0,0) 走到 (0,1)（1 單位距離）。Bessie 跳到 (0,2)。Bessie 從(cong) (0,2) 走到 (1,2)（1 單位距離）。Bessie 跳到 (2,3)。Bessie 從(cong) (2,3) 走到 (3,3)（1 單位距離）。Bessie 總共走過的路程為(wei) 3 單位距離。

解析：首先考慮 dpi。設為(wei) 隻使用前 i個(ge) 跳板，且必須使用第 ii個(ge) ，能夠省下的最大距離。轉移方程如下：

顯然暴力轉移是 O(p2) 的。考慮如何優(you) 化。

發現實際上如果把 dpi的值賦值到 (x2(i),y2(i))這個(ge) 點上麵，那麽(me) 現在就是一個(ge) 二維統計問題。

想要純 BIT，顯然需要降維。發現本質上是個(ge) 可以離線的加點/矩形查詢，所以考慮排序。

將所有的點的 y坐標離散化，把 (x1,y1)和 (x2,y2)分開離散化；然後我們(men) 就有了 2p個(ge) 單點，然後按照 xx為(wei) 第一關(guan) 鍵字，y為(wei) 第二關(guan) 鍵字排序。然後就可以直接二維數點套路了：對於(yu) 每一個(ge) (x1,y1)，可以查詢區間 (1,y1)的最大值，並記錄 dp值；否則就把 dp值打到 y2上麵。

所以現在我們(men) 需要一個(ge) 數據結構，支持單點修改、前綴查詢最大值。顯然可以樹狀數組。

最後求出 dp之後，答案就是2n−maxdp。

於(yu) 是這道題就解決(jue) 了~

總時間複雜度 O(plogp)，空間複雜度 O(p)。

3
Task 1題目：

Bessie 成為(wei) 了一名藝術家，正在創作壁畫！她現在正在創作的作品是一個(ge) 高為(wei) N 的方陣，方陣的每行都由 M 個(ge) 方格組成（1≤N,M≤1000）。每個(ge) 方格是空的，畫了石頭，或者畫了水。Bessie 已經畫上了包含石頭的方格，包括整幅畫作的邊界。她現在想要將某些空的方格畫上水，使得如果這幅畫是真實的，其中應當不存在水的淨移動。

定義(yi) 從(cong) 上到下第 i 行的方格的高度為(wei) N+1−i。Bessie 想要她的畫作滿足以下限製：假設方格 a 畫的是水。那麽(me) 如果存在一條從(cong) a 到方格 b 的路徑，由高度不超過 a 的空的方格或是有水的方格組成，路徑中每相鄰兩(liang) 個(ge) 方格都有一條公共邊，那麽(me) b 畫的也是水。

求 Bessie 可以創作的不同作品的數量模 109+7 的餘(yu) 數。Bessie 可以將任意數量的空格畫上水，包括不畫以及全畫。

測試點性質：測試點 1-5 滿足 N,M≤10。測試點 6-15 沒有額外限製。

輸入格式（文件名：cave.in）：輸入的第一行包含兩(liang) 個(ge) 空格分隔的整數 N 和 M。以下 N 行每行包含 M 個(ge) 字符。每個(ge) 字符均為(wei) '.' 或 '#'，分別表示一個(ge) 空的方格和一個(ge) 畫有石頭的方格。第一行和最後一行、第一列和最後一列僅(jin) 包含 '#'。

輸出格式（文件名：cave.out）：輸出一個(ge) 整數，為(wei) 滿足限製的作品的數量模 109+7 的餘(yu) 數。

輸入樣例：4 9#...#...##.#...#.#

輸出樣例：9如果第二行中的任意一個(ge) 方格被畫上水，那麽(me) 所有空的方格必須都被畫上水。否則，假設沒有這樣的方格畫有水。那麽(me) Bessie 可以選擇畫上第三行的空格組成的三個(ge) 連續區域的任意子集。

所以，畫作的總數等於(yu) 1+23=9。

解析：這道題如果想對了方向就很簡單了。可如果一直在想如何把圖給摳出一個(ge) 森林就很難了。發現如果一個(ge) 格子放了水，對於(yu) 在這個(ge) 格子及以下的高度隻要有一條路徑能到達另一個(ge) 格子，那那個(ge) 格子也會(hui) 有水。不難聯想到可以將各個(ge) 點標上號，使用並查集來做此題。考慮對於(yu) 所有水的高度（注：高度是指從(cong) 下往上的高度）小於(yu) 等於(yu) h的方案數，答案應該是所有聯通塊的方案數的乘積。

可以發現，如果有兩(liang) 個(ge) 聯通塊合並，更新的答案應該是這兩(liang) 個(ge) 聯通快的方案數的乘積。所以對於(yu) 原先高度為(wei) hh的各個(ge) 聯通塊的方案數，可以遍曆一遍第 h+1行，看有哪些聯通塊可以合並，然後將方案數更新，由於(yu) 如果在第 h+1行放一格水，這一個(ge) 聯通快就都會(hui) 充滿水，所以還需將更新完的各個(ge) 聯通塊的方案數加一。

那麽(me) 就可以每次更新聯通塊，從(cong) 高度為(wei) hh 推到高度為(wei) h+1了。為(wei) 了方便可以將方案數存在祖先那裏，然後從(cong) 第 n 行一直推到第 1行了。總效率 O(nm) 。

Task 2題目：

Bessie 最近參加了一場 USACO 競賽，遇到了以下問題。當然 Bessie 知道怎麽(me) 做。那你呢？考慮一個(ge) 僅(jin) 由範圍在 1…K（1≤K≤20）之間的整數組成的長為(wei) N 的序列 A1,A2,…,AN（1≤N≤5*104）。給定 Q（1≤Q≤2*105）個(ge) 形式為(wei) [Li,Ri]（1≤Li≤Ri≤N）的詢問。對於(yu) 每個(ge) 詢問，計算 ALi,ALi+1…,ARi 中不下降子序列的數量模 109+7 的餘(yu) 數。AL,…,AR 的一個(ge) 不下降子序列是一組索引 (j1,j2,…,jx)，滿足 L≤j1<j2<⋯<jx≤R 以及 Aj1≤Aj2≤⋯≤Ajx。確保你考慮了空子序列！

測試點性質：測試點 2-3 滿足 N≤1000。測試點 4-6 滿足 K≤5。測試點 7-9 滿足 Q≤105。測試點 10-12 沒有額外限製。

輸入格式（文件名：nondec.in）：輸入的第一行包含兩(liang) 個(ge) 空格分隔的整數 N 和 K。第二行包含 N 個(ge) 空格分隔的整數 A1,A2,…,AN。第三行包含一個(ge) 整數 Q。以下 Q 行每行包含兩(liang) 個(ge) 空格分隔的整數 Li 和 Ri。

輸出格式（文件名：nondec.out）：對於(yu) 每個(ge) 詢問 [Li,Ri]，你應當在新的一行內(nei) 輸出 ALi,ALi+1…,ARi 的不下降子序列的數量模 109+7 的餘(yu) 數。

輸入樣例：5 21 2 1 1 232 34 51 5

輸出樣例：3420對於(yu) 第一個(ge) 詢問，不下降子序列為(wei) ()、(2) 和 (3)。(2,3) 不是一個(ge) 不下降子序列，因為(wei) A2≰A3。對於(yu) 第二個(ge) 詢問，不下降子序列為(wei) ()、(4)、(5) 和 (4,5)。解析：我們(men) 要快速求出多組詢問一個(ge) 區間內(nei) 不下降序列的個(ge) 數。（不過不同的數不超過20）設計dp方程，f[i][j]表示左端點為(wei) i，有段點值為(wei) j的方案數。g[i][j]表示右端點為(wei) i，左端點值為(wei) j的方案數。我們(men) 逆向思維，如何求出一個(ge) 詢問。

考慮拚接的思想，從(cong) 這個(ge) 詢問中間的某一個(ge) 點，隻要知道從(cong) l[i]到mid的所有f[i][j]和mid+1到r[i]的所有g[i][j]，顯然每一種要嗎隻在左邊或隻在右邊（加一個(ge) 空集即可），否則必定過mid，所有我們(men) 可以枚舉(ju) 拚接的地方，然後從(cong) l到mid左右f[l][i]之和乘上從(cong) r到mid+1所有g[r][j]（j>=i）之和就是答案。所以對於(yu) 每一個(ge) 詢問，我們(men) 隻需知道任意一個(ge) 在其中的點的所有f和g數組就可以O（n）求出答案。

但是我們(men) 現在有m個(ge) 詢問，如何找出這些mid且保證複雜度。分治大法好。考慮二分切割。於(yu) 是對於(yu) 每一個(ge) l到r，我們(men) 預處理出mid的f，g數組，用數據結構總共n∗log n2。然後把過mid的所有詢問處理掉。把在左側(ce) 和右側(ce) 的詢問分開保證，分別分治即可。

Task 3題目：

有 N（2≤N≤2*105）個(ge) 世界，每個(ge) 世界有一個(ge) 傳(chuan) 送門。初始時，世界 i（對於(yu) 1≤i≤N）位於(yu) x 坐標 i，y 坐標 Ai（1≤Ai≤109）。每個(ge) 世界裏還有一頭奶牛。在時刻 0，所有的 y 坐標各不相同，然後這些世界開始墜落：世界 i 沿著 y 軸負方向以 i 單位每秒的速度移動。在任意時刻，如果兩(liang) 個(ge) 世界在某一時刻 y 坐標相同（可能是非整數時刻），傳(chuan) 送門之間就會(hui) “同步”，使得其中一個(ge) 世界的奶牛可以選擇瞬間傳(chuan) 送到另一個(ge) 世界。

對於(yu) 每一個(ge) i，在世界 i 的奶牛想要去往世界 Qi（Qi≠i）。幫助每頭奶牛求出如果她以最優(you) 方案移動需要多少時間。每個(ge) 詢問的輸出是一個(ge) 分數 a/b，其中 a 和 b 為(wei) 互質的正整數，或者 −1，如果不可能到達。

測試點性質：測試點 2-3 滿足 N≤100。測試點 4-5 滿足 N≤2000。測試點 6-14 沒有額外限製。

輸入格式（文件名：falling.in）：輸入的第一行包含一個(ge) 整數 N。下一行包含 N 個(ge) 空格分隔的整數 A1,A2,…,AN。下一行包含 N 個(ge) 空格分隔的整數 Q1,Q2,…,QN。

輸出格式（文件名：falling.out）：輸出 N 行，第 i 行包含奶牛 i 的旅程的時間。

輸入樣例：43 5 10 23 3 2 1

輸出樣例：7/2

7/2

5/1

-1

考慮原先在世界 2 的奶牛的答案。在時刻 2 世界 1 和世界 2 同步，所以奶牛可以前往世界 1。在時刻 7/2 世界 1 和世界 3 同步，所以奶牛可以前往世界 3。

解析：

我們(men) 考慮一下，當兩(liang) 個(ge) 世界“同步”之時，哪種情況我們(men) 會(hui) 選擇傳(chuan) 送，哪種情況則不。

顯然，當這頭牛的目的地比它現在的位置要高時，它應該盡量往下落速度慢的世界走，這樣方便等待高處的目的地落下來，也因此隻要與(yu) 它同步的世界比它慢就應該傳(chuan) 送；當這頭牛的目的地比它現在的位置要低時，它應該盡量往下落速度快的世界走，以此來追趕它的目的地，也因此隻要與(yu) 它同步的世界比它快就應該傳(chuan) 送。

我們(men) 可以證明，隻要固定了目的地的高度關(guan) 係（即高於(yu) 出發點高度還是低於(yu) 出發點高度），則無論時刻如何，每一個(ge) 世界上的牛，都有著唯一的傳(chuan) 送目標。

我們(men) 不妨假設我們(men) 的目的地在出發點下方，則我們(men) 應該盡量往下落速度大的世界走。我們(men) 把目的地在出發點上方的情況稱作UP類，而目的地在出發點下方的情況稱作DW類。則我們(men) 以下隻考慮DW類。

我們(men) 考慮對於(yu) 每個(ge) 世界，畫出它的高度h與(yu) 時間t的關(guan) 係。（注意下文中“斜率”一詞指的是傾(qing) 斜程度，即越陡峭的線斜率越大，換句話說，是正常的斜率取絕對值後的結果）

一張典型的圖可能會(hui) 長這樣：

則在一處交點處，就意味著發生了一次“同步”，也就意味著斜率小的直線可以在DW時傳(chuan) 送到斜率大的直線上，而斜率大的直線可以在UP時傳(chuan) 送到斜率小的直線上。

考慮對於(yu) 具體(ti) 的兩(liang) 條直線ff和gg。它們(men) 長成這樣：

因為(wei) 我們(men) 考慮的是DW情況，因此我們(men) 隻考慮從(cong) f到g的情況。顯然，隻有當g是f出發後第一條遇見的大斜率直線時，f才會(hui) 轉移到g；否則，即之前存在一條大斜率直線，f就一定已經在那條直線上轉移過去了。

這樣看來，對於(yu) 同一個(ge) f，這樣的g應該是唯一的，因為(wei) f出發後遇到的第一條大斜率直線是唯一的。我們(men) 把這條直線g記作dwf。這樣子，如果我們(men) 已經找出了所有的dwf，則對於(yu) 詢問，隻需要不斷地跳到dwf，直到當前直線跑到了目的地的下麵，即可。

但是，我們(men) 不能忽略的是，如果f不是從(cong) 頭開始的怎麽(me) 辦？換句話說，如果f不是出發點，它是從(cong) 另一條直線，假設是d轉移來的怎麽(me) 辦？這樣子的話，dwf與(yu) f的交點可能在（f與(yu) d的交點）前麵，也就是說不能簡單地跳到dwf。

正常的情況是這樣的圖：

可以看到，dwf是h，但是在A處時f卻跳不到h（因為(wei) f與(yu) h的交點C在A前麵）。但是，細心的讀者可能已經發現了，在這樣的情況下，dwf 變成了h而不是原圖的f！這就導致了實際上d早在D點處就已經轉到了h，而不會(hui) 像原來我們(men) 想象的那樣到A點再轉。

事實上，每個(ge) 轉移的目標，一定是dwf，因為(wei) 如果出現了之前相交過的情況，此時的直線h一定與(yu) d的交點在A前麵。也因此，直接暴力跳dwf的算法是正確的。這隻是DW的情況。類似的，UP的情況也可以通過我們(men) 預處理一個(ge) upf數組出來進行轉移。

此處不再贅述。我們(men) 可以寫(xie) 出這樣的n2 做法（n2預處理，跳dw/up）。此處有代碼（聯係課程老師獲取）期望得分35%。

我們(men) 考慮優(you) 化。如果我們(men) 畫出每個(ge) 位置的dw_fdwf的話，會(hui) 發現實際上構成了一個(ge) （一堆）凸包：即這樣：

凸包可以通過單調隊列預處理出來。複雜度O(n)。但是初始化時需要進行排序，因此是O(nlogn)的。代碼（實際上還是O(n2)的，隻不過跳dwdw時的深度可能比較小致使能通過84%）：此處有代碼（聯係課程老師獲取）發現所有的dw/up一定構成一棵樹的結構。

因此我們(men) 隻需要建出這棵樹，然後在上麵樹上倍增就可以在 nlogn時間內(nei) 找到在目的地直線上方的最後一條直線。總複雜度O(nlogn)。期望得分100%。