對于每一個詢問，直接暴力在每一個序列中二分查詢
時間複雜度為$o(nk)-o(k\log n)$
将所有序列合并後排序，并對每一個元素預處理出每個序列中第一個大于等于其的元素（位置），那麼隻需要在總序列中二分并輸出該位置預處理的答案即可
關于這個預處理，顯然隻需要從後往前掃描一遍總序列即可
時間複雜度為$o(nk^{2})-o(k+\log nk)$
使用分治歸并，并對合并後序列的每一個元素預處理出參與合并的兩個序列第一個大于等于其的元素位置
對于查詢，隻需要在總序列中二分一次，并根據預處理的資訊遞歸下去即可
時間複雜度為$o(nk\log k)-o(k+\log nk)$
事實上，隻需要将下标為偶數的項參與合并，此時即找到第一個大于等于"其"的偶數項，再判斷上一項是否大于等于"其"即可，這樣查詢的複雜度并沒有變化
（另外，為了避免特判可以強制将最後一項也加入）
沿用做法3，并做此優化，歸納可得每一個位置上的序列長度都為$n$，複雜度即降為$o(nk)$
當然，直接沿用做法2也是可以的，即令$\{b_{k}\}=\{a_{k}\}$且$\{b_{i}\}$為$\{a_{i}\}$和$\{b_{i+1}\}$合并的結果，同樣在合并後預處理相同的資訊，通過此優化不難證明$\{b_{i}\}$的長度和為$o(nk)$
時間複雜度為$o(nk)-o(k+\log nk)$
View Code
給定一張$k$個點的DAG，每個點上有一個長為$n$的單調不下降序列$\{a_{i}\}$
$m$次詢問$x$和一條路徑，求出每一個路徑上的序列中第一個大于等于$z$的元素
保證每一個點的入度和出度均不超過$d$
題解：
類似于做法4，在葉子上令$\{b_{leaf}\}=\{a_{leaft}\}$且$\{b_{i}\}$為$\{a_{i}\}$和$\forall (i,j)\in E,\{b_{j}\}$合并的結果（後者合并時隻取下标為$d+1$的倍數的項），并預處理相同的資訊
令$L_{i}$為$i$上序列的長度，則有$L_{i}=n+\frac{\sum_{(i,j)\in E}L_{j}}{d+1}$，進而有
$$
\sum_{i\in V}L_{i}=\sum_{i\in V}(n+\frac{\sum_{(i,j)\in E}L_{j}}{d+1})\le \sum_{i\in V}(n+\frac{d}{d+1}L_{i})
将其化簡，也即$\sum_{i\in V}L_{i}\le (d+1)nk$
簡單分析，可以發現預處理的時空複雜度均為$o(d\sum_{i\in V}L_{i})$，由此也即$o(d^{2}nk)$
另外，由于隻取了$d+1$的倍數項，查詢時最多要向前找$d$次，即最壞要找$o(dk)$次
（顯然$d$要很小此做法才較優，是以二分做到$o(k\log d)$沒有意義）
時間複雜度為$o(d^{2}nk)-o(dk+\log nk)$