二逼线段树60pts求助
查看原帖
二逼线段树60pts求助
285617
黑影洞人楼主2022/9/7 18:42
#include<cstdio>
#include<algorithm>
#define lc p<<1
#define rc p<<1|1
#define N 3005
using namespace std;
int m,n,q;
struct seg{
	struct node{int val,tag,clr;}s[N];
	void pushup(int p){
		s[p].val=max(max(s[lc].val,s[rc].val),s[p].val);
	}
	void pushdown(int p){
		if(s[p].clr){
			s[lc].val=s[rc].val=s[lc].tag=s[rc].tag=0;
			s[lc].clr=s[rc].clr=1;
			s[p].clr=0;
			return;
		}
		s[lc].val=max(s[lc].val,s[p].tag);
		s[rc].val=max(s[rc].val,s[p].tag);
		s[lc].tag=max(s[lc].tag,s[p].tag);
		s[rc].tag=max(s[rc].tag,s[p].tag);
	}
	void change(int p,int L,int R,int l,int r,int v){
		if(L>r||R<l)return;
		if(L>=l&&R<=r){
			s[p].val=max(s[p].val,v);
			s[p].tag=max(v,s[p].tag);
			return;
		}
		pushdown(p);
		change(lc,L,(L+R)/2,l,r,v);change(rc,(L+R)/2+1,R,l,r,v);
		pushup(p);
	}
	void clear(){s[1].clr=1,s[1].val=s[1].tag=0;}
	int query(int p,int L,int R,int l,int r){
		if(L>r||R<l)return 0;
		if(L>=l&&R<=r)return s[p].val;
		pushdown(p);
		return max(query(lc,L,(L+R)/2,l,r),query(rc,(L+R)/2+1,R,l,r));
	}
};
struct Segement_tree{
	seg val,tag;
}s[N];
void pushup(int p,int x,int y){
	s[p].val.change(1,1,n,x,y,s[lc].val.query(1,1,n,x,y));
	s[p].val.change(1,1,n,x,y,s[rc].val.query(1,1,n,x,y));
}
void pushdown(int p,int x,int y){
	int res=s[p].tag.query(1,1,n,x,y);
	s[lc].val.change(1,1,n,x,y,res);
	s[rc].val.change(1,1,n,x,y,res);
	s[lc].tag.change(1,1,n,x,y,res);
	s[rc].tag.change(1,1,n,x,y,res);
	s[p].tag.clear();
}
void change(int p,int L,int R,int l,int r,int x,int y,int v){
	if(L>r||R<l)return;
	if(L>=l&&R<=r){
		s[p].val.change(1,1,n,x,y,v);
		s[p].tag.change(1,1,n,x,y,v);
		return;
	}
	pushdown(p,x,y);
	change(lc,L,(L+R)/2,l,r,x,y,v);change(rc,(L+R)/2+1,R,l,r,x,y,v);
	pushup(p,x,y);
}
int query(int p,int L,int R,int l,int r,int x,int y){
	if(L>r||R<l)return 0;
	if(L>=l&&R<=r)return s[p].val.query(1,1,n,x,y);
	pushdown(p,x,y);	
	return max(query(lc,L,(L+R)/2,l,r,x,y),query(rc,(L+R)/2+1,R,l,r,x,y));
}
signed main(){
	scanf("%d%d%d",&m,&n,&q);
	while(q--){
		int a,b,c,d,e;
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&e); 
		d++,e++;
		int ans=query(1,1,m,d,d+a-1,e,e+b-1);
		change(1,1,m,d,d+a-1,e,e+b-1,ans+c);
	}
	printf("%d",query(1,1,m,1,m,1,n));
	return 0;
}


2022/9/7 18:42
加载中...