线段树节点存两个域： 1. 该区间内的最大brightest和 2.恰好为该区间长度的brightest和
排序已经保证了到右边界时会先减然后才会加（也就是处理了边界——边上的星星不可以加——只加左不加右）。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 30010;

typedef long long llg;

struct node
{
    llg x, y, c;
}p[N<<2];

struct TreeNode
{
    llg sum, max;
}tree[N<<5];

llg n, w, h, limit;
llg py[N<<2];

bool cmp(node a, node b)
{
    if(a.x == b.x)
        return  a.c < b.c;
    else
        return  a.x < b.x;
}

llg getpos(llg key)
{
    llg l, r, mid;
    l = 1;
    r = limit;
    while(l <= r)
    {
        mid = (l+r) >> 1;
        if(py[mid] == key)  return  mid;
        else  if(py[mid] > key)  r = mid-1;
        else  l = mid+1;
    }
    return  -1;
}

void BuildTree(llg u, llg l, llg r)
{
    llg tmp = u<<1, mid = (l+r)>>1;
    tree[u].max = tree[u].sum = 0;
    if(l+1 == r)  return;
    BuildTree(tmp, l, mid);
    BuildTree(tmp+1, mid, r);
}

void Insert(llg u, llg l, llg r, llg a, llg b, const llg &c)
{
    llg tmp = u<<1, mid = (l+r)>>1;
    if(l==a && r==b)
    {
        tree[u].sum += c;
        tree[u].max = max(tree[tmp].max, tree[tmp+1].max) + tree[u].sum;
        return;
    }
    else
    {
        if(b <= mid)  Insert(tmp, l, mid, a, b, c);
        else  if(a >= mid)  Insert(tmp+1, mid, r, a, b, c);
        else
        {
            Insert(tmp, l, mid, a, mid, c);
            Insert(tmp+1, mid, r, mid, r, c);
        }
        tree[u].max = max(tree[tmp].max, tree[tmp+1].max)+tree[u].sum;
    }
}

int main()
{
    llg i, ans;
    while(scanf("%lld%lld%lld", &n, &w, &h) != EOF)
    {
        memset(tree, 0, sizeof(tree)); //equal to build tree
        for(i = 1; i <= n; i++)
        {
            scanf("%lld%lld%lld", &p[i].x, &p[i].y, &p[i].c);
            p[i+n].x = p[i].x+w;
            p[i+n].y = p[i].y;
            p[i+n].c = -p[i].c;
            py[i] = p[i].y;
            py[i+n] = p[i].y+h;
        }
        if(!n)
        {
            printf("0\n");
            continue;
        }
        n <<= 1;
        sort(py+1, py+n+1);
        sort(p+1, p+n+1, cmp);
        limit = 1;
        for(i = 2; i <= n; i++)
            if(py[i] != py[i-1])
                py[++limit] = py[i];
        ans = 0;
        for(i = 1; i <= n; i++)
        {
            Insert(1, 1, limit, getpos(p[i].y), getpos(p[i].y+h), p[i].c);
            ans = max(ans, tree[1].max);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

• Re:哪位牛可以解释一下这个程序为什么是错的，内附说明。 (163) Moon_1st 2011-05-29 20:19:47