#9 WA 有没有dalao可以帮忙看看
查看原帖
#9 WA 有没有dalao可以帮忙看看
215590
Ckger楼主2021/7/1 21:10
#include<bits/stdc++.h>
#define maxn 100010
#define foir(i,l,r) for (register int i=l;i<=r;++i)
#define fopr(i,l,r) for (register int i=l;i>=r;--i)
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
using namespace std;

long long t,ans;

inline int read()
{
	int x=0;bool f=0;char c=getchar();
	while (!isdigit(c)) f|=c=='-',c=getchar();
	while (isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return f?-x:x;
}

int n,w,h,tot;

struct line
{
	int u;
	int d;
	int x;
	long long rt;
	int tag;
}b[maxn<<1];

int a[maxn<<1];

long long tr[maxn<<4],tg[maxn<<4];

inline bool cmp(const line& p,const line& q) { return (p.x!=q.x)?(p.x<q.x):(p.tag>q.tag); }

inline void init()
{
	ans=0;
	memset(tr,0,sizeof tr);
	memset(tg,0,sizeof tg);
	n=read(),w=read(),h=read();
	w-=2;h-=2;
	foir(i,1,n)
	{
		int x=read(),y=read(),l=read();
		b[i*2-1].u=y+h+1;
		b[i*2-1].d=y;
		b[i*2-1].x=x;
		b[i*2-1].rt=l;
		b[i*2-1].tag=1;
		b[i*2].u=y+h+1;
		b[i*2].d=y;
		b[i*2].x=x+w+1;
		b[i*2].rt=l;
		b[i*2].tag=-1;
		a[i*2-1]=y;
		a[i*2]=y+h+1;
	}
	sort(a+1,a+1+n*2);
	tot=unique(a+1,a+1+n*2)-(a+1);
	sort(b+1,b+1+n*2,cmp);
}

inline void pushup(int p)
{
	tr[p]=max(tr[ls(p)],tr[rs(p)]);
}

inline void pushdown(int p)
{
	tr[ls(p)]+=tg[p];
	tg[ls(p)]+=tg[p];
	tr[rs(p)]+=tg[p];
	tg[rs(p)]+=tg[p];
	tg[p]=0;
}

void update(int L,int R,int ql,int qr,int p,int t,int k)
{
	if (a[L]>=qr||a[R+1]<=ql) return ;
	else if (a[L]>=ql&&a[R+1]<=qr)
	{
		tg[p]+=t*k;
		tr[p]=tr[p]+t*k;
//		cout<<"tr="<<tr[p]<<endl;
//		pushup(p);
		return ;
	}
	pushdown(p);
	int mid=(L+R)>>1;
	update(L,mid,ql,qr,ls(p),t,k);
	update(mid+1,R,ql,qr,rs(p),t,k);
	pushup(p);
}

int main()
{
	t=read();
	while (t--)
	{
		init();
//		cout<<tot<<endl;
		foir(i,1,n*2)
		{
//			cout<<"x="<<b[i].x<<" l="<<b[i].d<<" r="<<b[i].u<<endl;
			update(1,tot,b[i].d,b[i].u,1,b[i].tag,b[i].rt);
			ans=max(ans,tr[1]);
		}
		cout<<ans<<endl;
	}
	return 0;
}
/*

1
3 5 4
1 2 3
2 3 2
6 3 1

1
3 5 4
1 2 3
2 3 2
5 3 1


*/
2021/7/1 21:10
加载中...