RT 谢谢!
我90pts的代码 是维护线段的 而我在其他扫描线的题都是这种打法且都能过
也就是
// 维护mx值 即扫描线能覆盖到的最大值
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
#define N (int)(1e5+5)
#define ls (cur<<1)
#define rs (ls|1)
#define int long long
using namespace std;
int ny[N];
int n,w,h;
struct node {
int h,l,r,fl;
}g[N];
struct tr {
int sum,tag;
}t[N];
int rd() {
int f=1,sum=0; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return sum*f;
}
void push_up(int cur) {
t[cur].sum=max(t[ls].sum,t[rs].sum);
}
void push_down(int cur) {
if(!t[cur].tag) return;
t[ls].sum+=t[cur].tag; t[rs].sum+=t[cur].tag;
t[ls].tag+=t[cur].tag; t[rs].tag+=t[cur].tag;
t[cur].tag=0;
}
void update(int cur,int l,int r,int cl,int cr,int x) {
if(ny[l]>=cr||ny[r]<=cl) return;
if(cl<=ny[l]&&ny[r]<=cr) {
t[cur].sum+=x;
t[cur].tag+=x;
return;
}
int mid=(l+r)>>1;
push_down(cur);
update(ls,l,mid,cl,cr,x);
update(rs,mid,r,cl,cr,x);
push_up(cur);
}
bool cmp(node x,node y) {
return x.h==y.h?x.fl>y.fl:x.h<y.h;
}
signed main() {
int tt=rd();
while(tt--) {
memset(g,0,sizeof(g));
memset(ny,0,sizeof(ny));
memset(t,0,sizeof(t));
n=rd(); w=rd(); h=rd();
int x,y,z;
for(int i=1;i<=n;i++) {
x=rd(); y=rd(); z=rd();
g[(i<<1)-1]=node{x,y,y+h-1,z};
g[i<<1]=node{x+w-1,y,y+h-1,-z};
ny[(i<<1)-1]=y; ny[i<<1]=y+h-1;
}
n<<=1;
sort(g+1,g+1+n,cmp);
sort(ny+1,ny+1+n);
int ans=0,tot=0;
for(int i=1;i<=n;i++) if(ny[i]!=ny[i+1]) ny[++tot]=ny[i];
for(int i=1;i<n;i++) {
update(1,1,tot,g[i].l,g[i].r,g[i].fl);
ans=max(ans,t[1].sum);
}
printf("%lld\n",ans);
}
}
但是在这道题 就似乎要维护2条线段之间 改成这样就过了 区别在update函数和调用update函数
// 维护mx值 即扫描线能覆盖到的最大值
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
#define N (int)(1e6+5)
#define ls (cur<<1)
#define rs (ls|1)
#define int long long
using namespace std;
int ny[N];
int n,w,h;
struct node {
int h,l,r,fl;
}g[N];
struct tr {
int sum,tag;
}t[N];
int rd() {
int f=1,sum=0; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return sum*f;
}
void push_up(int cur) {
t[cur].sum=max(t[ls].sum,t[rs].sum);
}
void push_down(int cur) {
if(!t[cur].tag) return;
t[ls].sum+=t[cur].tag; t[rs].sum+=t[cur].tag;
t[ls].tag+=t[cur].tag; t[rs].tag+=t[cur].tag;
t[cur].tag=0;
}
void update(int cur,int l,int r,int cl,int cr,int x) {
if(ny[l]>cr||ny[r]<cl) return;
if(cl<=ny[l]&&ny[r]<=cr) {
t[cur].sum+=x;
t[cur].tag+=x;
return;
}
int mid=(l+r)>>1;
push_down(cur);
update(ls,l,mid,cl,cr,x);
update(rs,mid+1,r,cl,cr,x);
push_up(cur);
}
bool cmp(node x,node y) {
return x.h==y.h?x.fl>y.fl:x.h<y.h;
}
signed main() {
int tt=rd();
while(tt--) {
memset(g,0,sizeof(g));
memset(ny,0,sizeof(ny));
memset(t,0,sizeof(t));
n=rd(); w=rd(); h=rd();
int x,y,z;
for(int i=1;i<=n;i++) {
x=rd(); y=rd(); z=rd();
g[(i<<1)-1]=node{x,y,y+h-1,z};
g[i<<1]=node{x+w-1,y,y+h-1,-z};
ny[(i<<1)-1]=y; ny[i<<1]=y+h-1;
}
n<<=1;
sort(g+1,g+1+n,cmp);
sort(ny+1,ny+1+n);
int ans=0,tot=0;
for(int i=1;i<=n;i++) if(ny[i]!=ny[i+1]) ny[++tot]=ny[i];
for(int i=1;i<=n;i++) {
update(1,1,tot-1,g[i].l,g[i].r,g[i].fl);
ans=max(ans,t[1].sum);
}
printf("%lld\n",ans);
}
}