CF1767F Two Subtrees 題解——2025.9.2 鮮花
CF1767F Two Subtrees 題解
脳漿炸裂ガール
脳漿(のうしょう)炸裂(さくれつ)ガール
nou shou sa ku re tsu ga ru
作詞:れるりり
作曲:れるりり
編曲:れるりり
唄:初音ミク·GUMI
自問自答(じもんじとう) 無限苦言(むげん くげん)ヤバイ
ji mon ji tou mu gen ku gen ya ba i
自問自答 無限撓騷 不好!
挫傷(ざしょう)暗礁(あんしょう)に乗(の)り上(あ)げている
za syou an syou ni no ri a ge te i ru
觸礁撞上了挫傷暗礁
前頭葉(ぜんとうよう)から新(あら)たな痛(いた)みを
zen tou you kara a ra ta na i ta mi wo
從前額葉 傳來新的痛覺
共有(きょうゆう)したがる情報(じょうほう)バイパス(bypass)
kyo u yuu shita ga ru jyou hou bai pa su
想要共有 收斂不了
収束(しゅうそく)できない不條理(ふじょうり) スク水(み)
syuu so ku de ki nai fu jyou ri su ku mi
沒有條理 學校泳衣
吐瀉物(としゃぶつ)噴出(ふんしゅつ) 妄想(もうそう)デフラグ
to sya bu tsu fun syu tsu mou sou de fu ra gu
嘔吐物 噴出 妄想碎片整理
前方(ぜんほう)不注意(ふちゅうい) 顏面(がんめん)崩壊(ほうかい)
zen hou fu cyuu i gan men hou kai
前方不注意 臉部崩壞
どうでもいいけどマカロン食(た)べたい
dou de mo ii ke do ma ka ron ta be tai
雖說什么都可以 但是想吃馬卡龍
諸行(しょぎょう)無常(むじょう)のリズムに合(あ)わせて
syo gyou mu jyou no ri su mu ni a wa se te
合上了變換無常的旋律
ワンツーステップ(one two step)で女子(じょし)力(りょく)上(あ)げれば
wan tsu- su teppu de jyo shi ryo ku a ge re ba
一二三跳的 使出女子之力
ゆるふわ草食(そうしょく) 愛(あい)され給(たも)うて
yu ru fu wa sou syo ku ai sa re ta mou te
卷發草食 乞求被愛
そう仰(おお)せにては候(そうら)えども
sou oo se ni te wa sou ra e do mo
這樣子仰著頭等待著
就職(しゅうしょく)できない無理(むり)ゲーパスして
syuu syo ku de ki nai mu ri ge-pa su shi te
找不到工作
面接(めんせつ)ばっくれ交渉(こうしょう)決裂(けつれつ)
men se tsu ba kku re kou syou ke tsu re tsu
逃避面試 交涉決裂
攜帯(けいだい)紛失(ふんしつ) 精神(せいしん)壊滅(かいめつ)
kei dai fun shi tsu sei shin kai me tsu
手機丟失 精神崩潰
(※自律神経(じりつしんけい)に問題(もんだい)があるかもしれません)
(ji ri tsu shin kei ni mon dai ga a ru ka mo shi re ma sen)
(可能是自律神經有問題)
ペラペラな御托(ごたく)并(なら)べちゃって
pe ra pe ra na go ta ku na ra be cya tte
霹靂啪啦的叨叨噓噓著
結局(けっきょく)♂♀(オスメス)凹凸(おうとつ)擦(こす)って気持(きも)ち良(よ)くなりたいだけなら
ke kkyo ku o sa be tsu ou to tsu go su tte ki mo chi yo ku na ri ta i dai ke na ra
最終想要○×摩擦 獲取快感
その棒(ぼう)のようなもので私(わたし)を毆(なぐ)って
so no bou no you na mo no de wa ta shi wo na gu tte
就用像那根棒一樣的東西來【//////】插【///////】我
紅(あか)い華(はな)が咲(さ)き亂(みだ)れて
a kai ha na ga sa ki ma da re te
紅色的花朵 凌亂的開放
私(わたし)は脳漿(のうしょう)炸裂(さくれつ)ガール
wa ta shi wa nou syou sa ku re tsu ga-ru
我就是腦漿爆裂女孩
さあさあ狂(くる)ったように踴(おど)りましょう
sa sa ku ru tta you ni odo ri ma syou
狂亂的跳舞吧
どうせ100年后(ひゃくねんご)の今頃(いまごろ)には
dou se hya ku nen go no i ma go ro ni wa
反正100年以后的此時
みんな死(し)んじゃってんだから
min na shin jya tten da kara
大家都死了啊
震(ふる)える私を抱(だ)きしめて
fu ru e ru wa ta shi wo da ki shi me te
抱緊顫抖的我
もっと激(はげ)しく脳汁(のうじる)分泌(ぶんぴつ)させたら
mo tto ha ge shi ku nou ji ru bun pi tsu sa se tara
如果讓腦汁更加猛烈地分泌出
月(つき)の向(む)こうまでイっちゃって
tsu ki no mu kou ma de i cchya tte
就會噴向月亮的那頭
(※この電話番號(でんわばんごう)は???現在(げんざい)使(つか)われておりません)
( ko no den wa ban gou wa... gen zai tsu ka wa re te o ri ma sen)
(你所撥打的電話……你所撥打的電話是空號)
一問一答(いちもん一いちとう) カリスマ(charisma)弁護士(べんごし)
i chi mon- i chi tou ka ri su ma ben go shi
一問一答的大律師
How-to 本(ほん)を売(う)り上(あ)げている
How-to hon wo u ri a ge te i ru
大賣How-to書
スタバでキャラメル(caramel )濃(こ)いやつ頼(たの)んで
su ta ba de kya ra me ru ko i ya tsu ta non de
禁煙餐館里要一顆特濃奶糖
ドヤ顏(かお)したがる東京(とうきょう)バイアス(bias)
do ya ka o shita ga ru tou kyou ba i a su
想擺出怎樣臉的東京偏見
量產(りょうさん)アイドル(idol)一蓮(いちれん)托生(たくしょう)
ryou san a i do ru i chi ren taku syou
量產偶像 一蓮托生
お祭(まつ)り道化師(どうけし ) 戀愛(れんあい) NG
o ma tsu ri dou ke shi ren ai NG
慶典小丑 戀愛NG
子悪魔(こあくま)メイクで觸覚(しょっかく )生(は)やして
ko a ku ma me i ku de syo kka ku ha ya shi te
用小惡魔裝扮 促生觸覺
3時(じ)のおやつはマカロン食(た)べます
san ji no o ya tsu wa ma ka ron ta be ma su
3點的甜點是吃杏仁餅干
スラップベースの刻(きざ )みに合(あ)わせて
su ra ppu be-su no kaza mi ni a wa se te
合上貝斯的紋路
ハラキリ フジヤマ ゲイシャ(げいしゃ)が唄(うた)えば
ha ra ki ri fu ji yama ge i sya ga u ta e ba
切腹 富士山 藝妓唱歌的話
思(おも)わず女子會(じょしかい) 飛(と)び入(い)り參戦(さんせん)
o mo wa zu jyo shi kai to bi i ri sansen
不假思索就飛進女同酒會參戰
スイーツ(sweets)目當(めあ )てでツイート控(ひか)えめ
su i- tsu me a te de tsu i to hi ka e me
照下面前的甜點發到推特上
二次會(にじかい) 焼肉(やきにく) 五反田(ごたんだ)
ni ji kai ya ki ni ku go tan da
二次會 烤肉 五反田
ググって情弱(じょうじゃく)ウイルス(Virus )感染(かんせん)
gu gu tte jyou jya ku u i ru su kan zen
谷歌一下 不會上網 病毒感染
薄型(うすがた)ガラケー2年(にねん)で解約(かいやく)
u su ga ta ga ra ke- ni nen de kai ya ku
超薄裸機 2年 解約
(※暗證(あんしょう)番號(ばんごう)をもう一度(いちど)お確(たし)かめください)
( an syou ban gou wo mou i chi do o ta shi ka me ku da sai)
(請再次確認你的登陸密碼)
手招 (てまね)きされて尻尾(しっぽ)振(ふ)ってる
te ma ne ki sa re te shi bbo fu tte ru
手招搖起來 像九尾一樣
従順(じゅうじゅん)な子犬(こいぬ)みたいな可愛(かわい)さは最初(さいしょ)から求(もと)
めてないから
jyuu jyun na ko i nu mi tai na ka wa i sa wa sai syo kara mo to me te na i kara
像順的小狗一樣的可愛 最開始就沒有追求這個
その麻縄(あさなわ)で私(わたし)の身體(からだ)を縛(しば)って
so no a sa na wa de watashi no karada o shiba tte
用這條麻繩綁住我的身體
マルキ?ド?サド 枕(まくら)仕事(しごと)
maruki·do·sado makura shi go to
馬路基 德 薩德
私(わたし)は脳漿(のうしょう)炸裂(さくれつ)ガール
watashi wa nou syou sa ku re tsu ga-ru
我就是腦漿爆漿女孩
さあさあ狂(くる)ったように踴(おど)りましょう
sa sa ku ru tta you ni o do ri ma syou
瘋狂的跳舞吧
どうせ100年(ひゃくねん)后(ご)の今頃(いまごろ)には
dou se hya ku nen go no i ma go ro ni wa
反正一百年以后的現在
みんな死(し)んじゃってんだから
min na shin jya tten da kara
大家都死掉了吧
今(いま)すぐ私(わたし)を抱(だ)きしめて
i ma su gu watashi wo da ki shi mete
馬上把我抱緊
もっとびしょびしょ脳內(のうない)麻薬(まやく)に溺(おぼ)れて
mo tto bi syo bi syo no u nai ma ya ku ni o bo re te
更加沉溺于腦內麻藥
宇宙(そら)の彼方(かなた)へ漕(こ)ぎ出(だ)して
so ra no ka na ta e ko gi da shi te
駛向宇宙的另一端
さあさあ狂(くる)ったように踴(おど)りましょう
sa sa ku ru tta you ni o do ri ma syou
瘋狂的舞蹈吧
きっと100年(ひゃくねん)后(ご)の私(わたし)は
ki tto hyaku nen go no watashi wa
100年我一定
美少女(びしょうじょ)に生(う)まれ変(か)わってるはずだからさ
bi syou jyo ni u ma re ka wa tte ru ha zuda kara sa
會變成美少女重生
{さ}古(ふる)くさい身體(からだ)は脫(ぬ)ぎ舍(す)てて
[sa] fu ru ku sai kara da wa nu gi su te te
擺脫我陳舊的身體
もっと激(はげ)しく脳汁(のうじる)分泌(ぶんぴつ)させたら
mo tto ha ge shi ku nou ji ru bun pi tsu sa s e tara
讓腦汁更加猛烈地分泌
月(つき)の向(む)こうまでイっちゃって
tsu ki no mu kou ma de i ccya tte
噴向月亮那邊

首先可以直接四維莫隊套一個分塊,這個相當于是維護一個支持加入、撤銷、查詢眾數的 \({\cal O}(1) - {\cal O}(\sqrt n)\) 結構,這個很好做。
我們考慮一個更快的做法:
我們多考慮考慮樹的性質,我們發現每次查詢是一個子樹,考慮 P7124 [Ynoi2008] stcm,我們其實可以將子樹拍成前綴,這樣只有兩個指針了。
具體的做法有兩種,一種是 dsu on tree,一種是直接在 dfn 序上分治。無論怎樣,現在問題變成了有一個長為 \(n\log n\) 的操作序列,每個操作形如插入或撤銷,我們要在這個上面做莫隊。
但是這樣就不是撤銷而是刪除了,考慮一個 \({\cal O}(1) - {\cal O}(\sqrt n)\) 結構。
首先若我們輸出的是次數而不是最小的值,我們直接維護每個數的出現次數和所有出現次數的桶,因為每次次數只能 \(\pm 1\),所以答案也最多 \(\pm 1\),可以直接維護。
但是我們要維護的是值,所以我們值域分塊,查詢時先確定在那個塊里在枚舉塊內每個元素即可。
復雜度懶得算了,反正是 \(n\sqrt n{\rm polylog}\) 的吧。
這個 K8 寫了,我沒寫。
P





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

浙公網安備 33010602011771號