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

            2010 ICPC天津賽區 J hdu 3727 劃分樹的理解

            很久不寫劃分樹了,果然各種NC錯誤
            按照我的理解,劃分樹即一個線段樹(用來確定數組下標和層次)以及一個log2(n)*n的數組,來記錄劃分信息
            這題實現4個操作:
            1、插入
            按照劃分樹的定義,如果小于有序表中中間節點的值,就遞歸插入左子樹,否則遞歸插入右子樹。更新當前區間段的劃分信息(無非就是往后計算一個)
            2、詢問s,e區間第k小數
            查詢s,e區間里面劃分到左子樹的個數i,如果i>=k,那么顯然遞歸到左子樹查詢,否則就是遞歸到右子樹查詢k-i小的數。注意!這里要重新定位左子樹和右子樹中的區間,由于是閉區間,那么做端點為s+sum(s-1),右端點為s+sum(e)-1,這個減一丟了。。調了我半天。。哎。。以前寫都是左閉右開區間的,結果習慣了。。
            3、查詢值為k的數的位次
            這個需要一個輔助數組,記錄值為k的數插在最頂層區間的哪個位置了。這個辦好后,就容易了,如果數被劃分到了左子樹,那么遞歸查詢左子樹,否則返回遞歸查詢右子樹的值加上當前區間被劃分到左子樹的個數
            4、查詢rank k的數
            同樣是這樣,如果當前區間被劃分到左子樹的個數小于等于k,那么遞歸查詢左子樹,否則遞歸查詢右子樹中rank為k-左子樹的size。
            大概思想就是這樣了,實現有很多細節,比如說假設p==區間左端點(左區間木有數),那么算sum(p-1)的時候就要特判下了。我喜歡用三元式,很方便。

            代碼
            # include <cstdio>
            # include <cstring>
            # include <map>
            using namespace
            std;
            # define N 100005
            int arr[20][N];
            struct
            node
            {

               int
            s,e,layer;
               int
            c;
            }
            st[4*N];
            int
            q[500000][4],c;
            int
            remap[N],position[N];
            map<int,int> refer;
            void
            init(int s,int e,int layer,int pos=1)
            {

                st[pos].s=s;st[pos].e=e;
                st[pos].layer=layer;
                st[pos].c=st[pos].s;
                if
            (s!=e) init(s,(s+e)/2,layer+1,pos<<1),init((s+e)/2+1,e,layer+1,(pos<<1)+1);
            }

            void
            insert(int value,int pos=1)
            {

                 if
            (st[pos].s==st[pos].e)
                    arr[st[pos].layer][st[pos].c++]=value;
                 else

                 {

                     if
            (value<=(st[pos].s+st[pos].e)/2)
                     {

                         arr[st[pos].layer][st[pos].c]=(st[pos].c==st[pos].s?0:arr[st[pos].layer][st[pos].c-1])+1;
                         st[pos].c++;
                         insert(value,pos<<1);
                     }

                     else

                     {

                         arr[st[pos].layer][st[pos].c]=(st[pos].c==st[pos].s?0:arr[st[pos].layer][st[pos].c-1]);
                         st[pos].c++;
                         insert(value,(pos<<1)+1);
                     }
                 }
            }

            int
            q1(int s,int t,int k,int pos=1)
            {

                if
            (st[pos].s==st[pos].e)
                    return
              remap[arr[st[pos].layer][st[pos].s]];
                else

                {

                    if
            (arr[st[pos].layer][t]-(s==st[pos].s?0:arr[st[pos].layer][s-1])>=k)//left
                        return q1(st[pos].s+(s==st[pos].s?0:arr[st[pos].layer][s-1]),st[pos].s+arr[st[pos].layer][t]-1,k,pos<<1);
                    else
            //right
                    {
                        k-=arr[st[pos].layer][t]-(s==st[pos].s?0:arr[st[pos].layer][s-1]);
                        return
            q1((st[pos].s+st[pos].e)/2+1+s-1-st[pos].s+1-(s==st[pos].s?0:arr[st[pos].layer][s-1]),(st[pos].s+st[pos].e)/2+1+t-st[pos].s+1-arr[st[pos].layer][t]-1,k,(pos<<1)+1);
                    }
                }
            }

            int
            q2(int s,int pos=1)
            {

                if
            (st[pos].s==st[pos].e) return 1;
                else if
            (arr[st[pos].layer][s]-(s==st[pos].s?0:arr[st[pos].layer][s-1]))
                  return
            q2(st[pos].s+arr[st[pos].layer][s]-1,pos<<1);
                else
                  return
            (st[pos].c==st[pos].s?0:arr[st[pos].layer][st[pos].c-1])+q2((st[pos].s+st[pos].e)/2+1+s-st[pos].s+1-arr[st[pos].layer][s]-1,(pos<<1)+1);
            }

            int
            q3(int k,int pos=1)
            {

                if
            (st[pos].s==st[pos].e) return remap[arr[st[pos].layer][st[pos].s]];
                else if
            (k<=(st[pos].c==st[pos].s?0:arr[st[pos].layer][st[pos].c-1])) return q3(k,pos<<1);
                else return
            q3(k-(st[pos].s==st[pos].c?0:arr[st[pos].layer][st[pos].c-1]),(pos<<1)+1);
            }

            int
            main()
            {

                int
            n,test=1;
                while
            (scanf("%d",&n)!=EOF)
                {

                   refer.clear();c=1;
                   memset(arr,0,sizeof(arr));
                   for
            (int i=0;i<n;i++)
                   {

                       char
            tmp[12];
                       scanf("%s",tmp);
                       if
            (*tmp=='I')
                         q[i][0]=0;
                       else
            q[i][0]=tmp[6]-48;
                       switch
            (q[i][0])
                       {

                       case
            0:
                            scanf("%d",&q[i][1]);
                            refer[q[i][1]]=0;
                            break
            ;
                       case
            1:
                            scanf("%d%d%d",&q[i][1],&q[i][2],&q[i][3]);
                            break
            ;
                       default
            :
                            scanf("%d",&q[i][1]);
                            break
            ;
                       };
                   }

                   for
            (map<int,int>::iterator i=refer.begin();i!=refer.end();i++)
                     remap[c]=i->first,i->second=c++;
                   init(1,c-1,0);
                   long long
            t[4]={0,0,0,0};
                   int
            now=1;
                   for
            (int i=0;i<n;i++)
                     switch
            (q[i][0])
                     {

                       case
            0:
                            insert(refer[q[i][1]]);
                            position[refer[q[i][1]]]=now++;
                            break
            ;
                       case
            1:
                            t[1]+=q1(q[i][1],q[i][2],q[i][3]);
                            break
            ;
                       case
            2:
                            t[2]+=q2(position[refer[q[i][1]]]);
                            break
            ;
                       case
            3:
                            t[3]+=q3(q[i][1]);
                            break
            ;
                     };

                   printf("Case %d:\n%I64d\n%I64d\n%I64d\n",test++,t[1],t[2],t[3]);
                }

                return
            0;
            }

            posted on 2011-09-30 08:44 yzhw 閱讀(473) 評論(0)  編輯 收藏 引用 所屬分類: data struct

            <2010年10月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            国产成人久久AV免费| 国产精品一区二区久久不卡| 国产成人精品久久亚洲高清不卡 | 综合久久给合久久狠狠狠97色| 99久久免费只有精品国产| 久久99国产精品成人欧美| 日本高清无卡码一区二区久久| 国产成人综合久久精品红| 国产精品久久久亚洲| 精品久久久久久久久久久久久久久| 色天使久久综合网天天 | 久久久久亚洲Av无码专| 青草影院天堂男人久久| 色婷婷久久久SWAG精品| 久久夜色精品国产噜噜噜亚洲AV| 精品久久久久国产免费| 久久久久99精品成人片直播| 人妻无码精品久久亚瑟影视| 秋霞久久国产精品电影院| 久久国产亚洲精品| 久久精品?ⅴ无码中文字幕| 国产激情久久久久久熟女老人 | 久久综合九色综合网站| 无码人妻久久一区二区三区蜜桃| 久久久女人与动物群交毛片| 伊人久久大香线蕉成人| 岛国搬运www久久| 婷婷综合久久中文字幕蜜桃三电影| 久久久久亚洲av成人无码电影| 嫩草影院久久99| 久久久精品国产sm调教网站| 婷婷综合久久中文字幕蜜桃三电影| 久久久久亚洲AV片无码下载蜜桃| 国产精品美女久久久免费| 青青青国产成人久久111网站| 亚洲午夜无码久久久久| 久久久国产99久久国产一| 久久久久99这里有精品10| 久久综合亚洲鲁鲁五月天| 色综合久久天天综线观看| 日本高清无卡码一区二区久久|