poj(2325)线段树

这里介绍另外一种解法，此题可以用线段树，可以用树状数组

其实这题求的都是下面的和左面的，线段树这种数组结构刚好可以满足，为什么呢？这里稍微解释下吧，也有助于以后的复习

看上面这个图，[1,1]，[2,2]这样的叶节点表示题目的的图中的最下一层，而[4,5],[1,3]这样节点的value值是是其子节点之和，多以可以理解为在二维坐标系中是高于下面的节点的，其子节点都在它的左面，可能说的比较模糊，我也是想一会就明白了

#include<iostream>
#include<fstream>

using namespace std;

struct e{
    int l,r;
    int cn;
}tree[70000];
int level[15001];
int n;
int x[15001],y[15001];
int maxx;

void build(int l,int r,int p)
{
    tree[p].l=l;
    tree[p].r=r;
    tree[p].cn=0;
    if(l<r)
    {
        int mid=(l+r)>>1;
        build(l,mid,p*2);
        build(mid+1,r,p*2+1);
    }
}

void insert(int l,int p)
{
    if(l==tree[p].l&&l==tree[p].r)
    {
        tree[p].cn++;
        return;
    }
    int mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid)
        insert(l,p*2);
    else
        insert(l,p*2+1);
    tree[p].cn++;
}

int find(int l,int r,int p)
{
    if(l==tree[p].l&&r==tree[p].r)
    {
        return tree[p].cn;
    }
    int mid=(tree[p].l+tree[p].r)>>1;
    if(r<=mid)
        return find(l,r,2*p);
    if(l>mid) return find(l,r,2*p+1);
    else
        return find(l,mid,2*p)+find(mid+1,r,2*p+1);
}


void read()
{
//  ifstream cin("in.txt");
    int i,j,k;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
        maxx=max(maxx,x[i]);
    }
    build(0,maxx,1);
    for(i=1;i<=n;i++)
    {
        level[find(0,x[i],1)]++;
        insert(x[i],1);
    }
    for(i=0;i<n;i++)
        cout<<level[i]<<endl;
}

int main()
{
    read();
    return 0;
}

c++的输入输出是不行的，必须要用c的，否则过不了