CF896E Welcome home, Chtholly

對于給定一個長度為n(n<=1e5)的序列，值域范圍為1e5,要求支持兩類操作。

將區間[l,r]內所有大于x的數減x

查詢區間[l,r]內值為x的數的個數

首先由于n和值域同階，所以我們應該在值域上進行操作，但是這個東西不好用線段樹的結構維護，因為它的修改比較獨特，我們難以標記下傳的方式處理。

但是我們可以使用分塊暴力處理，然后因為操作一的復雜度與值域有關，我們可以看出來，因為只有減操作，所以最大值一定是單調遞減的，然后我們可以做到維護值域然后復雜度就可以做到O(n*\sqrt(n))，所以我們要盡量調整塊的個數盡量少，所以就不能使用線段樹這樣的分治結構了。

然后我們考慮復雜度，當x2<=mx的時候我們可以讓塊整體左移，相當于0點右移，然后只用處理O(x)的值域即可，當x2>mx時，我么可以處理O(mx-x)的值域，然后整體就是用O(x)的復雜度使得最大值減少了O(x)，所以復雜度是正確的。
然后對于零散塊，個數不超過O(\sqrt(n))所以可以暴力重構。

然后我們考慮一種數據結構可以做到O(1)合并，O(1)查詢大小，顯然可以使用并查集。

然后還有一個trick，就是我們可以單獨考慮每一個塊的貢獻，這樣可以將空間復雜度降低。

這道題維護時移動零點的trick很重要，可以實現O(1)整體移動，然后通過判斷我們就可以做到O(x)處理O(x)

總結

以上是生活随笔為你收集整理的CF896E Welcome home, Chtholly(分块/并查集/第二分块）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。