http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=502&problem=3673

感觉是模板题吧。。动态开方便多了,代码短,跑的还挺快的。。

(只贴出与题目有关的代码,宏定义见 GitHub

/* 0.178s */
struct node
{
    int l, r, maxh;
    bool isLeaf;
    node() {}
    node(int l, int r, int h, bool f = true) : l(l), r(r), maxh(h), isLeaf(f) {}
} v[2000005];

#define lo (o << 1)
#define ro ((o << 1) | 1)

inline void D(int o, int x)
{
    v[o].isLeaf = false;
    v[lo] = node(v[o].l, x, v[o].maxh);
    v[ro] = node(x, v[o].r, v[o].maxh); // 动态开节点
}

int U(int o, int l, int r, int h)
{
    Qmax(l, v[o].l), Qmin(r, v[o].r);
    if (l >= r) return 0;
    if (!v[o].isLeaf) return U(lo, l, r, h) + U(ro, l, r, h);
    if (h < v[o].maxh) return 0;
    if (v[o].l < l) return D(o, l), U(o, l, r, h);
    if (v[o].r > r) return D(o, r), U(o, l, r, h);
    v[o].maxh = h;
    return r - l;
}

int main()
{
    int q, sum, l, r, h;
    scanf("%*d");
    while (SI(q), q)
    {
        v[1] = node(1, 100000, 0);
        sum = 0;
        while (q--) SIII(l, r, h), sum += U(1, l, r, h);
        PI(sum);
    }
    return 0;
}

Comments

comments powered by Disqus