hzoi898 交通網絡 題解？

這題有四樣讀法，你知道么？

出一個毒瘤 ds 的最好方式就是把序列問題直接出到樹上，考察選手樹剖能力。

正確的題意：

給定一棵樹，在時刻 \([tl, tr]\) 鏈加，查時刻 \(t\) 時鏈上值不為 \(0\) 的邊數。

這個題沒啥意思，區間加（任意時刻序列中的值 \(\ge 0\)），區間數 \(0\) 板子，并且還放暴力過了。

考慮一個有點意思的錯誤讀法。

時刻 \([tl, tr]\) 區間加，查時刻 \(t\) 時區間值不為 \(0\) 的極長連續段數。

有兩種做法：

1. Qyun 式：

   考慮直接標記永久化，刪除的時候直接用其兩個兒子更新就可以了。

2. wang54321 式：

   考慮維護區間 \(0\) 的個數 \(x\) 和區間連續兩個都是 \(0\) 的個數 \(y\)。

   發現對于一個區間極長段數 \(= \frac{x * 2 - y * 2}{2} = x - y\)。

   考慮每兩個數之間插入一個虛點，其值是這兩個數的和，于是區間連續兩個都是 \(0\) 的數的個數等于區間虛點 \(0\) 的個數。

   分別維護原序列和虛點即可。

稍微擴展一下也是容易的，考慮：區間加（任意時刻序列中的值 \(\ge 0\)），區間值不為 \(0\) 的極長連續段數。

2 直接就可以做，1 發現其標記永久化的意義是保證其兒子的值是對的，并且標記始終在其能在的最上層（為了保證查詢當前節點時一定有標記），其實是可以推標記的，考慮兩個兒子標記如何合并到其父親，本質上是取 min，但是需要維護節點信息，考慮每個節點維護一下其沒有標記時的信息（大概是段數、左右端點是否有值），加上一些分討還是可以向上傳遞的。

上樹也是直接上，就是有不少細節。