2024.8.17 鮮花
コネクト
交(か)わした約束(やくそく)忘(わす)れないよ
『無(wú)法忘卻彼此結(jié)下的約定』
ka wa shi ta yakusoku wasu re nai yo
目(め)を閉(と)じ確(たし)かめる
『輕閉雙眼再次確認(rèn)』
me wo to ji tashika meru
押(お)し寄(よ)せた闇(やみ) 振(ふ)り払(はら)って進(jìn)(すす)むよ
『驅(qū)散聚集而來(lái)的黑暗邁步前進(jìn)吧』
oshiyo seta yami furi hara tte susumuyo
いつになったらなくした未來(lái)(みらい)を
『到底什么時(shí)候我才能夠』
itsuni natta ra nakushita mirai wo
私(わたし)ここでまた見(jiàn)(み)ることできるの?
『在這里重見(jiàn)失去的未來(lái)』
watashi kokode mata miru koto dekiruno
溢(あふ)れ出(だ)した不安(ふあん)の影(かげ)を何度(なんど)でも裂(さ)いて
『將漫溢的不安陰影逐一撕裂』
afuredashita fuanno kagewo nandodemo sa i te
この世界(せかい)歩(あゆ)んでこう
『在這世界里走下去』
kono sekai ayun dekou
とめどなく刻(きざ)まれた 時(shí)(とき)は今(いま)始(はじ)まり告(つ)げ
『無(wú)休止銘刻的時(shí)間此刻終告著開(kāi)端』
tomedonaku kizamareta tokiha ima hajimari tsuge
変(か)わらない思(おも)いをのせ
『載著永恒不變的思念』
kawaranai omoi wo nose
閉(と)ざされた扉(とびら)開(kāi)(あ)けよう
『去開(kāi)啟封閉的門扉吧』
tozasareta tobira akeyou
目覚(めざ)めた心(こころ)は走(はし)りだした未來(lái)(みらい)を描(えが)くため
『覺(jué)醒的心為了描繪未來(lái)開(kāi)始奔騰』
mezameta kokoroha hashi ridashita mirai wo egakutame
難(むずか)しい道(みち)で立(た)ち止(ど)まっても
『即使在曲折的路上停滯不前』
muzukashi i michide tachido mattemo
空(そら)はきれいな青(あお)さでいつも待(ま)っててくれる
『天空也會(huì)滿懷漂亮的蔚藍(lán) 無(wú)時(shí)無(wú)刻不在等候著我』
soraha kireina a o sade itsumo matte tekureru
だから怖(こわ)くない
『所以毫不畏懼』
dakara kowakunai
もう何(なに)があっても挫(くじ)けない
『無(wú)論發(fā)生什么也決不沮喪』
mou naniga atte mo kujikenai
振(ふ)り返(かえ)れば仲間(なかま)がいて
『轉(zhuǎn)身回望有伙伴在』
furikae reba nakama ga ite
気(き)がつけば優(yōu)(やさ)しく包(つつ)まれてた
『細(xì)心一想我總是被溫柔包圍』
kiga tsukeba yasashiku tsutsu mareteta
何(なに)もかもが歪(ゆが)んだ世界(せかい)で
『在充滿扭曲的世界里』
nanimo kamoga yugan da sekaide
唯一(ゆいつ)信(しん)じれるここが救(すく)いだった
『唯一能相信的是我在此被拯救了』
yuitsu shinjireru kokoga suku i datta
喜(よろこ)びも悲(かな)しみもわけあえば強(qiáng)(つよ)まる思(おも)い
『無(wú)論喜悅還是悲傷只要互相分擔(dān)便能更堅(jiān)強(qiáng)』
yoroko bimo kanashimimo wake a e ba tsuyomaru omoi
この聲(こえ)が屆(とど)くのなら
『如果這聲音能夠傳達(dá)得到』
kono koega todo kunonara
きっと奇跡(きせき)はおこせるだろう
『那么奇跡一定會(huì)發(fā)生吧』
kitto kisekiha okoserudarou
交(か)わした約束(やくそく)忘(わす)れないよ
『無(wú)法忘卻彼此結(jié)下的約定』
kawashita yakusoku wasure naiyo
目(め)を閉(と)じ確(たし)かめる
『輕閉雙眼再次確認(rèn)』
me wo toji tashika meru
押(お)し寄(よ)せた闇(やみ) 振(ふ)り払(はら)って進(jìn)(すす)むよ
『驅(qū)散聚集而來(lái)的黑暗邁步前進(jìn)吧』
oshiyoseta yami furi haratte susumuyo
どんなに大(おお)きな壁(かべ)があっても
『哪怕多么大的障礙』
donnani ookina kabega attemo
越(こ)えてみせるからきっと
『也一定跨越給你看』
koete miserukara kitto
明日(あした)信(しん)じて祈(いの)って
『堅(jiān)信明天 深切祈禱』
ashita shinjite inotte
壊(こわ)れた世界(せかい)で彷徨(さまよ)って私(わたし)は
『在崩潰的世界里彷徨的我』
kowareta sekaide samayo tte watashiha
引(ひ)き寄(よ)せられるように辿(たど)り著(つ)いた
『仿佛受到指引一般抵達(dá)此地』
hiki yoserareruyouni tadori tsuita
目覚(めざ)めた心(こころ)は走(はし)り出(だ)した未來(lái)(みらい)を描(えが)くため
『覺(jué)醒的心為了描繪未來(lái)開(kāi)始奔騰』
mezameta kokoroha hashiridashita mirai wo egakutame
難(むずか)しい道(みち)で立(た)ち止(ど)まっても
『即使在曲折的路上停滯不前』
muzukashi i michide tachidomattemo
空(そら)はきれいな青(あお)さでいつも待(ま)っててくれる
『天空也會(huì)滿懷漂亮的蔚藍(lán) 無(wú)時(shí)無(wú)刻不在等候著我』
soraha kireina a o sade itsumo mattete kureru
だから怖(こわ)くない
『所以毫不畏懼』
dakara kowa kunai
もう何(なに)があっても挫(くじ)けない
『無(wú)論發(fā)生什么也決不沮喪』
mou naniga attemo kuji kenai
ずっと明日(あした)待(ま)って
『一直等待著明天』
zutto ashita matte

經(jīng)典問(wèn)題:
給定一個(gè)序列,支持:
-
區(qū)間加
-
區(qū)間 rank
有 \(O(n\sqrt n)\) 的在線做法,但是過(guò)于不實(shí)用,這里重點(diǎn)講比較實(shí)用的離線做法。
考慮分塊,顯然有每次排序 \(+\) 二分的 \(O(n\sqrt n \log n)\) 的樸素做法。
考慮修改上界:散塊的排序。發(fā)現(xiàn)區(qū)間加后加了的部分和不加的部分分別有序,歸并可以做到 \(O(n\sqrt{n \log n})\)。
考慮整塊的二分,直接套分散層疊可以去掉 \(\log\),但過(guò)于難寫,估計(jì)也跑不過(guò)帶 \(\log\) 的。
考慮離線,將整塊的查詢離線,在每次要重構(gòu)或最后統(tǒng)一處理。
可以將查詢排序,用雙指針跑一遍整塊,用基數(shù)排序塊長(zhǎng)取根號(hào)單次復(fù)雜度 \(O(\sum q_i + \sqrt n)\)。
考慮每個(gè)詢問(wèn)在一個(gè)塊內(nèi)最多經(jīng)歷一次排序,\(\sum O(\sum q_i)=O(q\sqrt n)\)。
考慮每次修改最多產(chǎn)生兩個(gè)散塊,復(fù)雜度 \(\sum O(\sqrt n)=O(n\sqrt n)\)。
這鮮花也太水了
updata on 8.18:
其實(shí)這個(gè)做法是和值域相關(guān)的,在保證任意時(shí)刻值域 \(\le 10^9\) 時(shí)復(fù)雜度時(shí)正確的,其原因在于基數(shù)排序。
但是實(shí)測(cè)不如 \(n\sqrt{n\log n}\) 跑的快,可能是我們實(shí)現(xiàn)太差了。
最后感謝 wkh2008 提供思路和進(jìn)行測(cè)試
派蒙——from Pursuing-OIer

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

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