学步园

 这里主要想区别一下线段树和点数的区别：

比如区间［0，7］，点数的划分如下：

[0,7]->[0,3]->[4,7]->...->［0,0],[1,1],[2,2]...[7,7]，叶子节点是单个的点。

创建代码如下：

void build(int l,int r,int root)
{
        tree[root].l=l;
        tree[root].r= r;
        tree[root].cn=0;

        if(l==r)//叶子节点结束标志
                return;
        int mid=(l+r)>>1;
        build(l,mid,2*root);
        build(mid+1,r,2*root+1);
}

线段树划分如下：

[0,7]->[0,3]->[3,7]->...->［0,2],[1,2],[2,3]...[6,7]，叶子节点是长度为一的线段。

创建代码如下：

void build(int l,int r,int root)
{
        tree[root].l=l;
        tree[root].r= r;
        tree[root].cn=0;

        if(l+1==r)//线段长度唯一时结束（叶子节点）
                return;
        int mid=(l+r)>>1;
        build(l,mid,2*root);
        build(mid,r,2*root+1);
}

本题使用线段树的特殊情况：点树解决。

#include <iostream><br /> using namespace std;<br /> struct node<br /> {<br /> int l,r;<br /> int cn;<br /> }tree[3200*100];<br /> int level[15010];<br /> int p[15010][2];<br /> void build(int l,int r,int root)<br /> {<br /> tree[root].l=l;<br /> tree[root].r= r;<br /> tree[root].cn=0;<br /> if(l==r)<br /> return;<br /> int mid=(l+r)>>1;<br /> build(l,mid,2*root);<br /> build(mid+1,r,2*root+1);<br /> }<br /> void insert(int r,int p)<br /> {<br /> if(tree[p].l==r && tree[p].r ==r)<br /> {<br /> tree[p].cn++;<br /> return;<br /> }<br /> int mid = (tree[p].l+tree[p].r)>>1;<br /> if(r<=mid)<br /> insert(r,2*p);<br /> else<br /> insert(r,2*p+1);<br /> tree[p].cn=tree[p*2].cn+tree[p*2+1].cn;<br /> }<br /> int find(int l,int r,int p)<br /> {<br /> if(l==tree[p].l && r==tree[p].r)<br /> {<br /> return tree[p].cn;<br /> }<br /> else<br /> {<br /> int mid = (tree[p].l+tree[p].r)>>1;<br /> if(r<=mid)<br /> return find(l,r,2*p);<br /> else if(l>mid)<br /> return find(l,r,2*p+1);<br /> else<br /> return find(l,mid,2*p)+find(mid+1,r,2*p+1);<br /> }<br /> }<br /> int main()<br /> {<br /> int n;<br /> scanf("%d",&n);<br /> int i = 0;<br /> int max_v=0;<br /> for(i=0;i<n;i++)<br /> {<br /> scanf("%d %d",&p[i][0],&p[i][1]);<br /> if(max_v < p[i][0])<br /> max_v = p[i][0];<br /> }<br /> build(0,max_v,1);<br /> for(i=0;i<n;i++)<br /> {<br /> level[find(0,p[i][0],1)]++;<br /> insert(p[i][0],1);<br /> }<br /> for(i=0;i<n;i++)<br /> printf("%d/n",level[i]);<br /> }<br />