• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            首先用平衡樹做出來了
            學了一下傳說中SBT,比較好用,編碼不是很難
            能夠寫二叉查找樹就會寫一半了。

            平衡樹只維護當前的區間,然后查找當前區間的
            第K元素。

            所以首先把區間從小到大排序,這樣可以保證每個
            元素只插入一次,刪除也只有一次。
            如樣例。 首先把 1-5  區間元素插入,
            到第二個區間 2-7 時,把 1-2 刪除, 5-7 插入

            SBT插入和刪除都是logn,總復雜度nlogn+ mlogm

            代碼




            另外還用數狀數組做了下

            樹狀數組的做法和以上相似,只是首先要把離散化一
            下, 稍微有些麻煩。插入相當于在樹狀數據對應元素
            增加 1, 刪除相當于增加 -1, 查找每 k 元素,相
            當于找到 sum 等于 k的最小元素,這個可以二分sum
            去求, 總復雜度為 mlogm+ nlognlogn。

            不過好像求第k元素有一個 nlogn 的做法, 沒學會
            還得去看看。


            代碼


            這題還可以用其它數據結構做出
            確實是一道練習數據結構的好題啊

            posted on 2009-04-12 18:38 Darren 閱讀(372) 評論(0)  編輯 收藏 引用
            欧美日韩精品久久久久| 人人狠狠综合久久亚洲婷婷| 亚洲国产成人乱码精品女人久久久不卡 | 思思久久99热只有频精品66| 久久精品卫校国产小美女| 亚洲色欲久久久综合网东京热 | 国产成人精品久久一区二区三区| 久久―日本道色综合久久| 人妻中文久久久久| 久久精品www人人爽人人| 久久国产精品二国产精品| 色8久久人人97超碰香蕉987| 精品久久久久一区二区三区| 久久国产亚洲精品无码| 亚洲欧美久久久久9999| 国产一久久香蕉国产线看观看| 久久乐国产综合亚洲精品| 成人a毛片久久免费播放| 久久亚洲精精品中文字幕| 亚洲国产精品无码久久九九| 国产一区二区三区久久精品| 久久综合色老色| 欧美大战日韩91综合一区婷婷久久青草 | 久久电影网| 青草影院天堂男人久久| 久久综合给合久久狠狠狠97色| 少妇久久久久久被弄到高潮| 国产ww久久久久久久久久| 久久A级毛片免费观看| 亚洲香蕉网久久综合影视| 久久亚洲精品无码aⅴ大香 | 久久久久婷婷| 久久国产高清一区二区三区| 国产精品九九久久精品女同亚洲欧美日韩综合区 | 精品99久久aaa一级毛片| 伊人久久免费视频| 97精品国产91久久久久久| 久久精品aⅴ无码中文字字幕不卡 久久精品aⅴ无码中文字字幕重口 | 久久久黄片| 无码人妻少妇久久中文字幕| 亚洲AV伊人久久青青草原|