• <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>

            RMQ問(wèn)題ST算法 POJ 3264

            ST算法O(nlogn)預(yù)處理,O(1)的查詢指定區(qū)間的最值(以最小值為例)

            基本上是把待求區(qū)間[l,r]分為兩段長(zhǎng)為len的區(qū)間

            左邊一段為[l,l+len-1],右邊一段為[r-len+1,r]

            len必須使得兩段區(qū)間覆蓋待求區(qū)間

            設(shè)所求數(shù)組為w

            那么,所求最小值就是兩個(gè)區(qū)間的最小值間的最小值

            即min(min{w[i],l<=i<=l+len-1},min{w[j],r-len+1<=j<=r})

            若都在預(yù)先處理中先求得兩個(gè)區(qū)間的最小值

            則每次查詢的復(fù)雜度都是O(1)

            ---

            對(duì)len做一個(gè)限制:只能為2的冪

            在預(yù)處理中求出所有mi[b][t] : 以b為起點(diǎn),長(zhǎng)為2^t的區(qū)間的最小值.

            則求解min(min{w[i],l<=i<=l+len-1},min{w[j],r-len+1<=j<=r})

            就變成min(mi[l][t],mi[r-2^t+1][r]),其中t可以由此得出,以保證兩段區(qū)間可以覆蓋待求區(qū)間:

            t=ln(r-l+1)/ln(2)

            ---

            可以看到mi[b][t]=min(mi[b][t-1],mi[b+2^(t-1)-1][t-1])

            特別地對(duì)于所有mi[i][0],其值都是w[i];

            由此自底向上推出所有的mi[b][t]

            mi大小為n*logn,預(yù)處理時(shí)間復(fù)雜度為O(nlogn),查詢時(shí)間復(fù)雜度為O(1)


            #include <iostream>
            ?#include <math.h>
            ?#define max(a,b) ((a>b)?a:b)
            ?#define min(a,b) (a<b?a:b)
            ?
            using namespace std;
            ?
            const int maxn=50001;
            ?int h[maxn];
            ?int mx[maxn][16],mn[maxn][16];
            int n,q;
            ?
            ?void rmq_init()
            ?{
            ???? int i,j;
            ???? for(j=1;j<=n;j++) mx[j][0]=mn[j][0]=h[j];
            ???? int m=floor(log((double)n)/log(2.0));
            ???? for(i=1;i<=m;i++){
            ???????? for(j=n;j>0;j--){
            ???????????? mx[j][i]=mx[j][i-1];
            ???????????? if(j+(1<<(i-1))<=n) mx[j][i]=max(mx[j][i],mx[j+(1<<(i-1))][i-1]);
            ???????? }
            ??? }
            ??? for(i=1;i<=m;i++){
            ???????? for(j=n;j>0;j--){
            ??????????? mn[j][i]=mn[j][i-1];
            ???????????? if(j+(1<<(i-1))<=n) mn[j][i]=min(mn[j][i],mn[j+(1<<(i-1))][i-1]);
            ???????? }
            ???? }
            ?}
            ?
            ?int rmq(int l,int r)
            ?{
            ???? int m=floor(log((double)(r-l+1))/log(2.0));
            ??? int a=max(mx[l][m],mx[r-(1<<m)+1][m]);
            ???? int b=min(mn[l][m],mn[r-(1<<m)+1][m]);
            ??? return a-b;??
            ?}
            ?
            ?int main()
            ?{
            ???? int i,l,r;
            ???? scanf("%d%d",&n,&q);
            ???? for(i=1;i<=n;i++) scanf("%d",&h[i]);
            ???? rmq_init();
            ???? for(i=0;i<q;i++){
            ???????? scanf("%d%d",&l,&r);
            ???????? printf("%d\n",rmq(l,r));
            ???? }

            ?}

            posted on 2008-05-19 20:52 Victordu 閱讀(2569) 評(píng)論(2)  編輯 收藏 引用

            評(píng)論

            # re: RMQ問(wèn)題ST算法 POJ 3264 2008-09-18 19:52 劉劉牛

            "就變成min(mi[l][t],mi[r-2^t+1][r]),其中t可以由此得出,以保證兩段區(qū)間可以覆蓋待求區(qū)間:

            t=ln(r-l+1)/ln(2) "


            是不是有點(diǎn)問(wèn)題呢?


              回復(fù)  更多評(píng)論   

            # re: RMQ問(wèn)題ST算法 POJ 3264 2009-04-11 14:22 Wei Quan Min

            Great.....

            Can u write sth about suffix array + lcp in the next thread....

            I am not really clear about suffix array. Clear about the O(n^2 log n)..
            but I'm curious about O(n log n) which is solved by using lcp..

            Thx  回復(fù)  更多評(píng)論   


            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            導(dǎo)航

            <2007年12月>
            2526272829301
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            統(tǒng)計(jì)

            常用鏈接

            留言簿(5)

            隨筆檔案(46)

            搜索

            積分與排名

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            国内精品久久久久久99| 久久男人中文字幕资源站| 97精品伊人久久大香线蕉app| 一本久久a久久精品亚洲| 日本福利片国产午夜久久| 久久免费99精品国产自在现线| 午夜福利91久久福利| 精品国产乱码久久久久久1区2区| 国产高潮国产高潮久久久91 | 色妞色综合久久夜夜| 精品国产VA久久久久久久冰| 久久久久97国产精华液好用吗| 97久久国产综合精品女不卡| 久久精品无码免费不卡| 97精品伊人久久大香线蕉app| 性做久久久久久久久浪潮| 热久久国产精品| 麻豆一区二区99久久久久| 亚州日韩精品专区久久久| 久久国产精品一区二区| 伊人久久大香线蕉av不卡| 久久艹国产| 久久综合狠狠综合久久激情 | 久久99热这里只频精品6| 丁香五月网久久综合| 久久久无码精品亚洲日韩按摩| 久久综合给合综合久久| 国产2021久久精品| 91超碰碰碰碰久久久久久综合| 人妻精品久久久久中文字幕一冢本| 午夜精品久久影院蜜桃| 久久精品综合一区二区三区| 办公室久久精品| 久久高清一级毛片| 国内精品久久久久久久影视麻豆| 国内精品久久九九国产精品| 色综合久久综合中文综合网| 伊人久久大香线蕉亚洲五月天| 少妇人妻88久久中文字幕| 久久发布国产伦子伦精品| 国产精品久久久久…|