调了快一上午了……求助各位大佬QwQ
对着题解改了改,但是改了半天还是不对。
代码如下(加上了注释):
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 10005
int t_,n,wi,hi,q,lsh[MAXN<<1],tlsh;
struct node{//询问
int l,r,w,a;
node(int l=0,int r=0,int w=0,int s=0)
:l(l),r(r),w(w),a(s){}
}e[MAXN<<1];
struct node1{//线段树
int l,r,maxn,lz;
}t[MAXN<<3];
int read(){//快读
int w=0,f=1;
char c=getchar();
while (c>'9'||c<'0'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0'&&c<='9'){
w=(w<<3)+(w<<1)+(c^48);
c=getchar();
}
return w*f;
}
bool cmp(node x_,node y_){//自定义排序
if (x_.w==y_.w) return x_.a>y_.a;
return x_.w<y_.w;
}
void build(int i,int l,int r){//建树
t[i].l=l,t[i].r=r,t[i].maxn=t[i].lz=0;
if (l==r){
return;
}
int mid=l+r>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
}
void push_down(int i){//下传
if (t[i].lz){
t[i<<1].lz+=t[i].lz;
t[i<<1|1].lz+=t[i].lz;
t[i<<1].maxn+=t[i].lz;
t[i<<1|1].maxn+=t[i].lz;
t[i].lz=0;
}
}
void add(int i,int l,int r,int k){//扫描
if (t[i].l>=l&&t[i].r<=r){
t[i].maxn+=k;
t[i].lz+=k;
return;
}
push_down(i);
if (t[i<<1].r>=l) add(i<<1,l,r,k);
if (t[i<<1|1].l<=r) add(i<<1|1,l,r,k);
t[i].maxn=max(t[i<<1].maxn,t[i<<1|1].maxn);
}
int main(){
t_=read();
while (t_--){
int ans=0;
tlsh=q=0;
n=read(),wi=read()-1,hi=read()-1;
for (int i=1;i<=n;i++){
int x=read(),y=read(),a=read();
e[++q]=node(y,y+hi,x,a);
e[++q]=node(y,y+hi,x+wi,-a);//处理询问
lsh[++tlsh]=y,lsh[++tlsh]=y+hi-1;
}
sort(lsh+1,lsh+1+tlsh);
int g=unique(lsh+1,lsh+1+n)-lsh-1;//离散化
sort(e+1,e+1+q,cmp);//排序
build(1,1,n);
for (int i=1;i<=q;i++){
int l=lower_bound(lsh+1,lsh+1+g,e[i].l)-lsh;
int r=lower_bound(lsh+1,lsh+1+g,e[i].r)-lsh;//离散化
add(1,l,r,e[i].a);
ans=max(ans,t[1].maxn);
}
printf("%d\n",ans);
}
return 0;
}