zhangxyhp

摘要： 首先將枚舉原排列中的區(qū)間轉(zhuǎn)化為枚舉值域上的區(qū)間。 從小往大對(duì) \(r\) 掃描線，對(duì)于每個(gè) \(l\in[1,r)\) 維護(hù)將 \([l,r]\) 在原排列中最少要分成多少段。顯然只有 \(1\) 或 \(2\) 段才會(huì)產(chǎn)生貢獻(xiàn)。那么我們用線段樹維護(hù)值域上的每個(gè) \(l\) 的最小段數(shù)，并維護(hù)值域區(qū) 閱讀全文