b492: 史蒂芙的外交序列
Tags : 函數式線段樹 劃分樹 樹套樹 歸併樹
Accepted rate : 19人/22人 ( 86% ) [非即時]
評分方式:
Tolerant

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

Content

背景

史蒂芙為了人類國家決定出遠門外交,在一條神秘谷徑中有 $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$

Input

有多組測資。

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

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

  • $1 \le N, Q \le 50000$
  • $1 \le A_i \le N$
  • $1 \le L \le R \le N$
  • $1 \le K \le N$
Output
對於每個詢問輸出一行,第一個整數為探訪個數,第二個整數為滿意程度 $\mod 1000000007$ 的結果。
Sample Input #1
7 4
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
4 6 6
Sample Output #1
2 6
0 0
3 6
2 18
測資資訊:
記憶體限制: 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
Hint :
Tags:
函數式線段樹 劃分樹 樹套樹 歸併樹
出處:
[管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」