HDU-3016 Man Down 线段树

http://acm.hdu.edu.cn/showproblem.php?pid=3016

这题是一个游戏题，名曰：是男人就下一百层。就是给定一系列的坐标，首先是纵坐标，然后是线段的左右坐标，最后是在该条线段的增加或者扣除的血量。

解决这题的关键在于如何处理这多条线段的关系，如果是从上而下的话，那么我们能够更新一条边的两个端点下的最优值，那么对于后面加入的边就有下面的动态方程：
　　　　　　sum[f] = max( sum(x),  f.x1 <= x <= f.x2 ) + val(f)
需要在该边的区域内寻找最大值来更新这条边的两个端点值，这样做显然处理起来较麻烦，时间开销也比较大。所以我们应该从下面开始往上面更新，对于最下面的一条边我们能够更新该条边的最优值，而对于上面的边，我们只要查找其左右两个端点的最优值来更新该条边即可。
　　　　　　sum[f] = max( sum(x1), sum(x2) ) + val(f)

代码如下：

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100000
using namespace std;

struct
{
int l, r, val, cover;
}seg[MAXN*3];

struct Node
{
int x1, x2, y, val;
bool operator < (Node t) const
    {
return y < t.y;
    }
}e[MAXN];

void creat(int f, int l, int r)
{
int mid = (l+r)>>1;
    seg[f].l = l, seg[f].r = r;
    seg[f].val = 0, seg[f].cover = 0;
if (r > l)
    {
        creat(f<<1, l, mid);
        creat(f<<1|1, mid+1, r);
    }
}

void init()
{
    creat(1, 1, MAXN);
    seg[1].cover = 1, seg[1].val = 100;
}

int query(int f, int pos)
{
int mid = (seg[f].l+seg[f].r)>>1; 
if (seg[f].cover == 1)
    {
return seg[f].val;
    }
if (pos <= mid)
return query(f<<1, pos);
else
return query(f<<1|1, pos);
}

void modify(int f, int l, int r, int val)
{
int mid = (seg[f].l+seg[f].r)>>1;
if (seg[f].l == l && r == seg[f].r)
    {
        seg[f].val = val;
        seg[f].cover = 1;
    }
else if (seg[f].r > seg[f].l)
    {
if (seg[f].cover == 1)
        {
            seg[f<<1].cover = seg[f<<1|1].cover = 1;
            seg[f<<1].val = seg[f<<1|1].val = seg[f].val;
            seg[f].cover = 0;
        }
if (r <= mid)
            modify(f<<1, l, r, val);
else if (l > mid)
            modify(f<<1|1, l, r, val);
else
        {
            modify(f<<1, l, mid, val);
            modify(f<<1|1, mid+1, r, val);
        }
    }
}

int main()
{
int N, x;
while (scanf("%d", &N) == 1)
    {
for (int i = 0; i < N; ++i)
        {
            scanf("%d %d %d %d", &e[i].y, &e[i].x1, &e[i].x2, &e[i].val);
        }
        sort(e, e+N);
        init();
for (int i = 0; i < N; ++i)
        {
            x = max(query(1, e[i].x1), query(1, e[i].x2));
            modify(1, e[i].x1, e[i].x2, x+e[i].val);
        } 
        x = max(query(1, e[N-1].x1), query(1, e[N-1].x2));
        printf(x >= 0 ? "%d\n" : "-1\n", x);
    }
return 0;
}