易错点:
- 线段树数组需要开四倍.
- 离散化星星后在重载运算符时需要以x(x坐标)为第一关键字,c(亮度)为第二关键字.
- 每组数据都需要init()(初始化).
- 在这类一个星星需要分成两个的题中,需要在读取完数据后进行n*=2(避免细节错误).
注意点:
- 在luogu测试会REre三个点,将线段树建树时的范围增大即可.
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=4e4,root=1;
struct Node{
int l,r;
int lazy,maxx;
void reset(){
l=r=lazy=maxx=0;
}
}tr[MAXN*4];
void build(int p,int l,int r){
tr[p].reset();
tr[p].l=l,tr[p].r=r;
if(l==r)return;
int mid=(l+r)>>1;
if(l<=mid)build(p<<1,l,mid);
if(r>mid)build((p<<1)|1,mid+1,r);
}
void change(int p,int l,int r,int val){
if(tr[p].l>=l&&tr[p].r<=r){
tr[p].lazy+=val;
tr[p].maxx+=val;
return;
}
if(tr[p].lazy){
tr[p<<1].lazy+=tr[p].lazy;
tr[p<<1].maxx+=tr[p].lazy;
tr[(p<<1)|1].lazy+=tr[p].lazy;
tr[(p<<1)|1].maxx+=tr[p].lazy;
tr[p].lazy=0;
}
int mid=(tr[p].l+tr[p].r)>>1;
if(l<=mid)change(p<<1,l,r,val);
if(r>mid)change((p<<1)|1,l,r,val);
tr[p].maxx=max(tr[p<<1].maxx,tr[(p<<1)|1].maxx);
}
struct Star{
int x;//横轴坐标
int l,r;//y1 y2位置
int c;//亮度
bool operator <(Star another)const{
return x==another.x?c<another.c:x<another.x;
}
}stars[MAXN];
int b[MAXN],yCnt=0;//y坐标离散化
void init(){
memset(b,0,sizeof(b));
yCnt=0;
}
int main(){
int n,w,h;
while(cin>>n>>w>>h){
init();
for(int i=1;i<=n;i++){
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
stars[i].x=x,stars[i+n].x=x+w;
stars[i].l=stars[i+n].l=y;
stars[i].r=stars[i+n].r=y+h-1;
stars[i].c=c,stars[i+n].c=-c;
b[++yCnt]=y,b[++yCnt]=y+h-1;
}
//离散化
sort(b+1,b+yCnt+1);
int bCnt=unique(b+1,b+yCnt+1)-(b+1);//去重
n=2*n;
for(int i=1;i<=n;i++){
stars[i].l=lower_bound(b+1,b+yCnt+1,stars[i].l)-b;
stars[i].r=lower_bound(b+1,b+yCnt+1,stars[i].r)-b;
}
sort(stars+1,stars+n+1);
build(root,1,bCnt);
int ans=0;
for(int i=1;i<=n;i++){
change(root,stars[i].l,stars[i].r,stars[i].c);
ans=max(ans,tr[root].maxx);
}
printf("%d\n",ans);
}
return 0;
}