b492. 史蒂芙的外交序列 - 高中生程式解題系統

內容

背景

史蒂芙為了人類國家決定出遠門外交，在一條神秘谷徑中有 $N$ 個小城市，每個城市都有各自的文明發展程度 $A_i$，史蒂芙依照自己的能力 $K$ 只能選擇文明發展程度 $A_i$ 小於等於 $K$ 的國家拜訪，並且這次遠門的滿意程度是所有走訪國家的權重相乘。

礙於時間有限，史蒂芙手頭上有數個計劃，打算對某個區間內的城市策劃行程，現在請你算出所有計畫的預期滿意程度以及走訪個數，由於滿意程度會很大，輸出 $\mod 1000000007$ 的結果。

給定 $N$ 個整數序列 $A[]$ 以及 $Q$ 個詢問，每一個詢問 $[L, R]$ 以及 $K$，請計算 $\sum_{L \le i \le R } [A_i \le K]$ 以及 $\prod_{L \le i \le R, \; A_i \le K } A_i$

輸入說明

有多組測資。

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

接著有 $Q$ 行，每行上三個整數 $L,\; R,\; K$，分別為詢問區間 $[L, R]$ 以及 $K$ 史蒂芙的能力。

輸出說明

對於每個詢問輸出一行，第一個整數為探訪個數，第二個整數為滿意程度 $\mod 1000000007$ 的結果。

範例輸入 #1

7 4
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
4 6 6

範例輸出 #1

測資資訊：

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

提示：

標籤:

函數式線段樹劃分樹樹套樹歸併樹

出處:

[管理者：

morris1028 (碼畜) ]

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