我要哭了，这题太折磨了。

又是一个单恋的孩子，很有才。然后就写情书。看星星啊，什么希望我俩看到是一颗星星。给出一个w*h的长方形矩形窗框，每个星星有一个权值，问能框住的{zd0}权值是多少。在边上的星星不算内。

黑书有详细讲解。

简单说说我自己做这题的过程吧。

好吧，这题困我好些时间。最开始用传统线段树做，一个结点记录起始点，终结点，此区间的权值。RE了几次，想一想，哇塞，这一存，极限数据，数组要开到2^32。必然RE了。好吧，传统线段树就搁浅了。

用2叉检索树，也就是黑书对应的那一节，每个节点只存星星中存在的一个y值。然后建树，插入操作和维护如黑书所说。

{zh1}一句，框上的点不属于矩形，只要排好序进行插入。不需考虑这点。证明很简单。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Node
{
__int64 x,y;
int w;      
}node[50005];//存点


__int64 ty[200005];//存y坐标，注意除重点。

__int64 tree[205537];//建树


int tn;
int n,num;
int maxt[205537],sum[205537];//存当前节点{zd0}值，和当前节点值。
__int64 w,h;

int cmp1(const void* a,const void* b)
{
return *(__int64*)a>*(__int64*)b?1:-1;  
}//对y坐标排序。

int len,ans;

int cmp(const void* a,const void* b)
{
if(((struct Node*)a)->x==((struct Node*)b)->x)
{
if(((struct Node*)a)->y==((struct Node*)b)->y)
return ((struct Node*)a)->w-((struct Node*)b)->w;
return ((struct Node*)a)->y-((struct Node*)b)->y;
}
return ((struct Node*)a)->x-((struct Node*)b)->x;   
}//对点排序，依次是x y w。

void create(int v,int star,int end)
{
if(v>tn)
tn=v;
int mid=(star+end)>>1;
tree[v]=ty[mid];
if(star<end)
{
if(star<mid)
create(v*2,star,mid);
if(mid<end)
create(v*2+1,mid+1,end);    
}
return ;
}//对y坐标。建树

int max(int a,int b)
{
return a>b?a:b;   
}


void insert(__int64 y,int w,int v)
{
int i,j,temp1,temp2;

for(i=1;tree[i]!=y;)
{
if(tree[i]<y)
i=i*2+1;
else
i=i<<1;                   
}

for(;i;i=i>>1)
{
sum[i]+=w;
j=i*2;
maxt[i]=max(maxt[j],sum[i]-sum[j+1]);
maxt[i]=max(maxt[i],sum[i]-sum[j+1]+maxt[j+1]);          
}
return ;    
}//插入操作。


int main()
{
while(scanf("%d %I64d %I64d",&n,&w,&h)!=EOF)
{
len=0;
ans=0;
tn=0;
len=0;
memset(maxt,0,sizeof(maxt));
memset(sum,0,sizeof(sum));
for(int i=0;i<n;i++)
{
scanf("%I64d %I64d %d",&node[i].x,&node[i].y,&node[i].w);
node[i+n].x=node[i].x+w;
node[i+n].y=node[i].y;
node[i+n].w=-1*node[i].w;     
}
num=n<<1;
for(int i=0;i<n;i++)
{
bool flag1=false;
bool flag2=false;
__int64 hy1=node[i].y;
__int64 hy2=node[i].y+h;
for(int j=0;j<len;j++)
{
if(ty[j]==hy1)
flag1=true;
if(ty[j]==hy2)
flag2=true;
}
if(!flag1)
ty[len++]=hy1;
if(!flag2)
ty[len++]=hy2;
}
qsort(node,num,sizeof(Node),cmp);
qsort(ty,len,sizeof(__int64),cmp1);


create(1,0,len-1);


for(int i=0;i<num;)
{  
__int64 x=node[i].x;
for(;i<num&&node[i].x==x;i++)
{
insert(node[i].y,node[i].w,1);
insert(node[i].y+h,-1*node[i].w,1);  
}
ans=max(ans,maxt[1]);
}
printf("%d\n",ans);


}
return 0;   
}