https://vjudge.net/contest/161102

?

HDU - 2795

題意：模擬一個(gè)過(guò)程，有n行，每行初始長(zhǎng)m，每次選擇最靠前的長(zhǎng)度超過(guò)ai的行減去ai，輸出每次選中哪些行。

線段樹(shù)維護(hù)區(qū)間最大值，然后再線段樹(shù)上二分找第一個(gè)長(zhǎng)度超過(guò)ai的點(diǎn)，單點(diǎn)修改。

?

POJ - 2828

題意：每次在第ai后加入一個(gè)數(shù)bi，求最終的數(shù)組狀態(tài)

維護(hù)序列的題，顯然可以用splay,然后這題會(huì)卡splay，所以用線段樹(shù)模擬這個(gè)過(guò)程，首先，如果是倒序處理的，那在第ai插入相當(dāng)于在當(dāng)前第ai個(gè)空插入，所以還是在線段樹(shù)上二分找這個(gè)空。

?

HDU - 1698

區(qū)間修改

打lazy

?

POJ - 3468

區(qū)間修改區(qū)間查詢

?

POJ - 2528

題意：按照順序給n個(gè)區(qū)間，問(wèn)可以看到幾個(gè)區(qū)間

這題我當(dāng)時(shí)不會(huì)，現(xiàn)在再回想還是不會(huì)……

然而居然……就是在做完線段樹(shù)后，遍歷一遍線段樹(shù)！然后就可以統(tǒng)計(jì)了！所以對(duì)于線段樹(shù)，并不是所有算法都是在線噠，處理好再遍歷一遍這種想法要記住啊！

?

POJ - 3667

支持兩種操作：1）找一個(gè)連續(xù)的大于k的區(qū)間，并占用它。2）釋放掉一個(gè)指定區(qū)間。

線段樹(shù)維護(hù)區(qū)間連續(xù)性，打lazy，記錄lmax,rmax，mmax，依然是線段樹(shù)上二分找這個(gè)區(qū)間

?

HDU - 1828

矩形周長(zhǎng)并。

寫(xiě)法就是每次加入或減少一條線段的時(shí)候記錄一下改變量，不過(guò)要記住就是先+線段再減線段。

轉(zhuǎn)載于:https://www.cnblogs.com/Macaulish/p/6896098.html

總結(jié)

以上是生活随笔為你收集整理的【给自己的小练习2-线段树】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。