弱弱的 JS 一等來(lái)發(fā)篇題解。

T1 種花（plant）

T1 還是很簡(jiǎn)單的。

肉眼觀察就可以發(fā)現(xiàn)，F(xiàn) 形是可以由 C 形長(zhǎng)出來(lái)的。所以還是就演變成如何求 C 形的個(gè)數(shù)。

我們考慮枚舉每一個(gè)形狀的左上端點(diǎn)。那么以這個(gè)點(diǎn)延展開(kāi)來(lái)的 C 形的個(gè)數(shù)就應(yīng)該是這個(gè)點(diǎn)向右最多能延展的格子數(shù)與其能向下延展的每個(gè)格子的向右延展的格子數(shù)乘積的和。即：

預(yù)處理求??和 還是很好辦的。最后前綴和優(yōu)化一下即可。

T2 喵了個(gè)喵（meow）

T2 非常搞人心態(tài)。

看一眼 ?的范圍，有一個(gè)非常容易想的辦法，我們可以將這么多卡牌攤開(kāi)，這樣的話，我們就可以盡量把每一種類型的牌露在棧頂或者壓在棧底。這就分別對(duì)應(yīng)了兩種操作方式。

情況 1：

一通亂消，這時(shí)候我們的棧是夠用的。也就是說(shuō)，一個(gè)棧放一對(duì)牌是沒(méi)有問(wèn)題的。這樣似乎用不到操作 2。

情況 2：

多了一種牌。嘶……這樣我們就必須用到操作 2 了。這也就意味著我們得留出一個(gè)空棧來(lái)放進(jìn)行操作 2 的牌。我們暫且叫它?。（(^-^)：stack of emptyness 的意思，不要亂想）

顯然不是每一張牌都要無(wú)腦塞到? 當(dāng)中去的。我們看一看別的棧，發(fā)現(xiàn)我們可以瞄準(zhǔn)別的棧棧底的牌，貌似很可以？然而這就會(huì)出現(xiàn)我們要等的牌很久沒(méi)來(lái)導(dǎo)致堆積成山的形勢(shì)出現(xiàn)。我們現(xiàn)在考慮預(yù)支未來(lái)：瞄準(zhǔn)放在棧頂?shù)呐啤@么一來(lái)反而可以，因?yàn)楹竺嬉纬傻臈５着贫际乾F(xiàn)在的棧頂牌。

現(xiàn)在我們記情況 1 中的策略為策略 A，情況 2 的策略為策略 B。一開(kāi)始我們先歸類：將牌種類為? 的牌扔到??號(hào)棧去。然后判斷有沒(méi)有前面的牌在里面，有就放進(jìn)去；如果 與牌堆頂?shù)呐剖峭悾敲淳桶堰@兩張牌塞到 里面去，接著按照策略 A 或 B 處理都沒(méi)問(wèn)題。

T3 建造軍營(yíng)（barrack）

T3 有點(diǎn)紙老虎。

B 國(guó)炸掉了割邊之后，圖才會(huì)不連通。我們先用 Tarjan 求出邊雙之后縮點(diǎn)，整個(gè)圖就變成一個(gè)樹(shù)嘍。想辦法搞樹(shù)形 dp。

令? 為? 的子樹(shù)中沒(méi)有 / 有軍營(yíng)的方案數(shù)。當(dāng)然啦，若有軍營(yíng)，則所有的軍營(yíng)都必須要和??連通。再令? 為此邊雙分量中點(diǎn)的個(gè)數(shù)， 為此邊雙分量中邊的個(gè)數(shù)。

先考慮如何統(tǒng)計(jì)答案。我們強(qiáng)制讓??子樹(shù)外的點(diǎn)都不建軍營(yíng)，同時(shí)一定不選 的邊。

令? 為? 的子樹(shù)中邊的個(gè)數(shù)。

則：

顯然：

初始化：

T4 比賽（Match）

久違的數(shù)據(jù)結(jié)構(gòu)。

離線，線段樹(shù)維護(hù)詢問(wèn)……沒(méi)了？

確實(shí)，沒(méi)了。但是碼量有點(diǎn)小大。

呼，高中的第一次 NOIP 就這么結(jié)束了。