day4字符串?dāng)?shù)據(jù)結(jié)構(gòu)選講

1、數(shù)據(jù)結(jié)構(gòu)選講JOHNKRAM自我介紹大家好，我是來(lái)自某不知名小地方的某不知名蒟蒻今天我來(lái)給大家講一點(diǎn)數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列三種操作：插入元素，刪除首元素，查詢首元素棧：后進(jìn)先出，先進(jìn)后出隊(duì)列：先進(jìn)先出，后進(jìn)后出STL中的stack和queue還有雙端隊(duì)列，兩頭皆可插入刪除查詢，STL中的dequeNOIP2004果子合并n堆果子，每次合并兩堆，代價(jià)為新堆的果子數(shù)，直到只剩一堆為止求最小總代價(jià)每次合并最小的兩堆先把果子堆從小到大排序，放入一個(gè)隊(duì)列中，再建一個(gè)空隊(duì)列兩個(gè)隊(duì)列隊(duì)首中的較小值即為整體最小值合并后的果子堆放入第二個(gè)隊(duì)列隊(duì)尾NOIP2016蚯蚓有n條蚯蚓，進(jìn)行m次操作，每次挑最長(zhǎng)的一條蚯蚓，設(shè)長(zhǎng)

2、度為x，切成長(zhǎng)度分別px和x-px的兩條蚯蚓，其他蚯蚓長(zhǎng)度增加q求每次操作切的蚯蚓的長(zhǎng)度和最后每條蚯蚓的長(zhǎng)度與合并果子類似，只是建三個(gè)隊(duì)列，從大到小排序后放入第一個(gè)隊(duì)列三個(gè)隊(duì)列隊(duì)首中的最大值即為整體最大值切完后的蚯蚓分別放入第二個(gè)與第三個(gè)隊(duì)列AHOI2013差異給一個(gè)長(zhǎng)度為n的串，令Ti表示它從第i個(gè)字符開始的后綴求后綴數(shù)組復(fù)習(xí)一下對(duì)于height數(shù)組中每個(gè)元素，求在哪些區(qū)間內(nèi)會(huì)成為最小值前面找第一個(gè)小于等于它的元素，后面找第一個(gè)小于它的元素使用單調(diào)棧即可堆一般是三種操作：插入元素，刪除極值，查詢極值還可以增加其他操作最常用的是STL中的priority_queueNOIP2004果子合并n堆

3、果子，每次合并兩堆，代價(jià)為新堆的果子數(shù)，直到只剩一堆為止求最小總代價(jià)每次合并最小的兩堆直接用堆就行了線段樹STL沒(méi)有了一種分治結(jié)構(gòu)的樹，每個(gè)結(jié)點(diǎn)代表一段區(qū)間左右孩子的區(qū)間的并等于父親區(qū)間，交為空集，長(zhǎng)度之差最大為1要求維護(hù)的信息有可加性建樹時(shí)將信息一層層合并上來(lái)支持單點(diǎn)修改信息可以查詢區(qū)間信息，轉(zhuǎn)化為查詢O(logn)個(gè)結(jié)點(diǎn)上的信息懶標(biāo)記區(qū)間修改怎么辦？使用懶標(biāo)記，修改時(shí)只修改父親信息并給父親打上懶標(biāo)記，不修改孩子信息準(zhǔn)備訪問(wèn)孩子時(shí)將懶標(biāo)記下傳并相應(yīng)修改信息要求懶標(biāo)記可以合并懶標(biāo)記無(wú)法解決的操作萬(wàn)事大吉了？顯然沒(méi)有也有不少操作懶標(biāo)記無(wú)法解決這時(shí)候就需要均攤分析了均攤分析區(qū)間開方并下取整，區(qū)間求和顯然每個(gè)數(shù)開O(logloga)次方就變成