2025.2.27 鮮花
波長 題解
群青
嗚呼いつもの様に
過ぎる日々にあくびが出る
さんざめく夜越え今日も
渋谷の街に朝が降る
どこか虛しいような
そんな気持ち
つまらないな
でもそれでいい
そんなもんさ
これでいい
知らず知らず隠してた
本當(dāng)の聲を響かせてよほら
見ないフリしていても
確かにそこにある
感じたままに描く
自分で選んだその色で
眠い空気纏う朝に
訪れた青い世界
好きなものを好きだと言う
怖くて仕方ないけど
本當(dāng)の自分
出會えた気がしたんだ
嗚呼手を伸ばせば伸ばすほどに
遠(yuǎn)くへゆく
思うようにいかない今日も
また慌ただしくもがいてる
悔しい気持ちも
ただ情けなくて
涙が出る
踏み込むほど
苦しくなる
痛くもなる
感じたままに進(jìn)む
自分で選んだこの道を
重いまぶた擦る夜に
しがみついた青い誓い
好きなことを続けること
それは楽しいだけじゃない
本當(dāng)にできる
不安になるけど
何枚でも
ほら何枚でも
自信がないから描いてきたんだよ
何回でも
ほら何回でも
積み上げてきたことが武器になる
周りを見たって
誰と比べたって
僕にしかできないことはなんだ
今でも自信なんかない
それでも
感じたことない気持ち
知らずにいた想い
あの日踏み出して
初めて感じたこの痛みも全部
好きなものと向き合うことで
觸れたまだ小さな光
大丈夫行こうあとは楽しむだけだ
全てを賭けて描く
自分にしか出せない色で
朝も夜も走り続け
見つけ出した青い光
好きなものと向き合うこと
今だって怖いことだけど
もう今はあの日の透明な僕じゃない
ありのままの
かけがえの無い僕だ
知らず知らず隠してた
本當(dāng)の聲を響かせてよほら
見ないフリしていても
確かにそこに今もそこにあるよ
知らず知らず隠してた
本當(dāng)の聲を響かせてよさあ
見ないフリしていても
確かにそこに君の中に

很早以前模擬賽的題了,感覺挺有意思,寫一下。
有點反人類。
首先你肯定會二分答案 \(w\),考慮 check,先對 \(a\) 前綴和一下,于是變成了后綴減 \(1\),使其滿足任意 \(j > i, a_j - a_i < w\)。
考慮掃這個,維護(hù)一個 \(lim\),每次遇到 \(a_i\) 若 \(a_i > lim\) 就做后綴減直到 \(a_i = lim\),然后更新 \(lim \gets^{\min} a_i + w\)。
發(fā)現(xiàn)后綴減純粹的玩原神,不如讓 \(lim\) 加,容易發(fā)現(xiàn)其是等價的。
正解一定是要快速統(tǒng)一維護(hù) \(L(x)\) 表示 \(w = x\) 時的 \(lim\) 和 \(S(x)\) 表示 \(w = x\) 時操作次數(shù)和的,考慮如何做,將其操作依次寫出來:
考慮到 \(L(x)\) 的變化,每次和一條水平線取 \(\max\) 和和一條 \(k = 1\) 的直線取 \(\min\),容易發(fā)現(xiàn)其具有單調(diào)性,畫畫圖容易發(fā)現(xiàn)其每次一定是將一段前綴推平,直接上棧都能維護(hù)了。
對于 \(S\) 不太好對 \(L\) 整體做,考慮對每段分別做,但是發(fā)現(xiàn)有貢獻(xiàn)的段必然滿足 \(L(x) < a_i\),但是 \(L(x) < a_i\) 在下一步就會被立刻推平,所以復(fù)雜度均攤也是對的。
說這題反人類的原因是這個題第一眼看上去有個類似貪心的東西明顯比二分答案有前途,但實際上那個貪心做法并沒有比較正常的正解寫法。
題解中說的差分約束做法我實在是看不懂了,有人講解一下嗎?
P

本文來自博客園,作者:xrlong,轉(zhuǎn)載請注明原文鏈接:http://www.rzrgm.cn/xrlong/p/18740427
版權(quán)聲明:本作品采用 「署名-非商業(yè)性使用-相同方式共享 4.0 國際」許可協(xié)議(CC BY-NC-SA 4.0) 進(jìn)行許可。

浙公網(wǎng)安備 33010602011771號