111 學年度 全國資訊學科能力競賽模擬賽 題解

題本：

• 系統測試：zh_TW
• 正式賽：zh_TW、en

工作人員

• 總召：侯欣緯
• 顧問：蔡旻諺、陳冠霖
• 出題驗題組：吳柏燁、吳柏翰、嚴暐華、林哲宇、林煜傑、王均倍、王褕立、范釗維、賴昭勳、鄭允臻、鄭詠堯、高允懋
• 測題組：林伯禧、王品翔、蔡旻諺、郭軒語、黃仲群、黃克崴
• 系統組：林哲宇、林秉軒、王褕立、陳冠霖、陳泰穎
• 美編組：笪瑜庭、鄭允臻

系統測試

pB 重訪抽水機 (Rewater)

author 吳柏燁 / setter 吳柏燁

Subtask 1

首先我們先從

$m_i=1$ 開始想，我們將有水點的位置分成三類：

1. 位於
   $t_i$ 左邊
2. 剛好位於
   $t_i$
3. 位於
   $t_i$ 右邊

對於 2. 顯然答案是

$0$，否則假設有水點位於

$t_i$ 左邊，觀察到如果在操作中戳到位於

$t_i$ 左邊點的話是不可能把水抽到點

$t_i$ 的。而只要戳到

$t_i$ 或是

$t_i$ 右邊的點，就可以直接把水抽到點

$t_i$。因此答案等價於期望要戳幾次才能戳到點編號

$\ge t_i$ 的點，由於此事件的機率為

$\frac{N-t_i+1}{N}$，可以推出期望值為

$\frac{N}{N-t_i+1}$。同理可以推出若一開始有水點位於

$t_i$ 右邊，期望值會是

$\frac{N}{t_i}$。

接著考慮推廣到

$m_i>1$ 的 case，可以發現如果一開始

$t_i$ 的兩邊都有水，那顯然答案是

$1$，否則隨便挑一個點出來做

$m_i=1$ 的 case 就可以了。

Subtask 2, 3

經由 subtask 1 的推導不難想到以下結論：令有水點為點

$a_i$，目標點為點

$t_i$，

$S$ 為以

$a_i$ 為根

$t_i$ 的子樹點集合。則一戳到集合

$S$ 內的點就可以結束，戳到其他點都不可能結束。因此，答案會是

$\frac{N}{|S|}$，其中

$|S|$ 為集合

$S$ 的大小。

因此我們問題轉換成：有

$Q$ 筆詢問，每次會給定兩個點

$u,v$，詢問以

$u$ 為根下點

$v$ 個子樹大小。

subtask 2 的限制下每次暴力 dfs 問大小會過，而 subtask 3 的話可以採取以下方法：

1. 先將樹以點
   $1$ 為根做一次 dfs，紀錄
   $s{z}_v$ 為點
   $v$ 的子樹大小
2. 若要詢問以
   $u$ 為根下點
   $v$ 的子樹大小，這裡分兩個 case：

(1) 以

$1$ 為根的情況下，點

$v$ 是點

$u$ 的祖先。則我們先用倍增找到在

$v$ 到

$u$ 的路徑上且深度比

$v$ 多

$1$ 的點。令此點為

$x$，則答案會是

$N-s{z}_x$
(2) 否則，答案會是

$s{z}_u$

整體複雜度會是

$O((N+Q)\log N)$

Subtask 4

同樣由 subtask 1 可以知道對於

$m_i>1$，我們要判斷的事情是以

$t_i$ 為根下，所有有水的點是否都在同一棵子樹，如果是那答案會跟

$m_i=1$ 一樣，否則答案會是

$1$。

在這筆 subtask 中，我們可以直接求出所有有水點以

$1$ 為根下的 LCA，若 LCA 為

$1$ 則代表有水的點不在同一棵子樹。

Subtask 5

至於滿分解的話，上面的做法會出錯的原因是若有點在以

$1$ 為根點

$t_i$ 子樹以外的話 LCA 沒有辦法判斷成功。然而由於我們的目標只是要判斷它們是否都在以

$t_i$ 為根的同一個子數裡，所以事實上我們可以先用祖先關係算完有多少點在

$t_i$ 子樹內。如果數量介於

$(0,m_i)$ 的話那答案顯然是 0，而若數量是

$0$ 則代表所有點都在子樹外，否則可以用跟 subtask 4 相同的作法，算完 LCA 再判斷即可。

pD 重訪黑白雞 (Rechicken)

author 吳柏燁 / setter 吳柏燁

15 分

注意到

$n^2\le 300$，所以直接回傳一個長度為

$n^2$ 的字串

$s$，若

$s_{in+j}=1$ 則代表邊

$(i,j)\in E$。

30 分

黑雞先將樹以

$1$ 為根 dfs 一遍，之後對於每個點

$v$ 將他的父親

$pa$ 轉成

$2$ 進位後把他們接起來再傳給白雞，之後白雞很容易就可以回推出樹的樣子

用的 bit 數大約為

$6n$。

50 分

黑雞回傳樹上歐拉迴路（euler tour tree）給白雞，其中用

$0$ 代表一條往下走的邊，

$1$ 代表往上走的邊。而之後白雞很容易就可以回推出樹的樣子。

用的 bit 數大約為

$2n$。

稍微壓一下個數大概可以達到 60 分

90 分

我們考慮以

$1$ 為根，將每一種樹都轉成一個編號。
定義

$d{p}_{n,l}$ 代表有多少個

$n$ 個點的樹，且根的每一個小孩的子樹大小都至少為

$l$。這裡若兩棵樹為有根同構則把它們視為相同

有了這個 dp 後就不難把每棵樹打到一個唯一的編號，但可能有不少細節，這裡留給讀者自行思考。

之後白雞考慮相同的 dp，用類似的方法即可回推出原樹的樣子。

樹的數量會

$<2^{40}$，所以這個方法會使用

$40$ 個 bit。

100 分

前面的做法我們直接以

$1$ 為根，好像有點太浪費了

我們考慮把樹以樹重心為根，這樣一來由於子樹的上界會變成

$\frac{n}{2}$，樹的數量就會變少了。

詳細的話，用

$d{p}_{n,l,r}$ 代表有多少個

$n$ 個點的樹，且根的每一個小孩的子樹大小都介於

$[l,r]$。這裡若兩棵樹為有根同構則把它們視為相同

之後黑雞與白雞只要採用類似的方法作編號與解碼即可

由於樹的數量

$<2^{35}$，所以這個方法會是使用

$35$ 個 bit，也就成功解決了這個問題。

正式賽

pA 方塊王 (Tower)

author 賴昭勳 / setter 高允懋、林煜傑 / editorial 侯欣緯

Chinese

Observation 1. 如果我們決定了一個疊方塊的順序，那麼對於

$1\le i<N$，由上往下前

$i$ 個方塊的重心應該要恰好在第

$i+1$ 個方塊的邊界，而全部

$N$ 個方塊的重心要在桌子的邊界。

Proof. 顯然全部

$N$ 個方塊的重心要在桌子的邊界。假設存在一個

$k$ 滿足前

$k$ 個方塊的重心不在第

$k+1$ 個方塊的邊界，並且這個

$k$ 是最小的，我們可以將前

$k$ 個方塊一起往左邊移一點直到它們的重心在第

$k+1$ 個方塊的邊界上，並且把前

$k+1$ 個方塊一起往右邊移一點直到它們的重心回到本來的位置，如此一來前

$k$ 個方塊的重心就會在第

$k+1$ 個方塊的邊界，並且方塊塔也不會傾倒。不斷重複之後就可以讓方塊塔滿足上述條件。

由此可知，如果我們固定疊方塊的順序，由上往下第

$i$ 個方塊重量是

$w_i$，我們一開始先把方塊們垂直整齊疊起來，接下來把最上面那一塊往左移，直到不能移為止、再把最上面的 2 塊往左移，直到不能移為止……依此類推，就能讓方塊塔延伸最長的距離。

在我們移最上面的

$k$ 塊的時候，我們能移動的距離就是此時前

$k-1$ 個方塊的重心到前

$k$ 個方塊的重心的距離，也就是

$\frac{L}{2}\frac{w_k}{w_1+\cdots +w_k}$。

所以答案就是

$$\frac{L}{2}(\frac{w_1}{w_2}+\frac{w_2}{w_1+w_2}+\cdots +\frac{w_N}{w_1+w_2+\cdots +w_N})$$

Observation 2. 重的方塊應該要放在下面。
Proof. 如果由上往下第

$i$ 和第

$i+1$ 個方塊滿足

$w_i>w_{i+1}$，那麼：

$$\begin{array}{rl}& \frac{w_i}{S+w_i}+\frac{w_{i+1}}{S+w_i+w_{i+1}}-\frac{w_{i+1}}{S+w_{i+1}}-\frac{w_i}{S+w_i+w_{i+1}}\\ =& \frac{S(w_{i+1}-w_i)}{(S+w_i)(S+w_{i+1})}+\frac{w_{i+1}-w_i}{S+w_i+w_{i+1}}\\ <& 0\end{array}$$
得出

$$\frac{w_i}{S+w_i}+\frac{w_{i+1}}{S+w_i+w_{i+1}}<\frac{w_{i+1}}{S+w_{i+1}}+\frac{w_i}{S+w_i+w_{i+1}}$$
其中

$S=w_1+\cdots +w_{i-1}$。由此可知，把第

$i$ 和第

$i+1$ 個方塊交換後，答案會更大。

因此，只要把方塊們按重量排序，並計算上述式子，就能得到答案。

pB 更加 Trivial 的題目 (Quadrivial)

author SorahISA / setter SorahISA

答案

$<0$ 的情況可以先掃過全部的序列求出最大值，所以以下只考慮答案

$\ge 0$ 的情況。
以下，「區間和」皆指跟

$0$ 取

$max$ 的值。

The case where the answer

$<0$ can be handled by scanning all sequences to find the maximum value, so the following only considers the case where the answer is

$\ge 0$.
In below, the "sum"s mentioned are all taken max with

$0$.

Subtask 1 (

$n=1$)

Chinese

Trivial.
對不知道如何計算「最大區間連續和」的人，可以參考這個教學。

Time Complexity:

$\mathcal{O}(k_1)$.

English

Trivial.
For those who do not know how to calculate the "maximum interval continuous sum", you can refer to this tutorial.

Time Complexity:

$\mathcal{O}(k_1)$.

Subtask 2 (

$n\le 500$)

Chinese

觀察到答案可以分為兩種狀態：

1. 左右界在同一序列
2. 左右界在不同序列

其中，對於左右界在同一序列的情形，答案就是該序列的最大連續和。

對於左右界在不同序列的情形，以下數字會被貢獻進答案：

• 左界那個序列的一個後綴。
• 右界那個序列的一個前綴。
• 被包在中間的序列的序列和。

其中，你可以在

$\mathcal{O}(\sum k_i)$ 對每個序列求出最大的前綴和、後綴和、以及序列和，顯然只有在序列和

$>0$ 的時候把他包在中間才有意義。

於是你可以枚舉左右界跟枚舉剩下的區間來在

$\mathcal{O}(n^3)$ 時間內計算出答案。

Time Complexity:

$\mathcal{O}(n^3+\sum k_i)$.

English

Observing that the answer can be divided into two states:

1. The left and right boundaries are in the same sequence.
2. The left and right boundaries are in different sequences.

In the case where the left and right boundaries are in the same sequence, the answer is the maximum subarray sum of that sequence.

For the case where the left and right boundaries are in different sequences, the following numbers will be contributed to the answer:

• A suffix of the sequence at the left boundary.
• A prefix of the sequence at the right boundary.
• The sum of the sequences enclosed in the middle.

In which, you can compute the maximum prefix sum, suffix sum, and total sum of each sequence in

$\mathcal{O}(k_i)$.
It is obvious that only when the sequence sum is greater than

$0$, it makes sense to include it in the middle.

Therefore, you can enumerate the left and right boundaries and the remaining intervals to calculate the answer in

$\mathcal{O}(n^3)$.

Time Complexity:

$\mathcal{O}(n^3+\sum k_i)$.

Subtask 3 (

$n\le 3000$)

Chinese

繼續上個 subtask 的做法，只要維護

$\sum _{i=1}^{n}max\{0,\sum _{j=1}^{k_i}{a}_{i,j}\}$，就能在枚舉左右界的時候

$\mathcal{O}(1)$ 更新答案。

Time Complexity:

$\mathcal{O}(n^2+\sum k_i)$.

English

Continuing the solution from the previous subtask, as long as you maintain

$\sum _{i=1}^{n}max\{0,\sum _{j=1}^{k_i}{a}_{i,j}\}$, you can update the answer in

$\mathcal{O}(1)$ when enumerating the left and right boundaries.

Time Complexity:

$\mathcal{O}(n^2+\sum k_i)$.

Subtask 4 (

$n\le 100000$)

Chinese

再繼續上個 subtask 的做法，考慮只枚舉左界，並計算把哪個序列變成右界會使答案增加最多。

觀察到把一個序列變成左界的時候，選擇最好的右界會讓答案增加

1. 「該左界的最大後綴和
   $-$ 總和」。
2. 除了該左界之外，使「最大前綴和
   $-$ 總和」最大的值。
3. 所有「序列和」的總和。

(1.) 跟 (3.) 都可以在預處理的時候做掉。
於是我們可以將所有區間按照「最大前綴和

$-$ 總和」由大至小排序，(2.) 就只會是第一項或第二項（如果左界是第一項），可以在

$\mathcal{O}(1)$ 求出。

Time Complexity:

$\mathcal{O}(n\lg n+\sum k_i)$.

English

Continuing the solution from the previous subtask, consider only enumerating the left boundary and calculating which sequence to make the right boundary will increase the answer the most.

Observing that when a sequence becomes the left boundary, choosing the best right boundary will increase the answer by

1. "Maximum suffix sum of the left boundary" minus "sum of the sequence".
2. "Maximum prefix sum of any sequence except the left boundary" minus "sum of the sequence".
3. The sum of all "sum of the sequence".

Points (1.) and (3.) can be done during preprocessing.
Therefore, we can sort all intervals by "maximum prefix sum" minus "sum of the sequence" from largest to smallest, and point (2.) will only be the first or second item (if we choose the first item as the left boundary), which can be calculated in

$\mathcal{O}(1)$.

Time Complexity:

$\mathcal{O}(n\lg n+\sum k_i)$.

Extra

Chinese

原本這題需要構造解，但是驗題完之後覺得不夠 trivial 於是就把那部分拿掉了。
不過因為我的作法在做的時候就一定會找出左右界，所以我不知道為什麼把那部分拿掉會變簡單。
問了驗題者的解法之後才意識到這題直接

$\mathcal{O}(n)$ DP 過去就好了。

一樣預處理出最大的前綴和、後綴和、區間和、總和之後，只要維護

$\mathtt{\text{dp}}[i][0/1][0/1]$ 代表前

$i$ 個區間有沒有選取前綴跟後綴，轉移式就很顯然了。

Time Complexity:

$\mathcal{O}(n+\sum k_i)$.

English

The original solution to this problem required a construction of the permutation, but after the tester tested the problem, it was felt that it was not trivial enough, so that part was removed.
However, since the official solution always finds the left and right boundaries when solving the problem, Neko-chan is curious about why removing that part makes it easier.
After asking the testers for their solutions, Neko-chan realized that this problem can be solved directly with

$\mathcal{O}(n)$ DP.

After preprocessing the maximum prefix sum, suffix sum, interval sum, and total sum, as long as you maintain

$\mathtt{\text{dp}}[i][0/1][0/1]$ to represent whether the prefix and suffix of the first

$i$ intervals are selected, the DP transition is obvious.

Time Complexity:

$\mathcal{O}(n+\sum k_i)$.

pI 子集合和 (SOS)

author 鄭詠堯 / setter 鄭詠堯

Chinese

Subtask 1

$N\le 20$

$O(N{2}^N)$ 枚舉所有子集合，應該不需要題解吧（X

Subtask 2

$N\le 1000$

我們可以考慮一個類似背包的 DP 結構。定義

$dp[i][j]$ 為考慮集合中前

$i$ 個元素中恰有

$j$ 個元素的子集合

$S$ 的

${\displaystyle \sum \prod _{x\in S}x}$，那麼答案就會是

${\displaystyle \sum _{j=1}^{N}dp[N][j]\times j}$。

DP 式可以這樣建構

$$dp[i][j]=\{\begin{array}{ll}dp[i-1][j]+dp[i-1][j-1]\times A_i,& \text{if }j>0\\ 1,& \text{if }j=0\end{array}$$

Subtask 3

$N\le {10}^5$

怪怪NTT，窩不會，待補

Subtask 5

我們可以回頭考慮 Subtask 2 的DP式子

仔細想想就會發現，這個式子其實不用那麼複雜

既然我們的答案中，

$dp[i][j]$ 會被乘上一個

$j$，那我們可以找個方法直接定義

$dp1[i]$ 為考慮前

$i$ 個物品時的答案

為了要轉移

$dp1[i]$，我們就先再定義

$dp2$，其中

$dp2[i]$ 是前

$i$ 個物品不乘上子集大小時的答案。

$dp2$ 的轉移很顯然是

$dp2[i]=\{\begin{array}{ll}dp2[i-1]\times (A_i+1),& \text{if }i>0\\ 1,& \text{if }i=0\end{array}$

這能如何幫助我們求出

$dp1$ 呢？先考慮第

$i$ 個物品有沒有被選取，沒有被選取時答案會是

$dp[i-1]$，這在 Subtask 2 的 DP 式中即為

$dp[i-1][j]$；有被選擇時對答案的貢獻在 Subtask 2 中便是剩下的

$dp[i-1][j-1]\times A_i$，注意到這裡對整體答案的貢獻，當

$dp[i-1][j-1]\times (j-1)$ 變成

$dp[i-1][j-1]\times A_i\times j$ 時，

$$(dp[i-1][j-1]\times (j-1)+dp[i-1][j-1])\times A_i=dp[i-1][j-1]\times A_i\times j$$ 也就是我們其實是在嘗試先把

$dp1[i-1]$ 加上

$dp2[i-1]$，再一起乘上

$A_i$。

綜合以上有選及沒選的 case，這就可以推導出最後的 DP 式子：

$$\begin{array}{rl}& dp1[i]=dp1[i-1]\times (A_i+1)+dp2[i-1]\times A_i\\ & dp2[i]=dp2[i-1]\times (A_i+1)\end{array}$$

於是我們就能以

$O(N)$ 的時間做出這題。

生函解

我不會QQ

令

$x$ 為一個形式變數並考慮這個形式多項式函數

$g(x)=\prod _i(A_{i}x+1)$。展開後

$x^k$ 的係數恰好就是所有大小為

$k$ 的子集合內元素乘積的總和。由於我們想要算的是這些總和乘以

$k$ 的值，於是可以聯想到我們要計算的是將多項式

$g$ 拿去微分後

$x^k$ 項的

$k$ 就會掉下來乘在係數上了。所以我們要算的值就是

$g^{\prime }(1)$。

English(WIP)

Subtask 1

$N\le 20$
Just enumerate through all subsets, trvial in

$O(N{2}^N)$ time.

Subtask 2

$N\le 1000$

We can consider dynamic programming here. Consider a knapsack-problem-like structure.

Define

$dp[i][j]$ as following. For all subsets

$S$ of size

$j$ of the first

$i$ element in

$A$,

${\displaystyle dp[i][j]=\sum \prod _{x\in S}x}$. Then the answer is trivially

${\displaystyle \sum _{j=1}^{N}j\times dp[N][j]}$.

Subtask 5

pD 小風的遊戲 (Game)

author 林煜傑 / setter 林煜傑

我們把城市視為點，道路視為邊，血量視為邊權。

First do the obvious intepretation to graph theory: let the cities be vertices, the roads be edges and the health be weights.

Partial (Only

$\mathtt{\text{YES}}/\mathtt{\text{NO}}$)

Chinese

首先很明顯

$h_{p_i}\ge i$，所以如果在等號成立下跑最短路的結果

$>d$，則一定是

$\mathtt{\text{NO}}$。唬爛一下會發現可以拿 50 分，這顯示

$\mathtt{\text{NO}}$ 的充要條件。

English

It's obvious that

$h_{p_i}\ge i$, when the equality holds, if the length of the shortest path

$>d$, the answer must be

$\mathtt{\text{NO}}$. It's also quite believable that it's sufficient. Implementing this solution gives

$50$ points, which proves the sufficiency using proof by AC.

Subtask 1 (

$M=N-1$)

Chinese

這代表圖是一棵樹。

注意到路徑是唯一的，所以就直接用 Partial 的判法，然後用某種方法找出所有路徑上的邊，把最大的邊調到夠高就會過了。

English

The graph is a tree.

Note that there's a unique path from

$S$ to

$T$. Using the heuristic above, we can then find the largest edge along the path from

$S$ to

$T$, adjusting the weight of this edge large enough gives the correct construction.

Subtask 2 (

$M=N$ and

$degree(i)=2$)

Chinese

這代表圖是一個環。

路徑恰有兩條，考慮有邊權最大的邊的路徑

$A$ 和另一個路徑

$B$，兩個路徑長分別是

$d_A,d_B$。

有三個情況。

• $d_B\le d$
  則對路徑
  $B$ 做跟 Subtask 1 一樣的事，但至少要把
  $h_{p_n}$ 調到
  $>d+1$。
• $d_B>d$ 且
  $d_A\le d$
  則對路徑
  $A$ 做跟 Subtask 1 一樣的事即可。
• $d_B>d$ 且
  $d_A>d$
  則無解。

English

The graph is a cycle.

There are exactly two paths, considers paht

$A$, which have the edge of the largest weight, and another path

$B$, the length of the two paths are

$d_A,d_B$ respectively

There are three cases.

• $d_B\le d$
  Do the same thing in Subtask 1 for path B. Remember to adjust other edges accordingly.

• $d_B>d$ and
  $d_A\le d$
  Do the same thing in Subtask 1 for path A.

• $d_B>d$ and
  $d_A>d$
  There's no solution

Subtask 3 (

$N\le 3000;M\le 5000$)

Chinese

考慮反覆找一個最短路。

如果最短路

$>d$，則一定

$\mathtt{\text{NO}}$。
如果最短路

$<d$，則調整這條最短路的最大的邊到足夠高使得這條路徑長度變恰好為

$d$，把邊權比這個邊還大的所有邊都設到至少

$d+1$。
如果最短路

$=d$，則我們已經調整完了，這時輸出

$\mathtt{\text{YES}}$ 以及調整完的所有邊權。

正確性是顯然的。

注意到每次至少會調整一條邊，因此重複跑最短路次數是

$O(M)$，最短路用 dijkstra 是

$O(M\log N)$。

時間複雜度是

$O(M^2\log N)$.

English

Repeatedly find the shortest path from

$S$ to

$T$.

if the length

$>d$, then the answer is

$\mathtt{\text{NO}}$.
if the length

$<d$, then adjust the largest edge in this path to make the length of this path

$D$, also adjust the edges that are bigger(but are not in the previous shortest path) to be just big enough to satisfy the constraints.
if the length

$=d$, then we're done and can output the solution

Subtask 4

Chinese

先預設

$h_{p_i}=i$，這是每個邊的最小可能權重，我們對目前的圖做一個二分搜。利用二分搜，我們找出最小的

$x$，使得如果只考慮邊權

$\le x$ 的邊，

$s$ 到

$t$ 的最短路徑

$\le d$。如果這個

$x$ 不存在，則輸出

$\mathtt{\text{NO}}$，否則一定是

$\mathtt{\text{YES}}$。

將所有邊權

$>x$ 的邊的邊權都調到

$>d$，即忽略他們。以下我們把邊權是

$>d$ 的邊視為不存在。找出一個

$s$ 到

$t$ 的最短路徑

$P$，路徑長為

$L\le d$。

注意到

$P$ 一定有邊權是

$x$ 的邊(稱為

$e$)，我們把

$e$ 的邊權調成

$x+d-L$。注意到對於任何

$s$ 到

$t$ 的路徑

$Q$，如果

$Q$ 不包含

$e$，則根據二分搜，我們知道

$Q$ 的長度

$>d$，如果

$Q$ 包含

$e$，假設他原本的路徑長是

$L^{\prime }$，根據最短路，

$L^{\prime }\ge L$，而改變

$e$ 之後的路徑長變成

$L^{\prime }+d-L\ge L+d-L=d$。

所以所有可能的路徑長都至少是

$d$，因此我們的構造是正確的，將

$h_{p_1},h_{p_2},...,h_{p_M}$ 設成

$1,2,\cdots ,x-1,x+d-L,d+1,d+2,...,d+N-x$ 即可。

用 dijkstra 來計算最短路，因此複雜度為

$O(M\log M\log N)$

English

First, check if

$S$ and

$T$ are connected, if not then the answer is

$\mathtt{\text{NO}}$.
If

$S=T$, check if

$D=0$.

First set

$w_{p_i}=i$, this is the minimum possible weight. Do a binary search on the graph to find the smallest

$x$ such that if we consider edges with weight

$\le x$, the shortest path from

$S$ to

$T$ is

$\le D$. if this

$x$ doesn't exist then the answer is

$\mathtt{\text{NO}}$, otherwise the answer is

$\mathtt{\text{YES}}$.

We can then ignore edges of weight

$>x$ by letting their weight greater than

$D$. We now treat those edges as non-exsistent. Find a shortest path

$P$ from

$S$ to

$T$ with length

$L\le D$.

Notice that

$P$ must have the edge of weight

$x$ due to its definition, call that edge

$e$, change the weight of

$e$ to be

$x+D-L$. We claim that this is a valid construction. For every path

$Q$ from

$S$ to

$T$, if

$Q$ doesn't have

$e$, the length of

$Q$ is

$>D$ by the binary search property; if

$Q$ does have

$e$, the length of

$Q$ is

$>L$, so after the change the length of

$Q$ will be greater than

$D$. Our claim was proven.

Set

$w_{p_1},w_{p_2},...,w_{p_M}$ to

$1,2,\cdots ,x-1,x+d-L,d+1,d+2,...,d+N-x$ is the solution.

We use Dijkstra to calculate the shortest path, So the time complexity is

$O(M\log M\log N)$

pG 幸運數字 (Number)

author 林煜傑 / setter 吳柏翰

首先，由簡單的greedy的想法可知道題目的意思即可轉換成
給定正整數

$N,M$ 以及

$N$ 個正整數

$a_1,a_2,\dots ,a_N$。
有

$Q$ 筆詢問，每次詢問會給你一個正整數

$b$，請回答有多少個

$i$ 使得

$a_i$ 在

$b$ 進位制下的位數和恰好是

$M$。

First, with simple greedy, the problem can be transformed as finding how many of of the given integers has digit sum of exactly

$M$ in base

$b_i$

Subtask 1：

$N,Q\le 1000$

Chinese

直接模擬即可，由於

$x$在轉換成

$b$進位的次數最多為

$lo{g}_{b}x$次，所以此作法的複雜度為

$O(NQlogC)$，其中

$C$為值域(2e6)

English

Direct calculation suffices, because the number of digits of

$x$ in base

$b$ is at most

$lo{g}_{b}x$, this solution has a time complexity of

$O(NQlogC)$, where

$C$ is the range (2e6)

以下的子題都是直接算出所有值域以下的所有

$b$的答案記下來，之後每筆詢問

$O(1)$輸出，以下記

$C$代表子題中

$a_i$的上限

In the following subtasks, we try to calculate the answer for every base in the range, and answer the queries in

$O(1)$ time. Let

$C$ be the upper limit of

$a_i$ in each of the subtasks.

Subtask 2：

$C=40000$

Chinese

觀察到當

$b$大於

$\sqrt{C}$時，

$C$以下的正整數在

$b$進位的表示下最多只有

$2$位，所以小於等於

$\sqrt{C}$的

$b$就直接把

$1$到

$C$中的所有數轉成

$b$進位後驗證位數和是否為

$M$，這邊的複雜度是

$O(C\sqrt{C}logC)$，大於

$\sqrt{C}$的

$b$的話位數和若要是

$M$只有

$(1)(M-1),(2)(M-2),\dots ,(M-2)(2),(M-1)(1)$這M種可能，且一旦表示的數超過值域就可以不用再計算，故可以證明這邊的複雜度是

$O(ClogC)$，所以總複雜度即為

$O(N+C\sqrt{C}logC+Q)$

English

Notice that when

$b$ is greater than

$\sqrt{C}$, integers below

$C$ have at most

$2$ digits in base

$b$. For integers below $\sqrt{C} we use the brute force method described above; for integers above

$\sqrt{C}$ we can enumerate the two digits and check. In the first part the time complexity is

$O(C\sqrt{C}logC)$; in the second part the time complexity is

$O(ClogC)$. The total time complexity is

$O(N+C\sqrt{C}logC+Q)$.

Subtask 3：

$C=300000$

Chinese

跟subtask2同樣的想法，再觀察到在計算

$1$到

$C$的

$b$進位表示法時不用每次都重算，而是可以把計算

$k-1$的結果加上

$1$，能進位就進位後就可以得到一個正確的

$k$的

$b$進位表示法，而這種作法進位的複雜度均攤為

$O(1)$，所以此時的總複雜度就變為

$O(N+C\sqrt{C}+Q)$

English

Following the idea in Subtask 2. We can then notice that when calculating the base

$b$ representation of

$k$ we can use the representation of

$k-1$, this means all the calculation in a base can be done in

$O(1)$ amortized, optimizing the solution to

$O(N+C\sqrt{C}+Q)$.

subtask 4：

$C=2000000$

Chinese

只有前面的分塊的想法理論上絕對會在這個子題TLE，所以我們需要更進一步的觀察

觀察到在

$b$進位底下，若是一個正整數

$x$在

$b$進位底下的位數和為

$y$，則

$x$跟

$y$會在模

$b-1$下同餘，所以對於每一個進位

$b$，所有可能使得在

$b$進位底下位數和為

$M$的數字

$x$必定型如

$M+(b-1)\times n$，其中

$n$為非負整數，而每次加

$b-1$的進位次數一樣會均攤成

$O(1)$，故這個做法的複雜度為

$O(N+ClogC+Q)$

English

You should get TLE with only the square root technique no matter what, more observation is needed for this subtask.

Notice that in base

$b$, if an integer

$x$ has digit sum

$y$, then

$x\equiv y(\text{mod b-1})$. So for every base

$b$, every candidate must be of the form

$M+(b-1)\times n$, where

$n$ is a non-negative integer. It turns out the adding

$b-1$ in base

$b$ multiple times is also amortized

$O(1)$, so this solution has a time complexity of

$O(N+ClogC+Q)$.

pF LCA 遊戲 (LCA)

author 王均倍 / setter 王均倍 / solution 賴昭勳 / editorial 王均倍

Observation 1

Chinese

我們把整題的方向轉一下：根永遠訂在 A，問 C 得到的答案 D，代表的是 B 和 C 的 LCA

English

Do a simple reinterpretation: the root is always at A, the answer D we get when we query C means the LCA of B and C.

Observation 2

Chinese

如果我們改問 C 的小孩

$C^{\prime }$ 那我們可以獲得更多資訊

English

If we instead of asking

$C$, ask its child

$C^{\prime }$, then we get more information.

Observation 3

Chinese

永遠只需要問葉子

English

We always query leaves.

Full Solution

Chinese

既然有了 Observation 3，我們可以考慮一下當我們詢問一個葉子會發生什麼事情。

為了方便說明，我們假設

$A$ 有

$k$ 個小孩：

$x_1,x_2,\dots ,x_k$，而我們現在詢問的葉子

$y$ 就在

$x_1$ 所在的子樹底下。

此時有兩種可能的情形：

1. 得到的答案是
   $A$：那我們就得到的資訊恰好是「答案不在
   $x_1$ 的子樹底下」
2. 得到的答案不是
   $A$：那我們就得到的資訊至少是「答案在
   $x_1$ 的子樹底下，不在
   $A$ 或者是
   $x_2,x_3,\dots x_k$ 的子樹底下」。

這邊好像有點 DP 的感覺了：問一片葉子，我們要嘛排除整個子樹，要嘛知道答案就在這個子樹裡面。

於是我們先訂個狀態：dp[x] 代表如果已知答案在 x 的子樹底下，最多還要問幾次。

轉移也很明顯了，因為我們希望盡可能的問最少次，所以策略必然是先挑那個如果中了就需要問很多次的子樹，因此只要把 child 的 DP 值排序，依序詢問並取 max 即可。

pC 頒獎音樂 (Ceremony)

author 侯欣緯 / setter 侯欣緯 / editorial 侯欣緯、蔡旻諺

Hint: 這題要怎麼寫 checker？
Hint: How is the checker implemented?

Observation 1

Chinese

Observation 1.

$a_1,a_2,\dots ,a_N$ 可以變成

$b_1,b_2,\dots ,b_N$ iff 滿足以下條件：

• $a_1=b_1$
• $a_N=b_N$
• unordered pair 的 multiset
  $\{(a_i,a_{i+1})\}=\{(b_i,b_{i+1})\}$，也就是所有相鄰數字的 unordered pair 不變

Proof. 很明顯要滿足這些條件，才有辦法把

$a$ 變成

$b$。考慮我們現在要把

$a$ 變成一個滿足這些條件的

$b$。令

$k$ 為最小的滿足

$a_k\ne b_k$ 的數字，如果

$k$ 不存在代表

$a=b$。否則，根據上述條件，

$1<k<N$。

根據上述條件，存在一個

$i$ 滿足

$k<i\wedge a_i=b_k$，並且分為兩種 case：

• $a_{i+1}=b_{k-1}$
  把
  $a$ 的
  $[k-1,i+1]$ 反轉後，就能讓
  $a_k=b_k$。
• $a_{i-1}=b_{k-1}$
  令
  $u=a_{i-1}=b_{k-1}=a_{k-1}$、
  $v=a_i=b_k$（別忘了對於
  $t<k$，
  $a_t=b_t$），
  $a$ 會長成像這樣：
  
  $$\begin{array}{cccccc}\dots & u& \dots & u& v& \dots \\ \dots & a_{k-1}& \dots & a_{i-1}& a_i& \dots \end{array}$$
  如果存在
  $k\le l<i\le r$，滿足
  $a_l=a_r$，那麼反轉
  $[l,r]$ 後，會變成第一種 case。如果對於任何滿足上述條件的
  $i$ 都不存在這樣的
  $(l,r)$ 的話，考慮把
  $a_{k-1},\dots ,a_N$ 和
  $b_{k-1},\dots ,b_N$ 當成一張以它們為一條歐拉路徑的圖。由於
  $u$ 在
  $a_{k-1},\dots ,a_N$ 出現了兩次，我們知道
  $b$ 會長成
  
  $$\begin{array}{cccccc}\dots & u& v& \dots & u& \dots \\ \dots & b_{k-1}& b_k& \dots & b_{>k}& \dots \end{array}$$
  根據上述條件，這兩張圖是同構的，因此根據
  $b$，圖上會有一個包含邊
  $(u,v)$ 的環。然而，因為我們要的
  $(i,l,r)$ 是不存在的，把
  $a$ 裡的任一個
  $(u,v)$ 拔掉（其實根本只有一個），都會變成兩條不共點的路徑，因此拔掉
  $(u,v)$ 後圖會變不連通，矛盾。由此可知，一定存在這樣的
  $(i,l,r)$。

綜上所述，我們總是可以把

$a_k$ 變成

$b_k$，一直換之後

$a$ 就會變成

$b$。

English

Observation 1.

$a_1,a_2,\dots ,a_N$ can be transformed into

$b_1,b_2,\dots ,b_N$ if and only if the following condition holds：

• $a_1=b_1$
• $a_N=b_N$
• the multiset of unordered pairs
  $\{(a_i,a_{i+1})\}=\{(b_i,b_{i+1})\}$, that is, the set of unordered pairs of adjacent numbers doesn't change.

Proof. It's obvious that the conditions are necessary. We now prove the sufficiency. Let's say

$a$ and

$b$ satisfy the constraints, we want to transform

$a$ into

$b$. Let

$k$ be the smallest number such that

$a_k\ne b_k$, if there' no such

$k$ means

$a=b$, otherwise, we have

$1<k<N$.

By the constraints, we know there exists an

$i$ that satisfies

$k<i\wedge a_i=b_k$, with the following 2 cases：

• $a_{i+1}=b_{k-1}$
  reverse the interval
  $[k-1,i+1]$ in
  $a$, then
  $a_k=b_k$.
• $a_{i-1}=b_{k-1}$
  Let
  $u=a_{i-1}=b_{k-1}=a_{k-1}$,
  $v=a_i=b_k$ (Note that for all
  $t<k$,
  $a_t=b_t$),
  $a$ can be visuallized as：
  
  $$\begin{array}{cccccc}\dots & u& \dots & u& v& \dots \\ \dots & a_{k-1}& \dots & a_{i-1}& a_i& \dots \end{array}$$
  If there exists
  $k\le l<i\le r$ satisfying
  $a_l=a_r$, then reversing
  $[l,r]$ reduce the problem to the first case. We'll prove that such reduction is always possible. We prove this by contradiction, that is, for every such
  $i$ there doesn't exist such pair
  $(l,r)$. Consider
  $a_{k-1},\dots ,a_N$ and
  $b_{k-1},\dots ,b_N$ as two different Eulerian path on a graph (with number as vertex and edge as adjacent pairs). Because
  $u$ appears at least twice in
  $a_{k-1},\dots ,a_N$, we can visualize
  $b$ as
  
  $$\begin{array}{cccccc}\dots & u& v& \dots & u& \dots \\ \dots & b_{k-1}& b_k& \dots & b_{>k}& \dots \end{array}$$
  Notice that the two graphs are isomorphic. From the visualization of
  $b$, the graph has a cycle containing
  $(u,v)$. However, because there's no such
  $(i,l,r)$, removing the
  $(u,v)$ pair from
  $a$ disconnects the graph. We have arrived at a contradiction, meaning such
  $(i,l,r)$ must exist.

In conclusion we can always transform

$a_k$ into

$b_k$, repeating this transforms

$a$ into

$b$.

Subtask 1.

Chinese

利用 Observation 1，一個

$O(N!\cdot N\log N)$ 的暴力解便呼之欲出。

English

A brute force solution of

$O(N!\cdot N\log N)$ using Observation 1. is simple.

Subtask 2.

Chinese

利用 Observation 1，我們觀察到序列的「

$1$ 與

$2$ 連續區間的交替次數」肯定是固定的，且我們已知開頭的數字跟原序列相同。

基於這個性質，我們可以先用最少的

$1$ 和

$2$ 滿足交替次數後，注意到每個非頭尾的數字都在期待著自己可以被多放上同樣的數字來讓不好聽的區段盡量少。

而在諸如

$121$ 這樣的序列中間放上一個

$2$ 並不會影響交替次數，還可以增加一組

$22$ 的相鄰對。

因此，貪心的利用我們手上統計出來剩餘的

$11$ 和

$22$ 相鄰對放

$1$ 和

$2$ 到每個中間的數字旁邊，放到不夠或放不下為止，如果放不下則隨便找地方塞就可以了。

可以在

$O(N)$ 的時間內完成。

English

Using Observation 1, we can see that the number of alternation between 1's and 2's is constant, also the

t and end must match.

Based on this, we first use the minimal amount of 1 and 2 to satisfy the number of alterations. Then, we notice that every number in the middle can utilize another of the same number to decrease the number of bad triplets. For example, in triplets like

$121$, adding a 2 is valid, and it's good because it decreases the number of bad triplets.

Therefore for this subtask, we can greedily place

$11$ and

$22$ to decrease the bad triplets count, if there's numbers left just place them anywhere. This solution works in

$O(N)$.

AC

Chinese

把每個

$(a_i,a_{i+1})$ 視為一條無向邊放在圖上，

$a$ 會是一條歐拉路徑。我們的目標是找到一條起終點不變的歐拉路徑當作答案。

每當走過一條邊，從

$u$ 走到

$v$ 之後，我們會希望走到的下一個點

$w$ 能滿足

$u,v,w$ 不是難聽的。如果我們對於每個點，都將它的鄰邊兩兩配對，每一對都表示「當我從其中一條邊走過來時，我就要走到跟他配對的那條邊」，直覺上最好的配法是盡量讓連接小點和大點的邊配對，如果不夠的話就配自環的邊，逼不得已才小配小、大配大。而一個壞組合就是這個配對會製造一個壞旋律（也就是小邊配小邊或大邊配大邊）。如果起終點不同，起終點可以會有一個不配對的邊，把無法配到好組合的一條邊拿出來就好。顯而易見地，這樣配出來的壞組合數量是答案的下界。

它之所以有可能不是真正的答案，是因為這樣子配對之後，不一定會是一整條路徑，而是最多一條路徑和一些迴路。不過，其實這就是真的答案，因為我們可以將路徑與迴路或迴路與迴路合併。

先考慮迴路與迴路合併的狀況，假設我們現在要將兩個有共點的迴路合併，從這兩迴路挑出一個共的點鄰邊的配對，接著分成幾種情況：

1. 兩個配對都是好組合。好組合的形式一定是一條大或中邊，和一條小或中邊（中邊 = 自環），把這兩個配對裡的大中邊交換一下配對對象，就能把它們換成兩個新的好組合，並將兩個迴路合起來。
2. 其中一個配對是好組合、另一個是壞組合。壞組合的形式一定是兩條小邊或兩條大邊，將兩個配對任意交換一個人，不管怎樣都會得到一個好組合和一個壞組合，並且可以把兩個迴路合起來。
3. 兩個配對都是壞組合。由於我們會盡量讓大邊和小邊配對，徑這兩個組合一定是全大邊或全小邊，不管怎麼交換配對對象，一定都還是兩個壞組合，但我們還是把兩個迴路合起來了。

由此可知，我們可以在不改變壞組合數量的情況下，把兩個迴路合起來。迴路與路徑合併的情況相似，如果它們共用的點有出現在路徑的中間，那和上面是一樣的。反之又分成幾種 case：

1. 迴路的配對是好組合。看路徑的那條鄰邊是大邊還是小邊，把它配對到迴路的配對中，會讓新配對是好組合的那條邊，而另一條邊就變成新的路徑起終邊。
2. 迴路的配對是壞組合。根據 greedy 的配對方法，迴路的配對和路徑的鄰邊，這三條邊一定是全大或全小，一樣任意重配後，就會把兩者合併。

因此同樣地，我們可以在不改變壞組合數量的前提下將路徑與迴路合併。綜上所述，我們可以把所有路徑和迴路都合併，並且答案就是剛剛說的下界。

在實作上，考慮一般的歐拉路徑作法。每當 DFS return 時，代表我們其實是找完了一個路徑或一個迴路。從某個點 return 回到本來的點，再往另一條邊走時，其實就是在做 merge 兩個迴路，或者一個路徑和一個迴路的事情。

因此，想像我們已經用前面的 greedy 方法配好邊了，DFS 時就先往配對的邊走，如果回來時我們還必須往別的邊走，那代表發生了需要 merge 的事情。在不是兩種狀況的第一個 case 時，怎麼走都是沒差的，不然我們會需要保持好組合還是好組合，結論是永遠盡量往「和剛剛過來的邊會是好組合」的邊 DFS 即可。注意如果剛剛走過來的邊是中邊（自環），那麼要判斷一下它在本來的配對裡是配對大邊（代表它的身分是小邊）還是配對小邊（代表它的身分是大邊），才能決定從配對邊 return 回來後，走其他的邊要先走什麼。

注意到每個節點的配對是獨立的，而且在決定一個隨意的配對後，我們總是有辦法製造出一條壞組合數量相同的歐拉路徑，因此只要你有辦法決定出一個壞組合數量最少的配對，你不管怎麼配都會是好的。（記得歐拉路徑不要寫爛。）

English

Now the transformation is clear: we have a Eulerian path

$(a_i,a_{i+1})$, and our goal is to find another Eulerian path with the same starting and ending point, while minimizing the bad triplet count.

When passing through an edge, we would hope that the next edge wouldn't form a bad triplet with the current edge, therefore if we pair all the edges around a certain vertex, as in "If I come from this edge, this is the edge I'll go next", the heuristic is that we want to pair edges to minimize the number of bad triplets, and only construct bad triplets if we're forced to. It can be seen that this is the lower bound of bad triplet count.

However, this may not be possible due to the fact that this pairing might not produce a path, but instead (at most) a path and several cycles.

Now we have to convince ourselves that this is also the upper bound, otherwise this problem wouldn't be solvable, would it?

We have two tasks left in order to make our dream come true: merging cycles and merging a path and a cycle. It's all casework from now.

In the following discussion we use the current vertex root, so we can classify edges as G(pointing to a bigger number than root), E(pointing to itself), L(pointing to a smaller number than root), and GE means an edge that is either G or E; LE means an edge that is either L or E.

Let's consider how to merge cycles first. When we merge two cycles sharing a point, there are three cases

1. Both pairs are good pairs. Good pairs are pairs of LE and GE, pair the LE of one with the GE of another, we successfully merged the cycles.
2. One of them is good, but the other is bad. There are three of LE(GE) and one of GE(LE), no matter what we do, there will be exactly one bad triplets.
3. Both pairs are bad. In this case we know we can't do better, so we just do whatever (a motto in life).

Finally consider how to merge a path and a cycle, if the contact point isn't an endpoint, it's the same as the cycle case, otherwise two more cases follows

1. The pair on the cycle is good. For this case we can check the edge on the path is LE or GE, and pair accordingly.
2. The pair on the cycle is bad. Due to the greedy pairing, we know the edges are all G or all L, we still can't do better, so do whatever.

We have now successfully constructed the lower bound.

As for implementation, we can do a slight modification on the Eulerian path algorithm. Whenever the DFS returns, it means we're done finding a path or a cycle, when we return to the original point, and going out to the next edge, we are essentially merging the parts.

If we have paired the edges for each vertex, we can traverse the designated edge first when we're doing DFS, if we're back to where we started, then it's time to merge, the only case we need to worry about is the first case on both situation, because for other cases we just do whatever. So the implication is "walk on good edges first" when we're DFS is good. However for E edges we need to check whether its supposed to be a G or an L, we can do this by checking what it's paired to.

Notice that the pairing for each vertex is independent. Also, after an optimal pairing is found, the construction of Eulerian path is always possible, therefore we only need to worry about finding a good pairing (and implementing Eulerian path correctly).

code

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; \
    pvaspace=true;\
    b << pva;\
}\
b << "\n";}
#define SZ(a) int(a.size())

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

int main(){
    StarBurstStream

    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<deque<pii>> g(n + 1);
    vector<int> big(n + 1), small(n + 1), sum(n + 1), des(n + 1);
    
    auto addedge = [&](int u, int v, int id){
        g[u].eb(mp(v, id));
        if(u < v) big[u]++;
        else if(u > v) small[u]++;
        sum[u]++;
    };

    for(int i = 1; i <= n; i++){
        cin >> a[i];
        if(i > 1) addedge(a[i - 1], a[i], i), addedge(a[i], a[i - 1], i);
    }

    for(int i = 1; i <= n; i++){
        lsort(g[i]);
    }

    vector<int> ans;
    vector<bool> vst(n + 1);
    function<void(int, int)> dfs = [&](int now, int lst){
        while(!g[now].empty()){
            int s;
            if(lst == -1 || lst == now) s = big[now] >= small[now];
            else s = lst < now;
            int nxt, e;
            if(s){
                tie(nxt, e) = g[now].back();
                g[now].pob;
            }
            else{
                tie(nxt, e) = g[now].front();
                g[now].pof;
            }
            if(vst[e]) continue;
            vst[e] = true;
            dfs(nxt, now);
        }
        ans.eb(now);
    };

    dfs(a[1], -1);
    reverse(iter(ans));
    
    int total = 0;
    for(int i = 1; i < n - 1; i++){
        if(ans[i - 1] < ans[i] && ans[i] > ans[i + 1]){
            total++;
        }
        else if(ans[i - 1] > ans[i] && ans[i] < ans[i + 1]){
            total++;
        }
    }

    printv(ans, cout);

    return 0;
}

pH 圓規 (Compass)

author 侯欣緯 / setter 侯欣緯 / solution 賴昭勳 / editorial 賴昭勳

以下用

$n$ 來表示

$r$ 的最大值。

Let

$n$ denote the maximum of

$r$.

Subtask 1

Chinese

注意到，我們可以把一開始塗黑的格子

$(r,0)$ 當成一個信號，如果格子 AND 自己是黑色的，我們就能把那個結果拿去放到該半徑圓上所有格子。
這樣的次數會是所有圓的周長總和，大約是

$\pi n(n-1)$

English

For each of the

$n$ circles, we color the circle of radius

$i$ with the color of

$(i,0)$, this takes around

$\pi n(n-1)$ operations.
In practice, we can use or_col to color each cell, so we don't accidentally color a black cell white.

Subtask 2

Chinese

顯然的，每個圓一定是上下對稱和左右對稱。因此我們在預處理的時候可以只看第一象限，然後用 or_col 跟 or_row 把這個圖形對折兩次。這樣的詢問次數會是原本的大約

$1/4$ 倍。

English

Obviously every circle is symmetric around x and y axis, so we only pre-process the first quadrant, and use or_col and or_row to mirror the image twice, this takes around 4 times less operations.

Subtask 3

Chinese

以下的解都會需要用到 Subtask 2 的鏡射技巧。

• Not model solution 1: ~61pts
  可以發現到圓上會有許多連續一排的黑色格子。因此我們希望能把這一排連續的東西在一次操作做出。要支援這個功能的話，我們需要一個足夠長的連續黑色區段。這可以用

  $O(\log n)$ 次的倍增做到。之後再用前面的方式預處理即可

• Not model solution 2 ~55pts:
  把表格當成一個計算機，直接計算需要塗哪些格子。這個解是原本的官解，實做難度一點點點點高，可能要實做加法跟乘法之類的東西。

• Model Solution:
  想法：先把第一象限依照斜對角分成上面和右邊兩半，因為兩邊的情況對稱所以之後只討論右邊。對於每一個

  $x$ 值，我們希望只塗上最小的
  $y$ 一格，之後對一整排的格子把訊號推上去。
  具體來說，一開始預處理的格子可能有這些：
  
  

然後我們可以用

$n$ 次的 or_row 和 or_col 把所有在那些格子右上方的格子塗黑。

注意到如果我們將相鄰的兩排 xor，可以找到兩個

$x$ 值中間所有

$y$ 的格子。但是這樣的話上面的格子會少，因此我們由下到上再做一遍。
如下圖：

我們可以用其他象限的空間當成是記憶體，儲存這兩個圖形的長相。最後只要把這兩張圖 OR 起來就會接近最後的答案了

接下來只要把

$x$ 軸跟

$y$ 軸多餘的部份處理掉就做完了。除了預處理之外，後面的運算只需要

$O(n)$ 次操作。
這邊寫完的話會發現還是是錯的，原因是因為在某些

$r$ 值，斜對角線上會多一格，可以觀察

$r=3$ 的狀況。這個 case 無法用前面的方法解決，但是幸運的，會發生這件事情的

$r$ 值在

$r\le 3000$ 時，只有四個可能：

$r=3,17,99,577$，因此我們特判這些狀況即可（這些例外的數值可以寫一個程式輕鬆找出）。

這樣會是約

$2.6\times {10}^6$ 次，有大約

$65$ 分。

• Actual Full Solution:
  目前所有的作法都需要個別處理
  $r$ 值，但是其實有辦法把兩個相鄰的
  $r$ 值操作同時處理。具體來說，對於一個
  $r$ 值，我們把他所有會需要預處理的格子與
  $(r,0)$ 之間當成一個向量，那麼如果有一段連續的
  $r$ 值共享同一個向量，那就可以用 or_row 或 or_col 平行處理。預處理所有的向量之後，可以用一個簡單的 two-pointers 做完。

English

The following solutions all use the reflection idea from Subtask 2.

• Not model solution 1: ~61pts

Notice that there are many consecutive black cells on the circle, an idea is to try to use only one operation for each segment. When we're processing the

$i$-th circle, we should copy

$(i,0)$ multiple times using doubling (we could use some temporary space in other quadrant), this part contribute

$O(\log n)$ operations per circle.

After this we just do similar things as previous subtasks.

• Not model solution 2 ~55pts:

Implement a binary calculator in the grid to directly calculate what cells are black. This was the original official solution, which is a tad bit difficult to implement. It may require implementing addition and multiplication.

• Model Solution:

Split the first quadrant again into the top part and the right part. As they are identical so we'll only discuss the right part.
As in previous solutions, we do this circle by circle.

Main idea: for each

$x$ we only color the cell with the smallest

$y$ in that column, then push the colors upward.
For example we might only color these cell first.

Then we use

$n$ or_row's and or_col's To color every cell towards the upper right black.

For the right part we can find its contour by xor-ing adjacent columns, while for the upper part we xor adjacent rows.
Like the following figure.

Again we use other quadrants to store these two contours, then or the resulting two figures.

After this we just need to clean up the leftover black cells. Apart from preprocessing, the rest only takes

$O(n)$ operations.
You'll discover that this solution is still wrong, the reason is because for some

$r$, there will be one more cell on the diagonal, for example we can look at the case when

$r=3$. We have to process those edge cases one by one, but luckily there are only

$4$ edge cases when

$r\le 3000$:

$r=3,17,99,577$ (this can be found readily with another program). Fix those up and we're done.

This takes around

$2.6\times {10}^6$ operations, giving around

$65$ points.

• Actual Full Solution:

All previous solutions process all circles separately, however it's actually possible to process neighboring circles together. The way to do it is to draw many vectors from

$(r,0)$ to points on the

$r$-th circle, if for some neighboring

$r$'s they share some vector, we can process them together with or_col or or_row. After finding out all the vectors we can use a simple two-pointer method to finish this problem.

AC code

//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "Compass.h"
using namespace std;
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
#define iter(v) v.begin(),v.end()
#define SZ(v) (int)v.size()
#define pb emplace_back
const int maxr = 3000;
int row_vec[maxr+5][maxr+5], col_vec[maxr+5][maxr+5];
void get_corner(int r){
	int cnt = 0;
	or_row(r, 0, r, 0, 0, r, 1);	
	cnt++;
	{
		int y = 0;
		for (int x = r - 1;x >= 0;x--) {
			while (int(sqrt(r*r-y*y)) > x) y++;
			if (y > x) break;
			row_vec[r][r-x] = y;
			//or_row(r, 0, r, 0, x, y, 1);
			cnt++;
		}	
	}
	{
		int x = 0;
		for (int y = r - 1;y >= 0;y--) {
			while (int(sqrt(r*r-x*x)) > y) x++;
			if (x >= y) break;
			col_vec[r][r-y] = x;
			//or_row(r, 0, r, 0, x, y, 1);
			cnt++;
		}
	}	
	//cout << r << " " << cnt << "\n";
}
void combine() {
	for (int dx = 1;dx <= maxr;dx++) {
		for (int r = 1;r <= maxr;r++) {
			if (row_vec[r][dx] == 0) continue;
			//cout << r << " " << dx << " " << row_vec[r][dx] << "\n";
			int tmp = r;
			while (tmp <= maxr && row_vec[tmp][dx] == row_vec[r][dx])tmp++;
			int y = row_vec[r][dx];
			//cout << r << " " << tmp << " " << dx << " " << dy << "\n";
			or_row(r, 0, r, 0, r - dx, y, tmp - r);	
			r = tmp-1;
		}	
	}
	for (int dy = 1;dy <= maxr;dy++) {
		for (int r = 1;r <= maxr;r++) {
			if (col_vec[r][dy] == 0) continue;
			int tmp = r;
			while (tmp <= maxr && col_vec[tmp][dy] == col_vec[r][dy])tmp++;
			int x = col_vec[r][dy];
			or_col(0, r, 0, r, x, r - dy, tmp - r);
			r = tmp-1;
		}	
	}
}
void draw_circle(){
	int store = maxr + 20;
	for (int i = 1;i <= maxr;i++) get_corner(i);
	combine();

	or_row(0, 0, 0, 0, 0, -store, maxr+1);
	or_col(0, 0, 0, 0, -store, 0, maxr+1);

	for (int i = 1;i <= maxr;i++) or_row(0, i, 0, i-1, 0, i, maxr+1);			
	for (int i = 1;i <= maxr;i++) or_col(i, 0, i-1, 0, i, 0, maxr+1);			
	
	for (int i = 0;i <= maxr;i++) xor_row(0, i, 0, i-1, -(maxr+5), i, maxr+1);
	for (int i = 0;i <= maxr;i++) xor_col(i, 0, i-1, 0, i, -(maxr+5), maxr+1);
	for (int i = 0;i <= maxr;i++) or_row(-(maxr+5), i, 0, -(maxr+5)+i, 0, i, maxr+1);
	//clear
	for (int i = 0;i <= maxr;i++) {
		set_row(-(maxr+5), i, maxr+1, 0);
		set_col(i, -(maxr+5), maxr+1, 0);
	}
	and_row(0, 0, 0, -store, 0, 0, maxr+1);
	and_col(0, 0, -store, 0, 0, 0, maxr+1);
	
	or_row(3, 0, 2, 2, 2, 2, 1);
	or_row(17, 0, 12, 12, 12, 12, 1);
	or_row(99, 0, 70, 70, 70, 70, 1);
	or_row(577, 0, 408, 408, 408, 408, 1);

	for (int i = 1;i <= maxr;i++) or_col(i, 0, i, 0, -i, 0, maxr+1);
	for (int i = 1;i <= maxr;i++) or_row(-(maxr+1), i, -(maxr+1), i, -(maxr+1), -i, 2*(maxr+1));

	set_row(0, -store, maxr+1, 0);
	set_col(-store, 0, maxr+1, 0);

}

• Note
  官解次數大約
  $7.34\times {10}^5$ 次。
  這題還可以再壓（吧）。

The official solution uses around

$7.34\times {10}^5$ operations
It could probably still be optimized.

pE 好多個三口羊 (Escape)

author 賴昭勳 / setter 賴昭勳

Subtask 1,2,3

Chinese

首先考慮一個起始點在什麼情況下會被 merge。經過一些觀察，可以發現這個起始點的上下左右四個方向都要有三口羊，如附圖。

一個起始點的上面是左上的直線跟右上的直線中間的區域（包含線上）。X 代表三口羊的位置。注意到右下角的三口羊同時算為右邊跟下面。如果要嚴謹證明的話，可以考慮四個方向的三口羊與 8e7 的距離。每當 8e7 走一步，所有方向代表的三口羊與 8e7 的距離不會減少，而至少有一個方向會減少，因此必定存在一個時間會重疊。這樣也可以推得另一個性質：如果 8e7 是安全的，他一定能往正上/正下/正左/正右其中一個方向逃出。因此可以枚舉所有起始點（或是用怪怪 DFS）做出 Subtask 1。以下會用「上/下/左/右」覆蓋點代表蓋住該點那個方向的三口羊。

觀察一個三口羊對哪些點有影響。一個三口羊對所有下方（左下直線到右下直線的區域）可以作為上覆蓋點。其他方向以此類推，如附圖：

因此，我們可以對每個點維護他是否存在上/下/左/右覆蓋點，如果四個都存在就代表該點是不安全的。而更新覆蓋點的事情可以用 DFS 做到，這樣足以過 Subtask 2，複雜度

$O(C^2)$。

可以發現，這題需要用要的形狀都是轉 45 度的三角形，因此我們可以考慮平面逆時針旋轉 45 度的狀況。以下解釋都用旋轉過後的狀況。
考慮一直排有哪些點是不安全的。原本覆蓋點的條件會變成：該點左上/左下/右上/右下都需要有一隻三口羊。因此我們可以考慮左邊最高/最低的三口羊，以及右邊最高/最低的三口羊，他們會在直排上形成兩個區間。可以發現不安全的點數即為兩個區間的交集長度，如附圖：

紅色為交集的區間，而黑色圓圈是不安全的點，注意到因為有轉 45 度，所以要考慮每個點的奇偶性的狀況。

經過前面的觀察，我們可以暴力維護每一排的前綴高度（y 值）最大/最小值和後綴最大/最小值，每次加點之後再暴力詢問每一排得到答案，這樣能過 Subtask 3，複雜度

$O(NC)$。

以下附 Subtask 3 的標程

English

Firstly let's consider what makes a point dangerous, after some observation, we can see that to make a point dangerous requires Three-Mouthed Sheep in each cardinal direction, as the following graph shows, X means there's a three mouthed sheep there.

The diagonal splits the plane into 4 parts. Note that sheep on the diagonal counts for two directions at the same time. For a more rigorous proof, consider the bounding box formed by Three-Mouthed Sheep. Whenever 8e7 moves, Three-Mouthed sheep can move in a way that decreases the size of the bounding box. After enough moves the size of the bounding box is 0 and 8e7 is merged (poor 8e7!).

With this, another implication can be made: if he is safe in that square, there exists one escape route that is a straight line. This gives a brute force method of solving Subtask 1 (You can also try some weird DFS ideas).

From now on we use Up/Down/Left/Right Scout with respect to a point P to denote the Three-Mouthed Sheep guarding that side when 8e7 starts at P.

Let's observe how a Three-Mouthed Sheep is useful. A Three-Mouthed Sheep can be Up Scout for points below, and similar for other directions, as the following figure shows:

Therefore we can maintain for each point whether all directions are guarded, if so then that point is dangerous, Updating can be done with DFS. This idea is enough to pass Subtask 2 with a time complexity of

$O(C^2)$.

A common trick used in these types of problems is to rotate the plane 45 degrees, so let's do that. Now each point requires a UR/UL/DR/DL scout in order to be dangerous. Therefore for each column, we consider the top and bottom Three-Mouthed Sheep on both side of the column, their projection to the current column forms two segments, it's easy to see the size of their intersection is the number of dangerous points on that column, as the following figure shows.

The red segment denotes the intersection, while black circles denotes dangerous points. Notice that because we've rotated 45 degrees, we have to consider the parity for each point.

With these observations, we can write an algorithm maintaining the prefix/suffix min/max of the

$y$ values, with brute force updates. This solution passes Subtask 3. with a time complexity of

$O(NC)$.

Here we give a piece of code that passes Subtask 3.

Code

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 400005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 2*maxn;
int pmin[maxn], pmax[maxn], smin[maxn], smax[maxn];
int main() {
	io;
	int n, C;
	cin >> n >> C;
	C++;
	int m = 2*C;
	for (int i = 0;i < m;i++) {
		pmin[i] = smin[i] = inf;
		pmax[i] = smax[i] = -inf;
	}
	for (int i = 0;i < n;i++) {
		int tx, ty;
		cin >> tx >> ty;
		pii p = {tx - ty + (C-1), tx + ty + (C-1)};	
		for (int j = p.ff;j < m;j++) {
			if (p.ss < pmin[j]) pmin[j] = p.ss;	
			else break;
		}
		for (int j = p.ff;j < m;j++) {
			if (p.ss > pmax[j]) pmax[j] = p.ss;	
			else break;
		}
		for (int j = p.ff;j >= 0;j--) {
			if (p.ss < smin[j]) smin[j] = p.ss;	
			else break;
		}
		for (int j = p.ff;j >= 0;j--) {
			if (p.ss > smax[j]) smax[j] = p.ss;	
			else break;
		}
		ll ans = 0;
		for (int j = 0;j < m;j++) {
			int ub = min(pmax[j], smax[j]), lb = max(pmin[j], smin[j]);
			if (ub%2 != j%2) ub--;
			if (lb%2 != j%2)lb++;
			ans += max(0, (ub-lb)/2+1);
		}
		cout << ans << "\n";
	}	
}

Subtask 4,5

Solution 1.

Chinese

官解是 Subtask 3 的延伸，我們希望快速的維護新增一個點之後，前綴最大/最小值以及後綴最大/最小值。具體來說，我們希望算出

$$\sum _{i}max(0,\lceil (min(pma{x}_i,sma{x}_i)-max(pmi{n}_i,smi{n}_i)+1)/2\rceil )$$

這件事情可以用線段樹上二分搜 + 區間修改做到。
一個要注意的細節是，在計算答案的時候不能把區間長度為

$0$ 的部份算進答案。因此需要想辦法知道每一排什麼時候答案變為正的。第一個方法是用整體二分搜，複雜度會變成

$O(N\log N\log C)$ 之類的，可能會過不了 TL。另一個方法是觀察一排什麼時候答案會是非負的，這件事情等價於「出現一個左上-右下的點對經過該排以及左下-右上的點對經過該排，或是一個水平的點對穿過該排至少一個點」。這件事情可以透過線段樹加上維護一些 set 做到，均攤會是

$O(N(\log N+\log C))$。

最後考慮怎麼處理

$pmax$ 跟

$smax$ 取 min 的問題，可以發現存在一個點

$c$ 使得

$pma{x}_i\le sma{x}_i,\mathrm{\forall }i\le c$，且

$sma{x}_i\le pma{x}_i,\mathrm{\forall }i>c$，且這個

$c$ 點恰好是最高點的

$x$ 位置。因此我們可以很簡單的維護這個位置並且在線段樹上用一個區間和做到。

English

The official solution optimizes the brute force update mentioned previously. We'd like to maintain the prefix/suffix max/min, and calculate

$$\sum _{i}max(0,\lceil (min(pma{x}_i,sma{x}_i)-max(pmi{n}_i,smi{n}_i)+1)/2\rceil )$$

This can be done using binary search on segment tree and lazy propagation.

The first detail is when the length of the intersection is

$0$ we should ignore the interval, so we need to know when to stop ignoring each column. One idea is to use total binary search, the time complexity is around

$O(N\log N\log C)$, might not be fast enough; instead, we could make use of another observation: we should count a column iff either "there's a TopLeft-BottomRight pair AND a BottomLeft-TopRight pair crossing this column" or "there's a horizotal segment crossing this column". This can be implemented with segment tree plus some std::set's, in the end it should be

$O(N(\log N+\log C))$ amortized.

The second detail is how to maintain the min of prefix-max and suffix-max, notice that there's a point c such that

$pma{x}_i\le sma{x}_i,\mathrm{\forall }i\le c$, and

$sma{x}_i\le pma{x}_i,\mathrm{\forall }i>c$, in fact, it's exactly the

$x$ position of the maximum value. we can easily maintain the position and use segment tree with lazy propagation again.

AC code

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 400005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
#define iter(v) v.begin(),v.end()
#define SZ(v) (int)v.size()
#define pb emplace_back
const int inf = 2*maxn;
struct segtree{ // make sure all coordinates are positive
	int cnt[4*maxn];
	pii pmax[4*maxn], pmin[4*maxn], smax[4*maxn], smin[4*maxn];	
	//first: sum, second: change tag
	void init(int cur, int l, int r) {
		if (r <= l) return;
		cnt[cur] = 0;
		pmax[cur] = pmin[cur] = smax[cur] = smin[cur] = {0, 0};
		if (r - l <= 1) return;
		int m = (l + r) / 2;
		init(cur*2, l, m);
		init(cur*2+1, m, r);
	}
	void push(pii seg[], int cur, int l, int r) {
		if (seg[cur].ss) {
			seg[cur].ff = (ll)cnt[cur] * seg[cur].ss;
			if (r - l > 1) {
				seg[cur*2].ss = seg[cur].ss;
				seg[cur*2+1].ss = seg[cur].ss;
				seg[cur].ss = 0;
			}
		}
	}
	void pull(pii seg[], int cur, int l, int r) {
		int m = (l + r) / 2;	
		push(seg, cur*2, l, m), push(seg, cur*2+1, m, r);
		seg[cur].ff = seg[cur*2].ff + seg[cur*2+1].ff;
	}
	void addpos(int cur, int l, int r, int ind) {
		if (r <= l) return;
		push(pmax, cur, l, r);push(pmin, cur, l, r);
		push(smax, cur, l, r);push(smin, cur, l, r);
		if (r - l == 1) {
			cnt[cur] = 1;
			push(pmax, cur, l, r);push(pmin, cur, l, r);
			push(smax, cur, l, r);push(smin, cur, l, r);
			return;
		}
		int m = (l + r) / 2;
		if (ind < m) addpos(cur*2, l, m, ind);
		else addpos(cur*2+1, m, r, ind);
		pull(pmax, cur, l, r);pull(pmin, cur, l, r);
		pull(smax, cur, l, r);pull(smin, cur, l, r);
		cnt[cur] = cnt[cur*2] + cnt[cur*2+1];
	}
	void modify(pii seg[], int cur, int l, int r, int ql, int qr, int val) {
		if (r <= l || ql >= r || qr <= l) return;
		push(seg, cur, l, r);
		if (ql <= l && qr >= r) {
			seg[cur].ss = val;
			return;
		}
		int m = (l + r) / 2;
		modify(seg, cur*2, l, m, ql, qr, val);
		modify(seg, cur*2+1, m, r, ql, qr, val);
		pull(seg, cur, l, r);
	}
	ll getsum(pii seg[], int cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return 0LL;
		push(seg, cur, l, r);	
		if (ql <= l && qr >= r) return seg[cur].ff;
		int m = (l + r) / 2;
		return getsum(seg, cur*2, l, m, ql, qr) + getsum(seg, cur*2+1, m, r, ql, qr);
	}
};

struct DS{ //another segment tree with some other operations
	segtree odd, even;
	set<int> ru, rd, so, se;
	int state[maxn];
	int ma[4*maxn], mi[4*maxn];	
	pii ran[2*maxn];
	int C = 0, rows = 0;
	void init(int cur, int l, int r, int _C) {
		if (cur == 1) {
			C = _C;
			for (int i = l;i < r;i++) {
				ru.insert(i), rd.insert(i);
				state[i] = 0;
				if (i % 2) so.insert(i);
				else se.insert(i);
			}
			for (int i = 0;i < 2*C;i++) ran[i] = {inf, -inf};
			odd.init(1, 0, C);
			even.init(1, 0, C);
		}
		if (r <= l) return;
		ma[cur] = -inf;
		mi[cur] = inf;
		if (r - l == 1) return;
		int m = (l + r) / 2;
		init(cur*2, l, m, C), init(cur*2+1, m, r, C);
	}
	void modify(int cur, int l, int r, int ind, int val) {
		if (r <= l) return;
		if (r - l == 1) {
			ma[cur] = max(ma[cur], val);
			mi[cur] = min(mi[cur], val);
			return;
		}	
		int m = (l + r) / 2;
		if (ind < m) modify(cur*2, l, m, ind, val);
		else modify(cur*2+1, m, r, ind, val);
		ma[cur] = max(ma[cur*2], ma[cur*2+1]);
		mi[cur] = min(mi[cur*2], mi[cur*2+1]);
	}	
	int search(int cur, int l, int r, int ql, int qr, int type, int val, int dir) {
		//dir: 0 for leftmost, 1 for rightmost
		//type: 0 for mi, 1 for ma
		if (r <= l || ql >= r || qr <= l) return dir ? l-1 : r;
		if ((!type && mi[cur] > val) || (type && ma[cur] < val)) return dir ? l-1 : r;
		if (r - l == 1) {
			if (type == 0) {
				if (mi[cur] <= val) return l;
				else return dir ? l-1 : r;
			} else {
				if (ma[cur] >= val) return l;
				else return dir ? l-1 : r;
			}
		}	
		int m = (l + r) / 2;
		if (dir==0) {
			int vl = search(cur*2, l, m, ql, qr, type, val, dir);
			if (vl == m) return search(cur*2+1, m, r, ql, qr, type, val, dir);
			else return vl;
		} else {
			int vr = search(cur*2+1, m, r, ql, qr, type, val, dir);
			if (vr == m-1) return search(cur*2, l, m, ql, qr, type, val, dir);
			else return vr;
		}
	}
	int query(int cur, int l, int r, int ql, int qr, int type) {
		if (r <= l || ql >= r || qr <= l) return type ? -inf : inf;
		if (ql <= l && qr >= r) return type ? ma[cur] : mi[cur];
		int m = (l + r) / 2;
		int vl = query(cur*2, l, m, ql, qr, type);
		int vr = query(cur*2+1, m, r, ql, qr, type);
		return type ? max(vl, vr) : min(vl, vr);
	}

	void addpos(int x, int type) {
		bool ch = 0;
		if (type == 0 && !(state[x] & 1)) {
			state[x] |= 1;	
			ru.erase(ru.find(x));
			ch = 1;
		}
		if (type == 1 && !(state[x] & 2)) {
			state[x] |= 2;
			rd.erase(rd.find(x));
			ch = 1;
		}
		if (ch && state[x] == 3) {
			//debug("addpos", x);
			rows++;
			if (x%2) odd.addpos(1, 0, C, x);
			else even.addpos(1, 0, C, x);
		}
	}
	void hline(pii p) {
		ran[p.ss] = {min(p.ff, ran[p.ss].ff), max(p.ff, ran[p.ss].ss)};
		if (p.ff % 2) {
			auto it = so.lower_bound(ran[p.ss].ff);
			while (it != so.end() && (*it) <= ran[p.ss].ss) {
				addpos(*it, 0);
				addpos(*it, 1);
				so.erase(so.find(*it));
				it = so.lower_bound(ran[p.ss].ff);
			}
		} else {
			auto it = se.lower_bound(ran[p.ss].ff);
			while (it != se.end() && (*it) <= ran[p.ss].ss) {
				addpos(*it, 0);
				addpos(*it, 1);
				se.erase(se.find(*it));
				it = se.lower_bound(ran[p.ss].ff);
			}
		}
	}
	pii low = {inf, inf}, up = {-inf, -inf};
	ll ins(pii p) {
		
		//update range vals
		int lmax = query(1, 0, C, 0, p.ff, 1), lmin = query(1, 0, C, 0, p.ff, 0);
		int rmax = query(1, 0, C, p.ff+1, C, 1), rmin = query(1, 0, C, p.ff+1, C, 0);
		//debug("lmax", lmax, "lmin", lmin, "rmax", rmax, "rmin", rmin);
		bool par = p.ff % 2;
		if (p.ss > lmax) {
			int r = search(1, 0, C, p.ff, C, 1, p.ss, 0);
			//debug("lmax", p.ff, r);
			odd.modify(odd.pmax, 1, 0, C, p.ff, r, p.ss - (par%2?0:1));
			even.modify(even.pmax, 1, 0, C, p.ff, r, p.ss - (par%2?1:0));
		}	
		if (p.ss < lmin) {
			int r = search(1, 0, C, p.ff, C, 0, p.ss, 0);
			//debug("lmin", p.ff, r);
			odd.modify(odd.pmin, 1, 0, C, p.ff, r, p.ss + (par?0:1));
			even.modify(even.pmin, 1, 0, C, p.ff, r, p.ss + (par?1:0));
		}
		if (p.ss > rmax) {
			int l = search(1, 0, C, 0, p.ff+1, 1, p.ss, 1);
			//debug("rmax", l+1, p.ff+1);
			odd.modify(odd.smax, 1, 0, C, l+1, p.ff+1, p.ss - (par?0:1));
			even.modify(even.smax, 1, 0, C, l+1, p.ff+1, p.ss - (par?1:0));
		}	
		if (p.ss < rmin) {
			int l = search(1, 0, C, 0, p.ff+1, 0, p.ss, 1);
			//debug("rmin", l+1, p.ff+1);
			odd.modify(odd.smin, 1, 0, C, l+1, p.ff+1, p.ss + (par?0:1));
			even.modify(even.smin, 1, 0, C, l+1, p.ff+1, p.ss + (par?1:0));
		}
		modify(1, 0, C, p.ff, p.ss);


		{ //addpos
			int lef = min((int)p.ff, search(1, 0, C, 0, p.ff, 0, p.ss, 0));
			int rig = max((int)p.ff, search(1, 0, C, p.ff+1, C, 1, p.ss, 1));
			//debug("ru", lef, rig);
			auto it = ru.lower_bound(lef);
			while (it != ru.end() && *it <= rig) {
				addpos(*it, 0);
				it = ru.lower_bound(lef);
			}
			lef = min((int)p.ff, search(1, 0, C, 0, p.ff, 1, p.ss, 0));
			rig = max((int)p.ff, search(1, 0, C, p.ff+1, C, 0, p.ss, 1));
			it = rd.lower_bound(lef);
			//debug("rd", lef, rig);
			while (it != rd.end() && *it <= rig) {
				addpos(*it, 1);
				it = rd.lower_bound(lef);
			}
			hline(p);
		}

		//answer calculation
		if (p.ss < low.ss) low = p;
		if (p.ss > up.ss) up = p;
		ll sum = 0;
		sum += odd.getsum(odd.pmax, 1, 0, C, 0, up.ff) + even.getsum(even.pmax, 1, 0, C, 0, up.ff) +
			odd.getsum(odd.smax, 1, 0, C, up.ff, C) + even.getsum(even.smax, 1, 0, C, up.ff, C);
		//debug("tmp sum", sum);
		sum -= odd.getsum(odd.pmin, 1, 0, C, 0, low.ff) + even.getsum(even.pmin, 1, 0, C, 0, low.ff) +
			odd.getsum(odd.smin, 1, 0, C, low.ff, C) + even.getsum(even.smin, 1, 0, C, low.ff, C);
		//debug("sum", sum, "rows", rows);
		return sum/2 + rows;
	}
} ds;
int main() {
	io;
	int n, C;
	cin >> n >> C;
	C++;
	ds.init(1, 0, 2*C, 2*C);
	for (int i = 0;i < n;i++) {
		int tx, ty;
		cin >> tx >> ty;
		pii p = {tx - ty + (C-1), tx + ty + (C-1)};	
		//debug("p", p.ff, p.ss);
		cout << ds.ins(p) << "\n";
	}	
}
/*
4 30
29 0
11 10
21 1
19 23
*/

Solution 2

Chinese

另外一種解是 Subtask 2 作法的延伸，可以發現每一種點只有 16 種可能的狀態，因此可以用類似的方式開 16 棵線段樹維護，這樣的話複雜度仍然是

$O(N(\log N+\log C))$ ，但是要注意常數的問題。

English

The other solution is an extension of the solution in Subtask 2, we notice that for every point there are only 16 possible states, so we can use a similar method and utilize 16 segment trees to maintain our solution, this also has a time complexity of

$O(N(\log N+\log C))$. It will be fast enough if the implementation is efficient.

AC Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pii pair <int, int>
#define mp make_pair
#define all(x) x.begin(), x.end()
const int mod = 998244353, N = 200005;

const int NO = -123456789;

struct Seg {
    struct node {
        int mnl, mxl, mnr, mxr, lzl, lzr, alive;
        ll totr, totl;
    } tree[N << 2];
    void build(int l, int r, int id, vector <pii> &range) {
        tree[id].lzl = tree[id].lzr = NO;
        if (r - l == 1) {
            tree[id].mnr = tree[id].mxr = range[l].second;
            tree[id].mnl = tree[id].mxl = range[l].first;
            tree[id].totl = range[l].first, tree[id].totr = range[l].second, tree[id].alive = 1;
        } else {
            build(l, l + r >> 1, id << 1, range);
            build(l + r >> 1, r, id << 1 | 1, range);
            pull(id);
        }
    }
    void pull(int id) {
        tree[id].mnl = min(tree[id << 1].mnl, tree[id << 1 | 1].mnl);
        tree[id].mxl = max(tree[id << 1].mxl, tree[id << 1 | 1].mxl);
        tree[id].mnr = min(tree[id << 1].mnr, tree[id << 1 | 1].mnr);
        tree[id].mxr = max(tree[id << 1].mxr, tree[id << 1 | 1].mxr);
        tree[id].totl = tree[id << 1].totl + tree[id << 1 | 1].totl;
        tree[id].totr = tree[id << 1].totr + tree[id << 1 | 1].totr;
        tree[id].alive = tree[id << 1].alive + tree[id << 1 | 1].alive;
    }
    void give_l(int id, int x) {
        // change l to x (l <= x <= r)
        tree[id].mnl = tree[id].mxl = x;
        tree[id].totl = 1ll * x * tree[id].alive;
        tree[id].lzl = x;
    }
    void give_r(int id, int x) {
        // change r to x (l <= x <= r)
        tree[id].mnr = tree[id].mxr = x;
        tree[id].totr = 1ll * x * tree[id].alive;
        tree[id].lzr = x;
    }
    void push(int id) {
        if (tree[id].lzl != NO)
            give_l(id << 1, tree[id].lzl), give_l(id << 1 | 1, tree[id].lzl), tree[id].lzl = NO;
        if (tree[id].lzr != NO)
            give_r(id << 1, tree[id].lzr), give_r(id << 1 | 1, tree[id].lzr), tree[id].lzr = NO;
    }
    void delete_node(int id) {
        tree[id].alive = tree[id].totl = tree[id].totr = 0;
        tree[id].mnl = tree[id].mnr = 1 << 30, tree[id].mxl = tree[id].mxr = -1 << 30;
    }
    void remove_l(int x, int l, int r, int id) {
        if (x <= tree[id].mnr) return;
        if (r - l == 1) {
            delete_node(id);
        } else {
            push(id);
            if (x > tree[id << 1].mnr) remove_l(x, l, l + r >> 1, id << 1);
            if (x > tree[id << 1 | 1].mnr) remove_l(x, l + r >> 1, r, id << 1 | 1);
            pull(id);
        }
    }
    void modify_l(int a, int b, int x, int l, int r, int id) {
        if (a >= b) return;
        if (!tree[id].alive || tree[id].mnl >= x) return;
        if (a <= l && r <= b) {
            remove_l(x, l, r, id);
            if (tree[id].mxl <= x) {
                give_l(id, x);
            } else {
                push(id);
                modify_l(a, b, x, l, l + r >> 1, id << 1);
                modify_l(a, b, x, l + r >> 1, r, id << 1 | 1);
                pull(id);
            }
        } else {
            push(id);
            if (a < (l + r >> 1)) modify_l(a, b, x, l, l + r >> 1, id << 1);
            if ((l + r >> 1) < b) modify_l(a, b, x, l + r >> 1, r, id << 1 | 1);
            pull(id);
        }
    }
    void remove_r(int x, int l, int r, int id) {
        if (tree[id].mxl <= x) return;
        if (r - l == 1) {
            delete_node(id);
        } else {
            push(id);
            if (tree[id << 1].mxl > x) remove_r(x, l, l + r >> 1, id << 1);
            if (tree[id << 1 | 1].mxl > x) remove_r(x, l + r >> 1, r, id << 1 | 1);
            pull(id);
        }
    }
    void modify_r(int a, int b, int x, int l, int r, int id) {
        if (a >= b) return;
        if (!tree[id].alive || x >= tree[id].mxr) return;
        if (a <= l && r <= b) {
            remove_r(x, l, r, id);
            if (x <= tree[id].mnr) {
                give_r(id, x);
            } else {
                push(id);
                modify_r(a, b, x, l, l + r >> 1, id << 1);
                modify_r(a, b, x, l + r >> 1, r, id << 1 | 1);
                pull(id);
            }
        } else {
            push(id);
            if (a < (l + r >> 1)) modify_r(a, b, x, l, l + r >> 1, id << 1);
            if ((l + r >> 1) < b) modify_r(a, b, x, l + r >> 1, r, id << 1 | 1);
            pull(id);
        }
    }
    ll calc() {
        return tree[1].totr - tree[1].totl + tree[1].alive;
    }
};

struct Board {
    Seg root1, root2;
    int C;
    void init(int _C) {
        C = _C;
        vector <pii> range1(C + 1), range2(C);
        for (int i = 0; i <= C * 2; ++i) {
            int x = min(i, C * 2 - i);
            (i & 1 ? range2 : range1)[i / 2] = mp(-(x + (i & 1)) / 2, x / 2);
        }
        root1.build(0, C + 1, 1, range1);
        root2.build(0, C, 1, range2);
    }
    void modify_l(int a, int b, int x) {
        if (x & 1) {
            root1.modify_l((a + 1) / 2, (b + 1) / 2, x / 2 + (x > 0 ? 1 : 0), 0, C + 1, 1);
            root2.modify_l(a / 2, b / 2, (x - 1) / 2, 0, C, 1);
        } else {
            root1.modify_l((a + 1) / 2, (b + 1) / 2, x / 2, 0, C + 1, 1);
            root2.modify_l(a / 2, b / 2, x / 2, 0, C, 1);
        }
    }
    void modify_r(int a, int b, int x) {
        if (x & 1) {
            root1.modify_r((a + 1) / 2, (b + 1) / 2, x / 2 + (x > 0 ? 0 : -1), 0, C + 1, 1);
            root2.modify_r(a / 2, b / 2, (x - 1) / 2, 0, C, 1);
        } else {
            root1.modify_r((a + 1) / 2, (b + 1) / 2, x / 2, 0, C + 1, 1);
            root2.modify_r(a / 2, b / 2, x / 2 - 1, 0, C, 1);
        }
    }
    ll calc() {
        return root1.calc() + root2.calc();
    }
} state[16];

void solve() {
    int n, C;
    cin >> n >> C;
    for (int s = 1; s < 15; ++s)
        state[s].init(C);
    while (n--) {
        int x, y;
        cin >> x >> y;
        tie(x, y) = mp(x + y, x - y);
        for (int s = 1; s < 15; ++s) {
            for (int i = 0; i < 4; ++i) if (s >> i & 1) {
                int a, b;
                if (i & 1) tie(a, b) = mp(0, x + 1);
                else tie(a, b) = mp(x, C * 2 + 1);
                if (i & 2) {
                    state[s].modify_l(a, b, y + 1);
                } else {
                    state[s].modify_r(a, b, y - 1);
                }
            }
        }
        ll ans = 1ll * (C + 1) * (C + 1);
        for (int s = 1; s < 15; ++s) {
            ans += state[s].calc() * (__builtin_popcount(s) & 1 ? -1 : 1);
        }
        cout << ans << '\n';
    }
}

int main () {
    ios::sync_with_stdio(false), cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}