http://poj.org/problem?id=3277
线段树,离散化,成段更新
#include <stdio.h>
#include <stdlib.h> #define lson l, m, root<<1
#define rson m+1, r, root<<1|1 const long long N = ;
const long long inf = (<<)-; long long max1[N<<], color[N<<]; long long max(long long x, long long y)
{
return x>y? x: y;
} void push_up(long long root)
{
max1[root] = max(max1[root<<], max1[root<<|]);
} void push_down(long long l, long long r, long long root)
{
color[root<<] = max(color[root<<], color[root]);
color[root<<|] = max(color[root<<|], color[root]);
color[root] = -;
max1[root<<] = max(max1[root<<], color[root<<]);
max1[root<<|] = max(max1[root<<|], color[root<<|]);
} void build(long long l, long long r, long long root)
{
long long m;
color[root] = -;
if(l == r)
{
max1[root] = ;
return;
}
m = (l + r) >> ;
build(lson);
build(rson);
push_up(root);
} void update(long long L, long long R, long long x, long long l, long long r, long long root)
{
long long m;
if(L <= l && r <= R)
{
color[root] = max(color[root], x);
max1[root] = max(max1[root], color[root]);
return;
}
m = (l + r) >> ;
if(color[root] != -)
{
push_down(l, r, root);
}
if(L <= m)
{
update(L, R, x, lson);
}
if(m+ <= R)
{
update(L, R, x, rson);
}
push_up(root);
} long long query(long long L, long long R, long long l, long long r, long long root)
{
long long m, result = ;
if(L <= l && r <= R)
{
return max1[root];
}
m = (l + r) >> ;
if(color[root] != -)
{
push_down(l, r, root);
}
if(L <= m)
{
result = max(result, query(L, R, lson));
}
if(m+ <= R)
{
result = max(result, query(L, R, rson));
}
push_up(root);
return result;
} struct B
{
long long x, y;
long long h;
}b[N>>]; long long a[N], hash[N]; long long bs(long long l, long long r, long long x)
{
long long m;
while(l < r)
{
m = (l + r) >> ;
if(hash[m] == x)
{
return m;
}
if(hash[m] < x)
{
l = m + ;
}
else
{
r = m;
}
}
} int cmp0(const void *a, const void *b)
{
return *(long long *)a - *(long long *)b;
} int main()
{
long long n, i, j, temp, result = ;
long long k;
scanf("%lld", &n);
for(i=; i<=n; i++)
{
scanf("%lld%lld%lld", &b[i].x, &b[i].y, &b[i].h);
a[(i-)*+] = b[i].x;
a[(i-)*+] = b[i].y;
}
qsort(a+, *n, sizeof(a[]), cmp0);
j = ;
hash[j] = a[];
for(i=; i<=*n; i++)
{
if(a[i] != a[i-])
{
j = j + ;
hash[j] = a[i];
}
}
// for(i=1; i<=j; i++)
// {
// printf("%5d", i);
// }
// printf("\n");
// for(i=1; i<=j; i++)
// {
// printf("%5d", hash[i]);
// }
// printf("\n");
build(, j-, );
for(i=; i<=n; i++)
{
// printf("update %lld %lld %lld\n", bs(1, j+1, b[i].x), bs(1, j+1, b[i].y)-1, b[i].h);
update(bs(, j+, b[i].x), bs(, j+, b[i].y)-, b[i].h, , j, );
// for(k=1; k<=j-1; k++)
// {
// printf("%4d", k);
// }
// printf("\n");
// for(k=1; k<=j-1; k++)
// {
// temp = query(k, k, 1, j, 1);
// result += (temp * (hash[k+1]-hash[k]));
// printf("%4d", temp);
// }
// printf("\n");
}
result = ;
for(i=; i<=j-; i++)
{
temp = query(i, i, , j, );
result += (temp * (hash[i+]-hash[i]));
// printf("%lld %lld %lld\n", i, temp, hash[i+1]-hash[i]);
}
printf("%lld\n", result);
return ;
}