2017 ACM-ICPC Asia Taiwan Online Programming Contest – 裁判長講評

tags: ACM-ICPC TOPC 2017 TOPC2017

本次賽題命題團隊為東華大學羅壽之教授、李官陵教授，清華大學李哲榮教授，元智大學張經略教授，台灣大學退役選手陳庭緯先生、王瀚中先生，清華大學退役選手李彥余先生，交通大學退役選手林韵凱先生、于尚鑫女士與裁判長所組成。由裁判長諮詢團隊後，自十道題目中選出八道進行修改調整後做為正式賽題，並委由命題團隊中的退役選手與台灣大學退役選手黃上恩先生與交通大學退役選手廖俊杰先生驗題。裁判長謹代表 2017 ACM-ICPC Asia Taiwan Online Programming Contest 感謝所有參與題組準備工作的教授與退役選手們辛勤的付出。

以下是本次的賽題講評。

題組難度總評

• Problem A 是題組中最容易實作，但需要搭配數學式定義解讀能力。有良好的實作能力應該可以在10分鐘內完成。預計 100 分鐘內大多數人可以解決。
• Problem B 是題組中較易實作且不容易搞錯題意的。搭配恰當的工具與謹慎實作應能在15分鐘內完成。預計 150 分鐘內大多數人可以解決。
• Problem C 預設難度中偏易，可能需要自己做演算法設計，並搭配一些小陷阱。不少隊伍對需要自行設計演算法的題目較不擅長。
• Problem D 預設難度中偏易，需要對於資料結構與實際效率有一定掌握。本次競賽搭配 IOI isolate Sandbox 準確量測執行時間，因此時限並不算太寬裕。
• Problem E 預設難度中，需要能應用二分法，並具備幾何知識與微分反三角函數的知識。提供範例測試資料時故意隱藏一種特例，可能因此答題狀況比預期要差。
• Problem F 預設難度中偏難，數學觀察 Divide and conquer 題。需要觀察到題目所求函數與組合數的相似關係才好作答。不少隊伍直接以遞迴式帶入，或基於此進行動態規劃，欠缺複雜度分析作法可行性，因此都無法得到好結果。
• Problem G 預設難度難偏中，高級資料結構設計題。題意很好理解，可是直接照做會 TLE ：這是在實作之前就可以分析出來的。正確的方法實作上有一定困難程度，因此多數 Submission 除了 WA 之外，還有許多 TLE 與 RE 。
• Problem H 預設難度難，圖論、動態規劃與高級資料結構應用題。
• 本次賽題有保證 Python 3 可以解出一半以上的問題。 A, B, E, F 均可以 Python 3 解出，甚至 C 也還有機會。

來自裁判長的建議

• 給做出一兩題沒有時間完成後續題組的隊伍：請鍛鍊基礎，熟悉可以使用的解題語言工具，如 C++ STL 中常用的 Container 如 vector, set, map, queue, priority_queue 等等，以及常用的演算法 sort, lower_bound, next_permutation 等等。
• 給做出兩題但是第三題卡住做不出來的隊伍：請開始多下工夫在演算法設計上，熟悉建議多從基礎設計方法如：Incremental Method、Enumeration、Divide and Conquer、Greedy Method、Dynamic Programming 等開始。
• 使用 C++ cin、cout 以及 Java Scanner、System.out 的同學，如果在比賽中處理數以萬計的大規模輸入跟輸出，請務必留意是否有作適當的最佳化。一般的建議是在競賽時 C++ 開發者使用 scanf 、 printf 以及 Java 開發者使用 BufferedReader 配合 StringTokenizer 、 StringBuffer 暫存輸出最後再一口氣用 System.out。
• 給會用 Greedy method 做 Problem C 卻 TLE 的隊伍：請確認一下自己會不會用主戰語言的內建排序功能喔。
• 給 Problem D 拿 TLE 的隊伍：請留意各種內建資料結構的效能喔。Big-O notation 描述的是
  $n$ 很大的時候，成長的趨勢，而不是在指定輸入大小的時候喔。
• 給 Problem E 一直拿 WA 的隊伍：這種時候，可能要想想是不是漏了什麼特例沒討論到。
• 給 Problem F 、 Problem G 沒做分析卻拿了滿手 TLE 的隊伍：ACM-ICPC 類競賽，複雜度是影響執行時間的主要關鍵，請記得作分析再上傳，電腦的速度可是有限的，命題者可是都有想過該給哪種解法 TLE 的。

Problam A – Similarity Computation

題意是給定兩個集合

$A$ 跟

$B$ ，求兩個集合的 Jaccard similarity coefficient。

這一題是本次題組中最簡單的題目之一，只要能夠讀懂題目上的數學式，便能很快地進行程式的撰寫。這題有一個小陷阱是 Jaccard similarity 剛好是

$0.5$ 時，如果粗心可能會錯判。如果參賽者熟悉一些語言提供的集合資料結構，那麼寫起來會更快，如下列 Python 3 程式碼：

T = int(input())
# 重複 T 次
for i in range(T):
    # 讀入 A, B 大小，但不用。
    input() 
    # 讀入 A, B 元素後，造出對應的集合
    A, B = set(input().split()), set(input().split())
    # 如果交集元素數的兩倍比聯集元素還多就輸出 1 否則輸出 0
    print(1 if len(A&B)*2 > len(A|B) else 0)

Problem B – The Combination of Poker Cards

題意是給定六張撲克牌的數字，求那六張牌的牌型。

這是在本次題組中技術難度比較低的題目，但有許多隊伍打錯字，或是實做方法選擇上，耗用了比較多實作時間。一個建議的實作方法是使用 C++ STL 的 map 、 Java STL 的 HashMap 、 Python 的 dict 來進行實作，如此一來可以很快的得知有多少種數字，以及每種數字出現的次數。Python 3的範例程式如下：

T = int(input())
for i in range(T):
    hand = {}
    for c in input().split():
        hand.setdefault(c,0)
        hand[c] += 1
    if len(hand) == 6: print('single')
    elif len(hand) == 5: print('one pair')
    elif len(hand) == 4:
        if any(v==3 for v in hand.values()): print('one triple')
        else: print('two pairs')
    elif len(hand) == 3:
        if any(v==4 for v in hand.values()): print('tiki')
        elif any(v==3 for v in hand.values()): print('full house')
        else: print('three pairs')
    elif len(hand) == 2:
        if any(v==3 for v in hand.values()): print('two triples')
        else: print('tiki pair')

Problem C – Coloring Intevals

題意是給定

$n$ 個區間，求將所有區間塗上顏色，使得任兩個有交集的區間顏色都相異的最小顏色數。

首先我們分析一下這題答案的下限：如果有一個點，落在

$k$ 個相異區間內，那麼答案至少要是

$k$。落在的最多區間的那個點，所對應的

$k$ 值(以下稱

$k^{\ast }$)，就是答案的下限。

接下來，我們如果能夠設計出一個演算法，用

$k^{\ast }$ 種顏色塗滿所有區間，那麼，我們就能證明

$k^{\ast }$ 就是該組輸入的答案。這裡採用一個 Greedy method 來設計演算法。我們維護兩個集合

$U$ (已使用)跟

$A$ (可使用)，初始均為空集合，另維護一個計數器

$c$，初始為

$0$，並從左到右開始塗區間的顏色。

觀察一下塗色情形需要處理的只有區間的左右兩端點。由左向右處理這些點，如有一區間左右端點相同，則先處理左端點。如果處理到左端點，

$A$ 不是空集合，就將

$A$ 中編號最大的塗給該區間，並將該顏色加入

$U$。

$A$ 為空集合，則將

$c$ 加一，將

$c$ 這個顏色塗上該區間，並將

$c$ 加入

$U$。如果處理到右端點，則代表該區間已經結束，自此之後可以使用該顏色，將該區間所塗的顏色加入

$A$。有興趣的同學，可以證明看看這樣做可以保證

$c$ 值(也就是使用到的顏色數量)永遠不會超過

$k^{\ast }$ (最佳解的下限)，換言之這樣就是最佳解。

綜上可知如果我們有所有左右端點排序好的資料，便能在

$O(n)$ 的時間內完成本題所需的計算。只要各位有排序工具，便能在

$O(n\log n)$ 的時間內完成排序，這是本題真正的時間瓶頸。最後需要留意的，是端點的範圍，用 int 是無法好好儲存的，請各位使用適當的資料型態。

Problem D – Mixing Coins

題意是給定需多排成一排的硬幣，依據一個給定的演算法，將三個硬幣融合升級為一個硬幣，直到無法進行時，還剩下多少個硬幣。

這個題目看似簡單，不過執行的時限卡的相當緊。如果使用一個陣列搭配 Run-length Encoding 來維護這些硬幣，那麼每次融合硬幣之後，都需要將後方的硬幣向前推移，並把新融合出的硬幣接在最後方，如此一來，每次操作所需要的時間將會是

$O(n)$ ，並且至少前

$\frac{n}{2}$ 的操作，至少需要

$\mathrm{\Omega }(n)$ 的時間，在本題的輸入規模下，這肯定要 TLE 。因此，必須選擇適當的資料結構來實作。第一種比較直覺的做法是採用每個操作只需要

$O(1)$ 的 Linked list。不過 Linked list 牽涉到位址可能不連續的記憶體存取，以及需要花時間 dereferencing ，效率並不是太好。在現代的計算機結構下，通常我會推薦 C++ 開發者使用 queue 跟 vector 分別實作一個儲存可能還會發生新的融合的硬幣 (用 Queue 存) ，跟已經確定不會在前面這段找到新的融合可能的硬幣 (用 Stack 存)，以連續的記憶體儲存資料，發揮快取記憶體的效能。至於 Java 開發者，我則建議各位可以使用 ArrayDeque 。

Problem E – Fences

題意是有一個大圓(外層圍籬)包覆一個邊不自交多邊形(內層圍籬)。給定大圓周長以及多邊形的各邊長度這兩個形狀滿足一些性質，要求介於兩者之間的面積，即兩者面積差。

首先由題目敘述得知，多邊形的頂點與大圓的距離均相等，據此可以推斷出，所有頂點都在一個跟大圓共用圓心的小圓邊界上，因此多邊形是個圓內接多邊形。只要能夠算出小圓半徑，便可以用三角形分割算出多邊形面積，再回推答案是多少。

當我們討論一個圓內接多邊形的外接圓半徑時，有幾個情況要注意。外接圓的圓心可能會在多邊形內、多邊形上、多邊形外。將多邊形的邊當作外接圓的弦時，所對應的圓心角定為

${\theta }_1,\dots ,{\theta }_n$，不失一般性的我們假定

${\ell }_n$ 最長，而對應的

${\theta }_n$ 最大。如圓心在多邊形內，則等式

${\theta }_1+\cdots +{\theta }_n-2\pi =0$ 成立。如圓心在多邊形外，則等式

${\theta }_1+\cdots +{\theta }_{n-1}-{\theta }_n=0$ 成立。如圓心在多邊形邊上，則兩個等式均成立。

由於我們並不知道外接圓半徑為何，我們可以觀察當把這些邊當作弦放在一個半徑為

$r$ 的圓內，所對應到的圓心角分別為

${\tau }_1(r),\dots ,{\tau }_n(r)$，其中

${\tau }_i(r)=2{\sin }^{-1}\left(\frac{{\ell }_i}{2r}\right)$ 。我們能夠拿來用的圓半徑

$r$ ，最小只能是最長邊的一半，即

$\frac{{\ell }_n}{2}$。讓我們定義

$f_1(r)={\tau }_1(r)+\cdots +{\tau }_n(r)-2\pi$ 及

$f_2(r)={\tau }_1(r)+\cdots +{\tau }_{n-1}(r)-{\tau }_n(r)$ 兩個函數。請留意

$f_1(r)=0$ 與

$f_2(r)=0$ 分別對應到前段所述的兩個等式，且

$f_1\left(\frac{{\ell }_n}{2}\right)=f_2\left(\frac{{\ell }_n}{2}\right)$ 。

$f_1$ 顯然是個單調遞減的函數，因為隨著圓半徑變大，所有的角都會變小，如果

$f_1\left(\frac{{\ell }_n}{2}\right)=f_2\left(\frac{{\ell }_n}{2}\right)>0$，我們可以透過二分法對

$f_1$ 進行勘根，找到

$r$ 使得

$f_1(r)\approx 0$，如是外接圓心在多邊形內的情形，這即能找到答案。而

$f_1\left(\frac{{\ell }_n}{2}\right)=f_2\left(\frac{{\ell }_n}{2}\right)<0$ 時，因為

$f_2(r)$ 是一個的特別的函數(請見補充)，直接對

$f_2(r)$ 做二分法即可勘出根的近似值，即找到

$r$ 使得

$f_2(r)\approx 0$，進而求出答案。當

$f_1\left(\frac{{\ell }_n}{2}\right)=f_2\left(\frac{{\ell }_n}{2}\right)=0$ 時，就直接用

$r=\frac{{\ell }_n}{2}$ 找答案了。

補充

由於我們討論的

$r$ 至少是

$\frac{{\ell }_n}{2}>0$ ，因此在本題討論的範圍內，對任意正數

$p$ ，可保證

$r^p\cdot f_2(r)$ 跟

$f_2(r)$ 同號。如有一正數

$p$ 使得

$r^p\cdot f_2(r)$ 具有單調遞增特性，則

$f_2(r)$ 可以利用二分法勘根。由於

$f_2(r)$ 是由一些反正弦函數所線性組成，先考慮反正弦函數的 McLaurin series：

$${\sin }^{-1}(x)=c_0+c_{1}x+c_2{x}^2+c_3{x}^3+\cdots +c_j{x}^j+\cdots$$
其中當

$k\in \mathbb{N}\cup \{0\}$ 時，

$c_{2k}=0$ 、

$c_{2k+1}=\frac{1\cdot 3\cdot \cdot \cdot \cdot \cdot (2k-1)}{2\cdot 4\cdot \cdot \cdot \cdot \cdot (2k)}\cdot \frac{1}{2k+1}>0$ 。由 McLaurin series 在

$|x|\le 1$ 時才能成立，而我們討論的

$r\ge \frac{{\ell }_n}{2}$，可知在我們討論的範圍內：

$$\begin{array}{rcl}{r}^p\cdot f_2(r)& =& r^p\cdot (\left(\sum _{i=1}^{n-1}\sum _{j=0}^{\mathrm{\infty }}{c}_j{\left(\frac{{\ell }_i}{2r}\right)}^j\right)-\sum _{j=0}^{\mathrm{\infty }}{c}_j{\left(\frac{{\ell }_n}{2r}\right)}^j)\\ & =& \sum _{j=1}^{\mathrm{\infty }}\frac{c_j}{2^j}({\ell }_1^j+\cdots +{\ell }_{n-1}^j-{\ell }_n^j)r^{p-j}\end{array}$$

而

$r^p\cdot f_2(r)$ 對

$r$ 之導函數為：

$$\begin{array}{rcl}{(r^p\cdot f_2(r))}^{\prime }& =& \sum _{j=1}^{\mathrm{\infty }}\frac{c_j}{2^j}(p-j)({\ell }_1^j+\cdots +{\ell }_{n-1}^j-{\ell }_n^j)r^{p-j-1}\end{array}$$

只要存在一個

$p$ ，使得對所有正整數

$j>0$，

$(p-j)({\ell }_1^j+\cdots +{\ell }_{n-1}^j-{\ell }_n^j)\ge 0$ 均成立，加上上式中有一項非零即可證明

$r^p\cdot f_2(r)$ 單調遞增。將

${\ell }_1^j+\cdots +{\ell }_{n-1}^j-{\ell }_n^j$ 視作一個自變數為

$j$ 的函數

$g(j)$。此時

${\ell }_n$ 是外接圓心在外之圓內接多邊形的最長邊長，不可能有其他邊一樣長，由指數增長特性，最終

${\ell }_n^j$ 的成長速度，會超過

${\ell }_1^j+\cdots +{\ell }_{n-1}^j$ 的總和。假定

$g(j^{\ast })=0$ 且

$j^{\ast }$ 為

$g$ 最小的根，此時

${\ell }_1^{j^{\ast }}+\cdots +{\ell }_{n-1}^{j^{\ast }}={\ell }_{n-1}^{j^{\ast }}$，然而

$j=j^{\ast }+\delta$ 且

$\delta >0$ 時，左手邊最多成長

${\ell }_{n-1}^{\delta }$ 倍，而右手邊成長

${\ell }_n^{\delta }$，這代表

$g(j^{\ast }+\delta )<g(j^{\ast })=0$，不會再回頭了。讓我們取

$p=j^{\ast }$，即可保證對所有正整數

$j>0$，

$(p-j)g(j)=(p-j)({\ell }_1^j+\cdots +{\ell }_{n-1}^j-{\ell }_n^j)\ge 0$ 均成立。再觀察由於多邊形的邊受三角不等式限制

${\ell }_1+{\ell }_2+\cdots +{\ell }_{n-1}>{\ell }_n$，這保證了

$g(1)>0$ ，因此

$p=j^{\ast }>1$ ，證得

$\frac{c_1}{2}(p-1)({\ell }_1+{\ell }_2+\cdots +{\ell }_{n-1}-{\ell }_n)r^{p-2}>0$，保證

$r^p\cdot f_2(r)$ 在

$r\ge \frac{{\ell }_n}{2}$ 時單調遞增。

綜合上述結論與「

$r^p\cdot f_2(r)$ 跟

$f_2(r)$ 同號」，我們可知

$f_2(r)$ 可以透過勘根定理，找出唯一根。要證明一性質成立比寫出會AC的程式碼困難許多，只要相信這題的根唯一，就可以進行二分法勘根。

Problem F – A Simple Function

題意是給定一個函數的遞迴定義，請計算特定的函數值。以下是命題者給的提示。

假設

$p$ 代表一質數，則可藉由題敘可得到當

$0\le x\le i$ 時，

$f(i,x,p)\equiv (\genfrac{}{}{0ex}{}{i}{x})(\text{mod }p)$。

證明步驟：

1. 證明
   $f(p,0,p)=f(p,p,p)=1$，且當
   $0<x<p$ 時，
   $f(p,x,p)=0$。
2. 證明當
   $0\le i<p$ 且
   $0\le x\le i$ 時，
   $f(i,x,p)=(\genfrac{}{}{0ex}{}{i}{x})$。
3. 證明
   $f(p^n,0,p)=f(p^n,p^n,p)=1$，且當
   $0<x<p^n$ 時，
   $f(p^n,x,p)=0$。
4. 證明當
   $n>k$ 且
   $a$ 和
   $b$ 不為
   $p$ 的倍數時，
   $f(a{p}^n,b{p}^k,p)=0$。
5. 證明當
   $a$ 和
   $b$ 不為
   $p$ 的倍數時
   $f(a{p}^n,b{p}^n,p)=f((a-1)p^n,(b-1)p^n,p)+f((a-1)p^n,b{p}^n,p)$。
6. 證明當
   $a$ 和
   $b$ 不為
   $p$ 的倍數時
   $f(a{p}^n,b{p}^n,p)=f(a{p}^{n-1},b{p}^{n-1},p)$。
7. 證明當
   $n\ge 1$ 且
   $a_1$ 和
   $b_1$ 不為
   $p$ 的倍數時，
   $f(a_{1}p+a_0,b_{1}p+b_0,p)=f(a_1,b_1,p)\times f(a_0,b_0,p)$。
8. 假設
   $a$ 和
   $b$ 分別寫成
   $p$ 進制時分別為
   $a_{n-1}{a}_{n-2}\cdots a_0$ 和
   $b_{n-1}{b}_{n-2}\cdots b_0$，則
   $f(a,b,p)=f(a_{n-1},b_{n-1},p)\times f(a_{n-2},b_{n-2},p)\times \cdots \times f(a_0,b_0,p)$。

Problem G – The Jet-Black Wings

題意是給定至多十萬個數字，以及總數至多十萬個的查詢(目前前K大的數字)與修改指令(將全部的數字對 X 做 XOR 後排序)，請輸出所有查詢的結果。

命題者表示：「我覺得我那題看標程比較好懂就是…」

//bcw0x1bd2 {{{
#include<bits/stdc++.h>
#include<unistd.h>
using namespace std;
#define FZ(x) memset((x),0,sizeof(x))
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define SZ(x) ((int)((x).size()))
#define ALL(x) begin(x),end(x)
#define REP(i,x) for (int i=0; i<(x); i++)
#define REP1(i,a,b) for (int i=(a); i<=(b); i++)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

#ifdef DARKHH
#define FILEIO(name)
#else
#define FILEIO(name) \
  freopen(name".in", "r", stdin); \
  freopen(name".out", "w", stdout);
#endif

#ifdef DARKHH
template<typename T>
void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; }

template<typename T, typename... Args>
void _dump( const char* s, T&& head, Args&&... tail ) {
  int c=0;
  while ( *s!=',' || c!=0 ) {
    if ( *s=='(' || *s=='[' || *s=='{' ) c++;
    if ( *s==')' || *s==']' || *s=='}' ) c--;
    cerr<<*s++;
  }
  cerr<<"="<<head<<", ";
  _dump(s+1,tail...);
}

#define dump(...) do { \
  fprintf(stderr, "%s:%d - ", __PRETTY_FUNCTION__, __LINE__); \
  _dump(#__VA_ARGS__, __VA_ARGS__); \
} while (0)

template<typename Iter>
ostream& _out( ostream &s, Iter b, Iter e ) {
  s<<"[";
  for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
  s<<"]";
  return s;
}

template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; }
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
template<typename T, size_t N>
ostream& operator <<( ostream &s, const array<T,N> &c ) { return _out(s,ALL(c)); }
template<typename T>
ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); }
template<typename A, typename B>
ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); }
#else
#define dump(...)
#endif
// }}}
// Let's Fight! ~OAO~~

const int MAXN = 100005;
const int MAX = 2147483647;
using BS = bitset<5>;

struct Trie {
  static const int S = 31;
  static const int MEM = S * MAXN + 5;
  struct Node {
    int tot,lv,ch[2],cnt[S];
    Node () {
      tot = lv = ch[0] = ch[1] = 0;
      memset(cnt, 0, sizeof(cnt));
    }
  };

  Node tree[MEM];
  int root, xmask, mem;

  void init() {
    xmask = 0;
    mem = 1;
    root = get_node();
    tree[root].lv = S-1;
  }
  void rox(int x) {
    xmask ^= x;
  }
  int get_node() {
    assert(mem < MEM);
    tree[mem] = Node();
    return mem++;
  }
  void add(int x) {
    x ^= xmask;
    //dump(BS(x));
    static vector<int> vec;
    vec.clear();
    int id = root;
    for (int i=S-1; i>=0; i--) {
      int b = (x >> i) & 1;
      auto &ch = tree[id].ch[b];
      if (ch == 0) ch = get_node();
      vec.PB(id);
      tree[ch].lv = i-1;
      id = ch;
    }
    vec.PB(id);
    for (auto i: vec) {
      tree[i].tot++;
      REP(j,S) {
        if ((x>>j)&1) tree[i].cnt[j]++;
      }
    }
  }
  ll qry(int k) {
    int res[S];
    memset(res, 0, sizeof(res));
    //dump(k, BS(xmask));
    int id = root;
    while (id) {
      if (tree[id].lv == -1 or tree[id].tot <= k) {
        REP(i,S) {
          if ((xmask>>i)&1) res[i] += min(tree[id].tot - tree[id].cnt[i], k);
          else res[i] += min(tree[id].cnt[i], k);
        }
        break;
      }
      int lc = tree[id].ch[0 ^ ((xmask>>tree[id].lv)&1)];
      int rc = tree[id].ch[1 ^ ((xmask>>tree[id].lv)&1)];
      if (tree[lc].tot >= k) id = lc;
      else {
        REP(i,S) {
          if ((xmask>>i)&1) res[i] += tree[lc].tot - tree[lc].cnt[i];
          else res[i] += tree[lc].cnt[i];
        }
        id = rc;
        k -= tree[lc].tot;
      }
    }
    ll r = 0;
    REP(i,S) {
      //if (i < 5) dump(i, res[i]);
      r += (1LL << i) * res[i];
    }
    return r;
  }
} trie;

int N,Q;
int ip[MAXN];

int main() {
  IOS;
  int nT;
  cin>>nT;
  int big = 0;
  REP1(cas,1,nT) {
    dump(cas);
    cin>>N>>Q;
    if (N + Q > 200) big++;
    assert(1 <= N and N <= 100000);
    assert(1 <= Q and Q <= 100000);
    trie.init();
    REP(i,N) {
      cin>>ip[i];
      assert(0 <= ip[i] and ip[i] <= MAX);
      trie.add(ip[i]);
    }
    REP(_,Q) {
      int cmd,x;
      cin>>cmd>>x;
      assert(cmd == 1 or cmd == 2);
      if (cmd == 1) {
        assert(0 <= x and x <= MAX);
        trie.rox(x);
      } else {
        assert(1 <= x and x <= N);
        ll res = trie.qry(x);
        cout<<res<<"\n";
      }
    }
  }
  assert(big <= 5);

  return 0;
}

Problem H – HH Country

題意是給一棵樹和至多十萬個的查詢。每次詢問一個點集內任兩點的距離總和。

作法一：虛樹 & DP

如果題目中只有一筆詢問，則可以輕易地用動態規劃解決。

考慮一個大小為

$k$ 的詢問點集，我們其實可以把所有該詢問中關心的點抽出來，賦予適當的邊權後形成一棵等價的「虛樹」。而關心的點則由詢問點集與詢問點集中任兩點之 LCA 所組成。不難證明關心點集的大小不超過

$2k$，因此每次在虛樹上做動態規劃即可。

基於 LCA 與 RMQ 的等價轉換，將詢問點集按照 DFS 序排序後，相鄰兩點之 LCA 集合即為任兩點之 LCA 集合，因此我們可以快速地找出關心點集。

本作法可以處理強迫在線版的題目。

作法二：啟發式合併 / 樹分治

由於本題並沒有強迫在線回答詢問，我們先存下所有詢問，之後使用常見的樹上計數技巧如啟發式合併或樹分治亦可以解決本題。