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
2 0 2 3
測資資訊：
記憶體限制：
512
MB
提示 ：
出處:
[管理者：
morris1028
(碼畜)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||