record

意识到区修单调性就很简单了吧。

愿意调的私信。

#include<cstdio>
#include<algorithm>
using namespace std;

#define int long long

int n,m,q;
struct tree_y
{
	struct node
	{
		int l,r; // 区间范围
		node *lson,*rson; // 左右儿子
		int maxs; // 历史区间最大值
		int set_tag; // 修改标记
		bool unset_tag; // 是否有标记
		node(){};
		node(int l,int r):l(l),r(r),lson(nullptr),rson(nullptr),maxs(0),set_tag(0),unset_tag(0){}
	} *root;
	#define init \
		int &l=Node->l,&r=Node->r; \
		node *&lson=Node->lson,*&rson=Node->rson; \
		int &maxs=Node->maxs; \
		int &set_tag=Node->set_tag; \
		bool &unset_tag=Node->unset_tag;
	void upd(node *Node) // 更新左右儿子
	{
		init;
		int mid=l+r>>1;
		if(lson==nullptr)
			lson=new node(l,mid);
		if(rson==nullptr)
			rson=new node(mid+1,r);
	}
	void set(node *Node,int v) // 修改
	{
		init;
		maxs=max(maxs,v); // 因为是历史最大值，所以要取max
		set_tag=max(set_tag,v); // 同理
		unset_tag=1;
	}
	void pushdown(node *Node) // 下传标记
	{
		init;
		if(l==r||!unset_tag)
			return;
		upd(Node);
		set(lson,set_tag);
		set(rson,set_tag);
		unset_tag=0;
	}
	void pushup(node *Node) // 合并子树信息
	{
		init;
		if(l==r)
			return;
		upd(Node);
		pushdown(Node);
		maxs=max(lson->maxs,rson->maxs);
	}
	void modify(node *Node,int x,int y,int v) // 区修
	{
		init;
		if(y<l||r<x)
			return;
		if(x<=l&&r<=y)
		{
			set(Node,v);
			return;
		}
		upd(Node);
		pushdown(Node);
		modify(lson,x,y,v);
		modify(rson,x,y,v);
		pushup(Node);
	}
	int query(node *Node,int x,int y) // 区查
	{
		init;
		if(y<l||r<x)
			return 0;
		if(x<=l&&r<=y)
			return maxs;
		upd(Node);
		pushdown(Node);
		return max(query(lson,x,y),query(rson,x,y));
	}
	tree_y(){}
	tree_y(int l,int r):root(new node(l,r)){}
	#undef init
};

struct tree_x
{
	struct node
	{
		int l,r; // 区间范围
		node *lson,*rson; // 左右儿子
		tree_y y_tree,tag_tree; // 区间历史最大值(线段树), 区修标记(线段树)
		node(){}
		node(int l,int r,int ll,int rr):l(l),r(r),lson(nullptr),rson(nullptr),y_tree(ll,rr),tag_tree(ll,rr){}
	} *root;
	#define init \
		int &l=Node->l,&r=Node->r; \
		node *&lson=Node->lson,*&rson=Node->rson; \
		tree_y &y_tree=Node->y_tree; \
		tree_y &tag_tree=Node->tag_tree;
	void upd(node *Node) // 更新左右儿子
	{
		init;
		int mid=l+r>>1;
		if(lson==nullptr)
			lson=new node(l,mid,y_tree.root->l,y_tree.root->r);
		if(rson==nullptr)
			rson=new node(mid+1,r,y_tree.root->l,y_tree.root->r);
	}
	void modify(node *Node,int x,int y,int xx,int yy,int v) // 区修
	{
		init;
		if(y<l||r<x)
			return;
		y_tree.modify(y_tree.root,xx,yy,v); // 一定包含要修改的区间
		if(x<=l&&r<=y)
		{
			tag_tree.modify(tag_tree.root,xx,yy,v); // 完全包含, 添加标记
			return;
		}
		upd(Node);
		modify(lson,x,y,xx,yy,v);
		modify(rson,x,y,xx,yy,v);
	}
	int query(node *Node,int x,int y,int xx,int yy) // 区查
	{
		init;
		if(y<l||r<x)
			return 0;
		if(x<=l&&r<=y)
			return y_tree.query(y_tree.root,xx,yy);
		upd(Node);
		return max(tag_tree.query(tag_tree.root,xx,yy),max(query(lson,x,y,xx,yy),query(rson,x,y,xx,yy)));
	}
	#undef init
	tree_x(){}
	tree_x(int l,int r,int ll,int rr):root(new node(l,r,ll,rr)){}
} *root;

signed main()
{
	scanf("%lld%lld%lld",&n,&m,&q);
	root=new tree_x(0,n,0,m);
	while(q--)
	{
		int x,y,xl,yl,v;
		scanf("%lld%lld%lld%lld%lld",&xl,&yl,&v,&x,&y);
		root->modify(root->root,x,x+xl-1,y,y+yl-1,root->query(root->root,x,x+xl-1,y,y+yl-1)+v);
	}
	printf("%lld",root->query(root->root,0,n,0,m));
	return 0;
}