abc327F - Apples（线段树）

https://atcoder.jp/contests/abc327/tasks/abc327_f

我们将时间看作x轴，位置看作y轴，那么我们随着时间增加，维护新加的点对区间的贡献，同时减去过时的点，线段树区间加法维护最大值即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#define A puts("YES")
#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll mo=1e9+7;
const ll inf=1ll<<60;
const int N=4e5+5;
int n,d,w,x,y,z,ans;
int t,a[N*4],mx[N*4];
vector<int> v[N];
void update(int o,int l,int r){
	if (x<=l && r<=y) {
		a[o]+=z;
		mx[o]+=z;
		return;
	}
	int m=(l+r)>>1;
	if (x<=m) update(lc,l,m);
	if (m<y) update(rc,m+1,r);
	
	mx[o]=max(mx[lc],mx[rc])+a[o];
}
void query(int o,int l,int r,int add){
	if (x<=l && r<=y) {
		ans=max(ans, mx[o]+add);
		return;
	}
	int m=(l+r)>>1;
	if (x<=m) query(lc,l,m,add+a[o]);
	if (m<y) query(rc,m+1,r,add+a[o]);
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);

	scanf("%d %d %d",&n,&d,&w);
	fo(i,1,n) {
		scanf("%d %d",&t,&x);
		v[t].emplace_back(x);
	}
	
	fo(i,1,2e5) {
		int st=i-d;
		if (st>0) {
			for (auto j:v[st]) {
				x=max(1,j-w+1); y=j; z=-1;
				update(1,1,2e5);
			}
		}
		
		for (auto j:v[i]) {
			x=max(1,j-w+1); y=j; z=1;
			update(1,1,2e5);
		}
		
		x=1; y=2e5;
		query(1,1,2e5,0);
	}
	
	printf("%d",ans);
	


	return 0;
}