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

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久久久99精品成人片三人毛片| 中文字幕久久精品无码| 美女写真久久影院| 99久久国产综合精品成人影院| 国产高清国内精品福利99久久| 91亚洲国产成人久久精品网址| 亚洲国产成人久久综合野外| 亚洲AV无码久久精品色欲| 91精品国产91热久久久久福利| 亚洲欧美日韩精品久久亚洲区| 久久久久无码精品国产| 日本国产精品久久| 69久久精品无码一区二区| 亚洲欧洲中文日韩久久AV乱码| 久久综合亚洲欧美成人| 久久综合九色欧美综合狠狠| 久久综合狠狠综合久久| 久久国产高清一区二区三区| 成人综合伊人五月婷久久| 热综合一本伊人久久精品| 久久福利青草精品资源站免费| 伊色综合久久之综合久久| 99久久精品九九亚洲精品| 无码人妻久久一区二区三区| 久久性精品| 9191精品国产免费久久| 91精品国产综合久久精品| 亚洲精品无码久久久影院相关影片| 久久久久噜噜噜亚洲熟女综合| 国产成人久久精品一区二区三区| 色天使久久综合网天天| 日韩久久久久中文字幕人妻| 国产亚洲成人久久| 91久久精品91久久性色| 久久99亚洲网美利坚合众国| 国产成年无码久久久免费| 精品久久久无码人妻中文字幕| 久久婷婷五月综合97色直播| 国产精品欧美久久久久无广告| 久久久精品免费国产四虎| 久久青青草原综合伊人|