求助 WA on #14
查看原帖
求助 WA on #14
1406678
hky_lightning楼主2025/1/15 08:22
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int ans=0,l,r,m,w,n;
int dp[N];
struct node{
	int x,w;
};
vector<node>c[N];
namespace LineTree{
	#define lt (cur<<1)
	#define rt ((cur<<1)|1)
	#define mid ((L+R)>>1)
	const int M=N<<2;
	int t[M],lz[M];
	void up(int cur){
		t[cur]=max(t[lt],t[rt]);
	}
	void sq(int cur,int w){
		lz[cur]+=w;
		t[cur]+=w;
	}
	void down(int cur){
		sq(lt,lz[cur]);
		sq(rt,lz[cur]);
		lz[cur]=0;
	}
	void build(int cur,int L,int R){
		if(L==R){
			t[cur]=0;
			return ;
		}
		build(lt,L,mid);
		build(rt,mid+1,R);
		up(cur);
	}
	int maxn(int cur,int l,int r,int L,int R){
		if((l<=L&&R<=r))
			return t[cur];
		else if(!(R<l||L>r)){
			int num=-1e9;
			down(cur);
			num=max(num,maxn(lt,l,r,L,mid));
			num=max(num,maxn(rt,l,r,mid+1,R));
			return num;
		}
		return -1e9;
	}
	void add(int cur,int l,int r,int L,int R,int w){
		if((l<=L&&R<=r)) 
			sq(cur,w);
		else if(!(R<l||L>r)){
			down(cur);	
			add(lt,l,r,L,mid,w);
			add(rt,l,r,mid+1,R,w);
			up(cur);
		}
	}
}
using namespace LineTree;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>l>>r>>w;
		c[l].push_back((node){l-1,w});
		c[r+1].push_back((node){l-1,-w});
	}	
	build(1,1,n+1);
	for(int i=1;i<=n;i++){
		for(int j=0;j<c[i].size();j++)
			add(1,1,c[i][j].x+1,1,n+1,c[i][j].w);
		dp[i]=maxn(1,1,i,1,n+1);
		add(1,i+1,i+1,1,n+1,dp[i]);
		ans=max(dp[i],ans);
	}
	cout<<ans;
	return 0;
}

2025/1/15 08:22
加载中...