[POJ 2482] | Eurce's Blog

这题前面竟然是一封情信，字里行间都饱含作者的深情……于是又搜了下kinfkong，是位中大的前辈哦，都31岁结婚了。他博客里的文章也挺有意思的……

扯远了，回到题目本身吧。题面是：在二维平面上有N颗星星，各有一个亮度值c，问如果用一个长W宽H的矩形来括住某些星星，如何使窗口内星星亮度和最大。

说实在的，题目本身也出得非常巧妙。解题需要两次利用区间值求和的思想，即在[a,b]区间上加c，相当于在顺序遍历的基础上在a点加c，b+1点减c。第一次是在y轴方向上，若在(x,y)点处有一颗星星亮度为c，则在(x,y+H)上增加一颗亮度为-c的星星。这样，由y=0向上更新线段亮度值，便能将矩形区域求最大和转换成线段求最大和。第二次则是在x轴方向上的，对横坐标x亮度为c的星星，增加一颗x+W处亮度为-c的星星，这样便能进一步将线段最大和转换成点最大值。由此，便能利用线段树在每次插入星星的同时O(lgN)地更新最大亮度值了。

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

#define LL long long

LL n,W,H,sl,ml,mx,w[10000],wl;

struct star
{
	LL w,h,c;
	bool operator < (const star &p) const
	{
		if(h==p.h&&w==p.w) return c<p.c;
		if(h==p.h) return w<p.w;
		return h<p.h;
	}
}s[20001];

struct node
{
	LL sm,ld,rd,mx;
	bool b;
	node *l,*r;
}mem[1000000],*root;

void ins(LL i,LL e,LL L,LL R,node *p)
{
	if(L==R)
	{
		e+=p->sm;
		p->sm=p->ld=p->rd=p->mx=e;
		return;
	}
	LL m=L+R>>1;
	if(p->b)
	{
		p->b=0;
		p->l=&mem[ml++];
		p->l->b=1;
		p->l->sm=p->l->ld=p->l->rd=p->l->mx=0;
		p->r=&mem[ml++];
		p->r->b=1;
		p->r->sm=p->r->ld=p->r->rd=p->r->mx=0;
	}
	if(i<=m) ins(i,e,L,m,p->l);
	else ins(i,e,m+1,R,p->r);
	p->sm=p->l->sm+p->r->sm;
	p->ld=p->l->ld>p->l->sm+p->r->ld?p->l->ld:p->l->sm+p->r->ld;
	p->rd=p->r->rd>p->r->sm+p->l->rd?p->r->rd:p->r->sm+p->l->rd;
	p->mx=p->l->mx>p->r->mx?p->l->mx:p->r->mx;
	p->mx=p->mx>p->l->rd+p->r->ld?p->mx:p->l->rd+p->r->ld;
}

int main()
{
	LL i,j,k,L,R;
	while(~scanf("%lld%lld%lld",&n,&W,&H))
	{
		ml=sl=mx=wl=0;
		L=0x7fffffff;
		R=0;
		root=&mem[ml++];
		root->sm=root->ld=root->rd=root->mx=0;
		root->b=1;
		while(n--)
		{
			scanf("%lld%lld%lld",&i,&j,&k);
			w[wl++]=i;
			L=i<L?i:L;
			R=(i+W)>R?(i+W):R;
			s[sl].w=i; s[sl].h=j; s[sl].c=k;
			sl++;
			s[sl].w=i; s[sl].h=j+H; s[sl].c=-k;
			sl++;
		}
		sort(s,s+sl);
		sort(w,w+wl);
		for(i=j=1;i<wl;i++)
			if(w[i]!=w[j-1]) w[j++]=w[i];
		wl=j;
		for(i=0;i<sl;i++)
		{
			ins(s[i].w,s[i].c,L,R,root);
			ins(s[i].w+W,-s[i].c,L,R,root);
			mx=root->mx>mx?root->mx:mx;
		}
		printf("%lld\n",mx);
	}
	return 0;
}

#include<cstdio>

#include<algorithm>

using namespace std;

#define LL long long

LL n,W,H,sl,ml,mx,w[10000],wl;

struct star

{

LL w,h,c;

bool operator < (const star &p) const

{

if(h==p.h&&w==p.w) return c<p.c;

if(h==p.h) return w<p.w;

return h<p.h;

}

}s[20001];

struct node

{

LL sm,ld,rd,mx;

bool b;

node *l,*r;

}mem[1000000],*root;

void ins(LL i,LL e,LL L,LL R,node *p)

{

if(L==R)

{

e+=p->sm;

p->sm=p->ld=p->rd=p->mx=e;

return;

}

LL m=L+R>>1;

if(p->b)

{

p->b=0;

p->l=&mem[ml++];

p->l->b=1;

p->l->sm=p->l->ld=p->l->rd=p->l->mx=0;

p->r=&mem[ml++];

p->r->b=1;

p->r->sm=p->r->ld=p->r->rd=p->r->mx=0;

}

if(i<=m) ins(i,e,L,m,p->l);

else ins(i,e,m+1,R,p->r);

p->sm=p->l->sm+p->r->sm;

p->ld=p->l->ld>p->l->sm+p->r->ld?p->l->ld:p->l->sm+p->r->ld;

p->rd=p->r->rd>p->r->sm+p->l->rd?p->r->rd:p->r->sm+p->l->rd;

p->mx=p->l->mx>p->r->mx?p->l->mx:p->r->mx;

p->mx=p->mx>p->l->rd+p->r->ld?p->mx:p->l->rd+p->r->ld;

}

int main()

{

LL i,j,k,L,R;

while(~scanf("%lld%lld%lld",&n,&W,&H))

{

ml=sl=mx=wl=0;

L=0x7fffffff;

R=0;

root=&mem[ml++];

root->sm=root->ld=root->rd=root->mx=0;

root->b=1;

while(n--)

{

scanf("%lld%lld%lld",&i,&j,&k);

w[wl++]=i;

L=i<L?i:L;

R=(i+W)>R?(i+W):R;

s[sl].w=i; s[sl].h=j; s[sl].c=k;

sl++;

s[sl].w=i; s[sl].h=j+H; s[sl].c=-k;

sl++;

}

sort(s,s+sl);

sort(w,w+wl);

for(i=j=1;i<wl;i++)

if(w[i]!=w[j-1]) w[j++]=w[i];

wl=j;

for(i=0;i<sl;i++)

{

ins(s[i].w,s[i].c,L,R,root);

ins(s[i].w+W,-s[i].c,L,R,root);

mx=root->mx>mx?root->mx:mx;

}

printf("%lld\n",mx);

}

return 0;

}

不过题目分类里写得这题属于“静态二叉检索树”。。。。这个暂时还没想出来该怎么写。。。