萌新刚学动态开点线段树求吊
查看原帖
萌新刚学动态开点线段树求吊
754467
f_hxr_楼主2023/10/16 11:46

rt

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf=1e9+7;
LL N,W,ans=0;
struct SegmentTree{
	struct Node{
		LL dat=0;
		Node* ls=nullptr,* rs=nullptr;
	}root;
	#define ls(p) p.ls
	#define rs(p) p.rs
	void pushup(Node& p){p.dat=max(p.ls->dat,p.rs->dat);}
	void pushdown(Node& p){
		if(!p.ls)p.ls=new Node();
		if(!p.rs)p.rs=new Node();
	}
	void ModifyPoint(Node& p,LL L,LL R,LL inx,LL xx){
		if(L==R){p.dat+=xx;return;}
		pushdown(p);
		LL mid=(L+R-1)/2;
		if(inx<=mid)ModifyPoint(*(p.ls),L,mid,inx,xx);
		if(mid<inx)ModifyPoint(*(p.rs),mid+1,R,inx,xx);
		pushup(p);
	}
	void ModifyPoint(LL inx,LL xx){ModifyPoint(root,-inf,inf,inx,xx);}
	LL QueryRange(Node& p,LL L,LL R,LL ql,LL qr){
		if(ql<=L&&R<=qr)return p.dat;
		pushdown(p);
		LL mid=(L+R-1)/2,ret=0;
		if(ql<=mid)ret=max(ret,QueryRange(*(p.ls),L,mid,ql,qr));
		if(mid<qr)ret=max(ret,QueryRange(*(p.rs),mid+1,R,ql,qr));
		return ret;
	}
	LL QueryRange(LL ql,LL qr){return QueryRange(root,-inf,inf,ql,qr);}
}S;
int main(){
	scanf("%lld%lld",&N,&W);
	for(int i=1;i<=N;i++){
		int a,b;scanf("%lld%lld",&a,&b);
		S.ModifyPoint(a,b);
	}
	if(W==0){cout<<0;return 0;}
	for(int i=W;i<=100005;i++)	
		ans=max(ans,S.QueryRange(i-W+1,i));
	cout<<ans;
	return 0;
}
2023/10/16 11:46
加载中...