NUAA上次热身赛的题目

自己用线段树写了一遍
还需...

#include <stdio.h>
#include <math.h>
#include <string.h>
 
struct node
{
    int left, right;
    node * pl, * pr;
    int height;
    int hCount;
    int Lheight, Rheight;
}line[80002];

int n;
int lineCount;
int point[80002];
int area;

node * newNode()
{
    node *pt = &line[lineCount++];
    memset(pt,0,sizeof(node));
    return pt;
}

node * makeTree(int ileft, int iright)
{
    node * root=newNode();
    root->left=ileft;
    root->right=iright;
    if(iright-ileft>1)
    {
        int mid=(ileft+iright)/2;
        root->pl=makeTree(ileft,mid);
        root->pr=makeTree(mid,iright);
    }

    return root;
}

void height(node * root, int height)
{
    root->height=height;
    root->Lheight=root->Rheight=height;
}

void update(node * root, int x1, int x2, int h)
{
    if(root->left==x1 && root->right==x2)
    {
        height(root,h);
        return;
    }
    if(root->hCount==1)
    {
        height(root->pl,root->height);
        height(root->pr,root->height);
    }
    root->hCount++;

    if(root->pl->right>x1)
    {
        if(root->pl->right>x2)
            update(root->pl,x1,x2,h);
        else
        {
            int mid=(root->left+root->right)/2;
            update(root->pl,x1,mid,h);
            update(root->pr,mid,x2,h);
        }
    }
    else
    {
        update(root->pr,x1,x2,h);
    }

    root->Lheight=root->pl->Lheight;
    root->Rheight=root->pr->Rheight;
    
}


void count(node * root, int x1, int x2)
{
    if(root->hCount==1)
    {
        area+=(root->right-root->right)*root->height;
        return;
    }
    if(root->right-root->left<=1 || root->hCount==0)
        return;

    if(root->pl->right>x1)
    {
        if(root->pl->right>=x2)
        {
            count(root->pl,x1,x2);
        }
        else
        {
            int mid=(root->left+root->right)/2;
            count(root->pl,x1,mid);
            count(root->pr,mid,x2);
        }
    }
    else
    {
        count(root->pr,x1,x2);
    }

}

int main()
{
    lineCount=0;
    node * root=makeTree(0,8002);
    while(scanf("%d", &n) != EOF && n)
    {
        area=0;
        int x1, x2, h;
        int i;
        for(i=0;i<n;i++)
            line[i].hCount=line[i].height=line[i].Lheight=line[i].Rheight=0;
        for(i=0;i<n;i++)
        {
            scanf("%d%d%d",&x1,&x2,&h);
            update(root,x1,x2,h);
        }
        

        count(root,0,8002);

        printf("%d\n",area);

    }
    return 0;

}