WA#4#9,扫描线+线段树求调qwq
查看原帖
WA#4#9,扫描线+线段树求调qwq
585805
MCRS_lizi楼主2022/7/29 18:52
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,w,h,ans,tot,len;
struct sb
{
	int val,lazy;
}tree[100001];
struct node
{
	int x,xh,ce;
}b[100001];
struct point
{
	int x,y,l;
}a[100001];
struct line
{
	int y,num,l,r;
}c[100001];
bool cmp1(node u,node v)
{
	return u.x<v.x;
}
bool cmp2(node u,node v)
{
	return u.xh<v.xh||u.xh==v.xh&&u.x<v.x;
}
bool cmp3(line u,line v)
{
	return u.y<v.y;
}
void clear()
{
	for(int i=1;i<=1e5;i++)
	{
		tree[i].val=tree[i].lazy=0;
	}
}
void pushdown(int l,int r,int mid,int p)
{
	tree[p*2].val+=tree[p].lazy;
	tree[p*2+1].val+=tree[p].lazy;
	tree[p*2].lazy+=tree[p].lazy;
	tree[p*2+1].lazy+=tree[p].lazy;
	tree[p].lazy=0;
}
void update(int l,int r,int k,int ll,int rr,int p)
{
	if(ll>r||rr<l)
	{
		return;
	}
	else if(ll>=l&&rr<=r)
	{
		tree[p].lazy+=k;
		tree[p].val+=k;
		return;
	}
	else
	{
		int mid=(ll+rr)>>1;
		pushdown(ll,rr,mid,p);
		update(l,r,k,ll,mid,p*2);
		update(l,r,k,mid+1,rr,p*2+1);
		tree[p].val=max(tree[p*2].val,tree[p*2+1].val);
	}
}
void add(line u)
{
	update(u.l,u.r,u.num,1,len,1);
}
signed main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>w>>h;
		w--,h--;
		len=0;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].x>>a[i].y>>a[i].l;
		//	a[i].x+=w,a[i].y+=h;
			b[++len].x=a[i].x;
			b[len].xh=i;
			b[++len].x=a[i].x+w;
			b[len].xh=i;
		}
		sort(b+1,b+len+1,cmp1);
		ans=-1;
		b[1].ce=1;
		for(int i=2;i<=len;i++)
		{
			if(b[i].x==b[i-1].x)
			{
				b[i].ce=b[i-1].ce;
			}
			else
			{
				b[i].ce=b[i-1].ce+1;
			}
		}
		tot=0;
		sort(b+1,b+len+1,cmp2);
		for(int i=1;i<=len;i+=2)
		{
			int l=b[i].ce,r=b[i+1].ce;
			c[++tot].l=l;
			c[tot].r=r;
			c[tot].num=a[b[i].xh].l;
			c[tot].y=a[b[i].xh].y;
			c[++tot].l=l;
			c[tot].r=r;
			c[tot].num=-a[b[i].xh].l;
			c[tot].y=a[b[i].xh].y+h+1;
		}
		sort(c+1,c+tot+1,cmp3);
		for(int i=1;i<=tot;i++)
		{
			add(c[i]);
			ans=max(ans,tree[1].val);
		}
		cout<<ans<<endl;
		clear();
	}
 	return 0;
}

本来上区间用y+h-1只错#9,现在改了#4#9一起错QAQ

2022/7/29 18:52
加载中...