b493. 史蒂芙的外交夥伴
標籤 : 函數式線段樹 啟發式合併
通過比率 : 9人/12人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-08-17 11:35

內容

背景

史蒂芙終於有了夥伴,夥伴們各自為了人類國家出訪外交,在大陸版圖中有 $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
公開 測資點#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 (碼畜) ]

本題狀況 本題討論 排行

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