閑話 Day3：

所以，就不得不功利化一點了。

而實際上呢。。。

這是什么，有意思，研究一下。
這是什么，好優(yōu)秀，實現(xiàn)一下。
這是什么，計數(shù)題，綠的，不會，下一個。
這是什么，計數(shù)題，黃的，不會，下一個。
。。。。。

我終于意識到了做事憑興趣這一點是很難改變的。

所以這幾天又去仔細(xì)參悟了一下分治與分治數(shù)據(jù)結(jié)構(gòu)。
本來想記下來的，但是感覺東西很多很費時間。
所以等過幾天再說吧。
大概在南京的時候會寫一寫吧。

這次是學(xué)術(shù)閑話來著，所以就把剛剛口胡出來的東西寫一寫吧。

線段樹分治

這道題正解貌似是點分治一類的東西。
但是我記得在模擬賽里面遇到這個題的時候題解給的是線段樹分治。
事實上，使用線段樹分治 + \(O(1)\) LCA 可以做到 \(O(n \log n)\) 的時空復(fù)雜度。
還是非常優(yōu)秀的。

然而，今天突然就想到了一個問題：
線段樹分治的空間復(fù)雜度能不能做線性。

（主要是參悟了分治數(shù)據(jù)結(jié)構(gòu)與分治的關(guān)系之后感覺很可做）

事實證明可以做到而且并不難想。

首先前置知識，為什么線段樹區(qū)間修改的復(fù)雜度是對的。

當(dāng)一個區(qū)間在線段樹上向下遞歸的時候，分為兩種情況：

1. 左右都不貼邊界。
2. 貼左邊界或貼右邊界。

容易發(fā)現(xiàn)，對于第一種情況，最多只會分裂一次，然后變成兩個貼邊界的區(qū)間。
而對于第二種情況，要么單向遞歸，要么雙向遞歸但是其中一邊是滿的。
而滿的區(qū)間顯然就不會向下遞歸了。

所以最終的復(fù)雜度為 \(O(\log n)\)，嚴(yán)謹(jǐn)分析的話最多會訪問 \(4 \times \log n\) 個點，修改最多影響到 \(2 \times \log n\) 個點。

好了回到原問題，線段樹分治。

假如現(xiàn)在有 \(m\) 個區(qū)間，我們先不把它們都下放到線段樹對應(yīng)節(jié)點上，先統(tǒng)一堆到根節(jié)點。
現(xiàn)在我們要去遍歷整棵樹了，到達一個節(jié)點的時候再去把區(qū)間都下方。

首先考慮左右都不貼邊界的情況，顯然不會影響空間復(fù)雜度。
畢竟都是單向遞歸，而且只會分裂一次。

再考慮貼左邊界的情況，其實也好處理。
要么只向左遞歸，不考慮。
要么左右遞歸，但是向左遞歸的部分直接就是整個節(jié)點修改，所以貢獻是 \(O(1)\) 的。
而且接下來馬上就要遞歸左子樹了，馬上就會被消掉。

最后考慮貼右邊界的情況，這個有點寄。

如果只向右遞歸還是不用處理。
考慮左右都遞歸。
如果我們直接分裂到左右子樹上，會導(dǎo)致某個區(qū)間直接霸占一整個左鏈的所有右兒子。
然后空間復(fù)雜度又變成 \(O(n \log n)\) 了。

事實上，我們可以先將其整個下放到左兒子上。
然后等左子樹遞歸完了之后，再從左兒子那里拿回來。
然后下放到右子樹，這個是 \(O(1)\) 的沒有什么問題。

不理解的話可以手動模擬一下。
畫出來其實有點像蕾米的翅膀來著。

這樣的話相當(dāng)于是一個遞歸又回溯的過程。
時間復(fù)雜度不變，一個區(qū)間還是只遍歷 \(O(\log n)\) 個節(jié)點。
但是空間復(fù)雜度直接降到了 \(O(n)\) 而且常數(shù)并不大。
全是 vector 操作啊那沒事了。

實現(xiàn)的話。。。
雖然看上去上述流程很麻煩而且還要分類討論。
但是實際上寫成遞歸函數(shù)的話也還好。
至少并沒有比常規(guī)的線段樹分治難寫多少。

等我有時間了去實現(xiàn)一個，現(xiàn)在先咕咕咕。

上次報了個公開賽，但是只是看了看最后一題，沒有打。
我自己也在 INOH 和 STAOI 分別出了一個題。

但是，出這些題的目的是什么？

如果只是為了難住別人的話那可就太閑了，屬實無意義。
如果是為了分享某些 trick 的話其實可以寫博客的。
而且像我這樣自己啥都不會也沒啥必要去往外分享東西。。。

然后我才發(fā)現(xiàn)貌似這次出題比較偏離本意了。

本來確實是發(fā)現(xiàn)了一個有意思的東西。
然后決定出個題玩玩。
然后發(fā)現(xiàn)其他方法跑得也很快，可以草過去。
然后就開始對著除了這個 trick 以外的地方卡常，疊科技。
然后把其他做法卡掉了。

每一步都和上一步銜接緊密，但是總的來看完全偏離了本意。

再考慮考慮，其實有很多的事情都是這個樣子。
隨著時間發(fā)展完全偏離了其本意，但是又處于某些原因無法廢除/修改。
或者說，甚至很多人都沒有意識到。

有一些想說的例子，但是不合適，不說了。
換一個經(jīng)典無害的吧。
（怎么又舉這種例子啊啊啊啊啊啊啊啊啊啊）

關(guān)于出題/考試。
考試原本的目的是啥來著，選拔人才是吧。
出題也就是全面考察一下知識掌握程度和綜合素養(yǎng)一類的。

但是隨著教育的發(fā)展這東西變成了啥。
學(xué)生開始去學(xué)做題套路，應(yīng)試技巧，背一些前人總結(jié)下來的模板。
真的就是一些除了應(yīng)付考試啥實際意義都沒有的東西。

在閑話 Day3 里面貌似稍微提到了一點，不多說了。
當(dāng)時感覺，只是因為沾了不少功利化的東西才會演變成這樣。

但是現(xiàn)在看來好像并不是。即使功利無關(guān)也會這樣。
我們周圍確實就存在著大量類似的無意義的東西。
有些可能類似于形式主義吧，反正大體就是完全偏離本意。

經(jīng)典例子，為啥鍵盤上的字母是亂序排布的。

在最開始，確實是順序排布的。
但是當(dāng)時的鍵盤有一個很大的問題，就是不能同時按兩個鍵，否則就會卡死。

鍵位順序排布確實很有利于提高打字效率。
但是打字快了就不可避免的會出現(xiàn)卡死的現(xiàn)象，反而降低了效率。

于是有個人就發(fā)明了現(xiàn)在的這種鍵盤。
特殊構(gòu)造使得常用的詞塊隔得比較遠(yuǎn)
發(fā)售之后，由于其非常獨特，當(dāng)時非常火。
再加上確實不容易卡死（打字速度下降了不少），所以后來就成為了主流鍵盤，一直到現(xiàn)在。

大概總結(jié)一下，目的是提高效率避免卡死。

但是現(xiàn)在呢？
現(xiàn)在的鍵盤同時按下所有鍵都不會卡死的吧。
字母亂序排序一定程度上不僅降低了效率，還提高了上手難度。
然而現(xiàn)在再也看不到順序排布的鍵盤了。
甚至沒有人再去提起過這個東西。

隨著時間的推移和時代的發(fā)展，鍵盤的結(jié)構(gòu)違背了其本身的目的。

對此的一種解釋是，兼容性問題，習(xí)慣問題。
多數(shù)人都習(xí)慣了亂序鍵盤，現(xiàn)在推出順序鍵盤沒有市場。
或者說，第一批使用順序鍵盤就意味著要同時適應(yīng)兩種不同的鍵盤。

但是。。。。
當(dāng)時改成亂序鍵盤就能適應(yīng)，現(xiàn)在改回順序鍵盤就無法適應(yīng)是吧。

如果多數(shù)人都能去仔細(xì)考慮這個問題的話可能鍵盤模式早就改回去了。
或者，改成另一種效率更高的排布方式。
普及這種東西的成本可能要遠(yuǎn)低于普及 5G 或者新款手機一類的，畢竟并不是所有人都每天接觸鍵盤。
而且?guī)淼氖找娲蟾攀欠浅４蟮摹?/p>

所以最后得出的結(jié)論是，我真閑啊。

貌似多數(shù)人都不會在每個細(xì)節(jié)處都去考慮，這種設(shè)計的本意是什么。
因此，大量的偏離本意的東西就這樣被人們忽視，然后起著負(fù)作用。

大概我是沒有必要關(guān)心這種東西的吧。
但是多留意一下總是有好處的。
至少可以讓我少做很多毫無意義的事情。

忘了聽哪里說的了，你谷要取消博客了（????）
其實也好，至少不至于以后突然翻到了現(xiàn)在寫的博客。
然后打開一看，答辯。
就像看小學(xué)寫的作文一樣。

這已經(jīng)將近 40 天了吧，怎么才寫了 ⑨ 期閑話。
。。。。。