b493. 史蒂芙的外交夥伴 - 高中生程式解題系統

內容

背景

史蒂芙終於有了夥伴，夥伴們各自為了人類國家出訪外交，在大陸版圖中有 $N$ 個小城市，每個城市都有各自的文明發展程度 $A_i$，史蒂芙的夥伴擁有各自能力 $K$ 只能選擇文明發展程度 $A_i$ 小於等於 $K$ 的國家拜訪。一開始國家跟國家之間彼此不相連，隨著外交拓展，小城市決定為史蒂芙的人類國家開一條道路通行另一個小城市，但如果這兩個小城市可以藉由直接相連或間接相連，那這一條道路將不會被建造。

礙於時間有限，史蒂芙手頭上有數個計劃，打算對起點城市到終點城市策劃行程，現在請你算出所有計畫的走訪個數。

題目描述

給定 $N$ 個城市版圖以及 $Q$ 個詢問，一開始城市彼此都不相連，詢問操作有以下兩種

0 X Y
建造城市編號 X 到城市編號 Y 的雙向道路。如果 X 和 Y 本身已經直接相連或間接相連，則忽略此操作。
1 X Y K
詢問路線 X 到 Y 的行程規劃，當夥伴的能力為 $K$ 能走訪的國家個數。

輸入說明

有多組測資。

每一組第一行有兩個整數 $N, \; Q$ 分別為城市個數和詢問個數，接下來有一行 $N$ 個整數 $A_i$ 表示文明程度。

接著有 $Q$ 行，每行上會有一組指令

0 X Y
建造城市編號 X 到城市編號 Y 的雙向道路。如果 X 和 Y 本身已經直接相連或間接相連，則忽略此操作。
1 X Y K
詢問路線 X 到 Y 的行程規劃，當夥伴的能力為 $K$ 能走訪的國家個數。

條件約束

$1 \le N \le 50000, \; 1 \le Q \le 100000$
$1 \le A_i \le N$
$1 \le X, \; Y \le N$
$1 \le K \le N$

加密方法

為了模擬真實情況，每一組數據都進行加密，防止預先知道下一天的情況。
一開始的加密金鑰 $d = 0$，隨後 $d$ 為最近一次詢問的答案。
當輸入為 $\text{0 X Y}$ 應解讀成 $\text{0 X^d Y^d}$，同理 $\text{1 X Y K}$ 應解讀成 $\text{1 X^d Y^d K^d}$
其中 $\text{^}$ 為 $\text{XOR}$ 互斥或運算子。

例如範例輸入的解密結果為

7 11
1 5 2 6 3 7 4
0 2 4
0 1 2
0 1 3
0 3 7
1 4 7 3
1 5 6 7
0 2 5
0 5 3
1 4 5 5
0 3 6
1 5 6 4

輸出說明

對於每一個詢問輸出一行。

範例輸入 #1

7 11
1 5 2 6 3 7 4
0 2 4
0 1 2
0 1 3
0 3 7
1 4 7 3
1 7 4 5
0 2 5
0 5 3
1 1 4 5
0 1 4
1 7 4 6

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <10M
公開測資點#3 (10%): 1.0s , <10M
公開測資點#4 (10%): 1.0s , <10M
公開測資點#5 (10%): 1.0s , <10M
公開測資點#6 (5%): 1.0s , <10M
公開測資點#7 (5%): 1.0s , <10M

提示：

標籤:

函數式線段樹啟發式合併

出處:

[管理者：

morris1028 (碼畜) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」