????(參考https://blog.csdn.net/zearot/article/details/48299459以及Clove_unique的csdn博客)
????線段樹應(yīng)用場(chǎng)景是需要符合區(qū)間加法信息的蚕苇，我就來(lái)做https://blog.csdn.net/zearot/article/details/48299459這篇文章中的幾道題來(lái)試試看吧哩掺。
????主要理清楚要維護(hù)區(qū)間信息，讓區(qū)間信息符合區(qū)間加法的性質(zhì)
零.逆序?qū)?br>
逆序?qū)儆诙S偏序中的特例涩笤，指的是一個(gè)序列a1,a2,a3...aN嚼吞，求出滿足：ai > aj 且 i < j 的個(gè)數(shù)的一系列問(wèn)題。
493. 翻轉(zhuǎn)對(duì)
這也是一道逆序?qū)Φ膯?wèn)題
線段樹常見思想蹬碧，1維排序舱禽，然后第二維進(jìn)行插入，用線段樹進(jìn)行統(tǒng)計(jì)恩沽。
cpp：
java：
一.染色問(wèn)題
hdu1556
code:https://paste.ubuntu.com/p/RSPfvr6Z7t/
詢問(wèn)最后每個(gè)點(diǎn)有幾種顏色
hdu5203
code:https://paste.ubuntu.com/p/t9FSzwtVbC/
詢問(wèn)區(qū)間的顏色
二.基本線段樹題目
1.ural1989
????字符串單點(diǎn)更新誊稚，詢問(wèn)是否有回文串。
????詢問(wèn)是否是回文串罗心，我們需要統(tǒng)計(jì)hash值來(lái)判斷是否回文串里伯。
????區(qū)間信息: 字符串的hash值
code:https://paste.ubuntu.com/p/cpCc36RVFf/
- poj3667
這道題寫了很久，錯(cuò)了很久渤闷，是一道區(qū)間合并的題疾瓮。
尋找最左邊的一個(gè)線段，分3種情況飒箭，可能出現(xiàn)在節(jié)點(diǎn)的左邊狼电，也可能出現(xiàn)在中間或者右邊蜒灰，所以我們需要通過(guò)線段樹維護(hù) 從左邊的最長(zhǎng)和從右邊的最長(zhǎng)，以及區(qū)間最長(zhǎng)3個(gè)值肩碟。
當(dāng)左兒子節(jié)點(diǎn)區(qū)間最長(zhǎng)能滿足的時(shí)候强窖，往左兒子走，在中間的情況削祈，我們需要統(tǒng)計(jì)左兒子的從右邊最長(zhǎng)以及右兒子的左邊最長(zhǎng)翅溺，最次，往右兒子方向走岩瘦。
這道題需要兩種標(biāo)記未巫。
code: https://paste.ubuntu.com/p/YZHHgnRs5S/
3.Codeforces 527C Glass Carving
和上面一道差不多，也是區(qū)間合并的問(wèn)題启昧，更簡(jiǎn)單些叙凡，是單點(diǎn)更新，統(tǒng)計(jì)有多少個(gè)連續(xù)的0(不妨設(shè)),還是分為三部分來(lái)處理密末，使用兩個(gè)線段樹來(lái)統(tǒng)計(jì)最后結(jié)果是(sx[1][0]+1)*(sx[1][1]+1)
code:https://paste.ubuntu.com/p/M7kKzSM6TN/
4.hdu3016 Man Down
5.Codeforces 558E A Simple Task
6.hdu2795
