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 阅读(438) 评论(0)  编辑 收藏 引用 所属分类: data struct


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年7月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜