【louguP1502】窗口的星星

用两条扫描线从左往右扫描，距离为W，右边的扫描线扫到就加上，左边的扫到就减去，

线段树上的一点\(x\)维护\((x,x+H)\)的星星总价值，修改时直接修改\((x-H,x)\)就行了

坐标大，离散化

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#define lc (p<<1)

#define rc (p<<1|1)

#define int long long

using namespace std;

const int MAXN=20010;

const int MAXM=400010;

inline int read(){

	int x=0; char c=getchar();

	while(c<'0') c=getchar();

	while(c>='0') x=x*10+c-'0',c=getchar();

	return x;

}

int T,n,W,H,mx[MAXN],Ans;

struct NODE{

	int x,nx,y,l,lx;

}a[MAXN];

inline bool cmp1(NODE p,NODE q){

	return p.x<q.x;

}

inline bool cmp2(NODE p,NODE q){

	return p.y<q.y;

}

int maxx[MAXM],tag[MAXM];

inline void push_up(int p){

	maxx[p]=max(maxx[lc],maxx[rc]);

}

inline void push_down(int p,int l,int r){

	if(tag[p]){

		int &d=tag[p];

		maxx[lc]+=d; maxx[rc]+=d;

		tag[lc]+=d; tag[rc]+=d;

		d=0;

	}

}

inline void update(int L,int R,int d,int p=1,int l=1,int r=n){

	if(L<=l&&r<=R){

		maxx[p]+=d;

		tag[p]+=d;

		return;

	}

	push_down(p,l,r);

	int mid=(l+r)>>1;

	if(L<=mid) update(L,R,d,lc,l,mid);

	if(R>mid) update(L,R,d,rc,mid+1,r);

	push_up(p);

}

signed main()

{

	T=read();

	while(T--){

		memset(maxx,0,sizeof(maxx));

		memset(tag,0,sizeof(tag));

		memset(mx,0,sizeof(mx));

		Ans=0;

		n=read(); H=read(); W=read();

		for(int i=1;i<=n;++i)

			a[i].x=read(),a[i].y=read(),a[i].l=read();

		sort(a+1,a+1+n,cmp1);

		int cnt=0;

		for(int i=1;i<=n;++i){

			a[i].nx=(a[i].x==a[i-1].x)?cnt:++cnt;

			mx[a[i].nx]=a[i].x;

		}

		int j=1;

		for(int i=1;i<=n;++i){

			while(a[i].x-mx[j]>=H) ++j;

			a[i].lx=j;

		}

		sort(a+1,a+1+n,cmp2);

		int l=1,r=1;

		while(r<=n){

			update(a[r].lx,a[r].nx,a[r].l);

			while(a[r].y-a[l].y>=W)

				update(a[l].lx,a[l].nx,-a[l].l),++l;

			Ans=max(Ans,maxx[1]);

			++r;

		}

		printf("%lld\n",Ans);

	}

	return 0;

}

/*

3

3 5 4

1 2 3

2 3 2

6 3 1

3 5 4

1 2 3

2 3 2

5 3 1

4 3 3

1 1 1

2 2 3

3 4 2

4 1 1

*/

巴特西

【louguP1502】窗口的星星

最新文章

热门文章