傳送門:https://atcoder.jp/contests/arc068

前言:智商不在線.

CD:簽到題

E:思維,數(shù)據(jù)結(jié)構(gòu)

在說這道題之前,還是強調(diào)一個結(jié)論:調(diào)和級數(shù):

題目大意:給你在線段

題目思路:

不難發(fā)現(xiàn):區(qū)間大小 大于等于 d 的區(qū)間一定對答案有貢獻(xiàn).自然想到對區(qū)間大小排序.

考慮區(qū)間長度小于d的區(qū)間:它其中要么含有一個d的倍數(shù).要么沒有.所以我們自然可以將這些區(qū)間插入到樹狀數(shù)組中去.暴力每個點都查詢一下即可.

注:這樣一定是正確的.因為在暴力查詢的過程中.每個區(qū)間最多貢獻(xiàn)一次.所以每一個點的答案都一定來自于不同的區(qū)間貢獻(xiàn).

由于調(diào)和級數(shù),暴力查詢的復(fù)雜度為:

F:又是神仙dp題目,補不下來

兩個推論:

1.一個長度為n的排列插入到雙端隊列中后產(chǎn)生

*可以利用遞推法:假設(shè)長度為n - 1 的排列產(chǎn)生X個方案,新增的n放在每個方案的兩邊將得到 2 * X 個 方案.

2.一個長度為n的排列插入到雙端隊列中后值域的分布一定成"V"字形且最小值一定是1.