poj 2352 第一道树状数组和线段树
poj 3277 线段树,离散化,扫描线

hdu 1823 二维线段树

scturtle posted @ 2010年12月01日 03:08 in algorithm , 3385 阅读

题意很明确,貌似主要就是用来测模板的....写的这个二维线段树虽然很长很罗嗦,但还是geilivable的啊,只不过用c++才能过

#include <cstdio>

typedef struct { int l,r; double val; } node1;
double max(double a,double b){return a>b?a:b;};
void swap(double &a,double &b) { double t=a;a=b;b=t; }
struct tree1
{
    node1 node[3000];
    void build(int l,int r,int root)
    {
        node[root].l=l;node[root].r=r;
        node[root].val=-1;
        if(l==r) return;
        int m=(l+r)/2;
        build(l,m,2*root);
        build(m+1,r,2*root+1);
    }
    void update(int x,double val,int root)
    {
        if(node[root].val<val)
            node[root].val=val;
        if(node[root].l == node[root].r)
            return;
        int m=(node[root].l+node[root].r)/2;
        if(x<=m) update(x,val,2*root);
        else update(x,val,2*root+1);
    }
    double query(int l,int r,int root)
    {
        if(node[root].l==l && node[root].r==r)
            return node[root].val;
        int m=(node[root].l+node[root].r)/2;
        if(r<=m) return query(l,r,root*2);
        else if(l>m) return query(l,r,root*2+1);
        else
            return max(query(l,m,root*2),
                    query(m+1,r,root*2+1));
    }
};
typedef struct {int l,r;tree1 tree; } node2;
struct tree2
{
    node2 node[300];
    void build(int xmin,int xmax,int ymin,int ymax,int root)
    {
        node[root].l=xmin;node[root].r=xmax;
        node[root].tree.build(ymin,ymax,1);
        if(xmin==xmax) return;
        int m=(xmin+xmax)/2;
        build(xmin,m,ymin,ymax,2*root);
        build(m+1,xmax,ymin,ymax,2*root+1);
    }
    void update(int x,int y,double val,int root)
    {
        node[root].tree.update(y,val,1);
        if(node[root].l==node[root].r)
            return;
        int m=(node[root].l+node[root].r)/2;
        if(x<=m) update(x,y,val,root*2);
        else update(x,y,val,root*2+1);
    }
    double query(int x1,int x2,int y1,int y2,int root)
    {
        if(node[root].l==x1 && node[root].r==x2)
            return node[root].tree.query(y1,y2,1);

        int m=(node[root].l+node[root].r)/2;
        if(x2<=m) return query(x1,x2,y1,y2,2*root);
        else if(x1>m) return query(x1,x2,y1,y2,2*root+1);
        else
            return max(query(x1,m,y1,y2,root*2)
                    ,query(m+1,x2,y1,y2,root*2+1));
    }
};
tree2 tree;
int main()
{   
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,h,hh;char s[2];
    double a,aa,l,ans;
    while(scanf("%d",&n),n)
    {
        tree.build(100,200,0,1000,1);
        while(n--)
        {
            scanf("%s",s);
            if(s[0]=='I')
            {
                scanf("%d %lf %lf",&h,&a,&l);
                tree.update(h,int(a*10),l,1);
            }
            else
            {
                scanf("%d %d %lf %lf",&h,&hh,&a,&aa);
                if(h>hh) {h^=hh;hh^=h;h^=hh;}
                if(a>aa) swap(a,aa);
                ans=tree.query(h,hh,int(a*10),int(aa*10),1);
                if(ans<0) puts("-1");
                else printf("%.1f\n",ans);
            }
        }
    }
}

 

jnanabhumiap.in 说:
2024年1月18日 19:00

JNANABHUMI AP offers the most recent information on education. The primary idea or goal of this website has been to offer comprehensive resources with information on any subject that can be accessed online. To make sure that every reader finds out what they should know about the subject they are interested in and jnanabhumiap.in links to our content.Jnanabhumi AP is a startup founded by enthusiastic bloggers and webmasters who are driven to produce interesting, factual, and well-written content. We are similar to an online community where you can find a variety of resources, information, and topics about newsworthy events or daily occurrences.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter