自动搬运

查看原文

来自洛谷，原作者为

	w4p3r I think all our memories, and everything in it. . .can be nothing but the fiction we tell ourselves.

搬运于2025-08-24 22:17:30，当前版本为作者最后更新于2020-07-22 12:15:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一丶前言

这道题可能是本蒟蒻做过的最巧的数据结构题，没有之一qaq。

二丶思路

我们可以先考虑这样一种做法。首先对于$(l_1,r_1,l_2,r_2,v)$的修改操作，可以视作我们在$l_1$行时对$l_2$到$r_2$这个区间$+v$，再在$r_1+1$行时对$l_2$到$r_2$这个区间$-v$。（这样我们把一个修改操作分解成了两个修改操作）

我们考虑从小到大枚举$L$，并处理所有$l_1=L$的询问操作。然后我们先把所有修改操作进行分解，并从小到大枚举$R$（枚举的时候要把修改操作加进去）。我们取出所有$L=l_1,R=r_1$的询问操作，并对$l_2$到$r_2$这个区间进行询问。

我们询问的是什么呢？可以发现，其实我们询问的其实是历史最大值，而修改操作就是一个区间加，所以我们只要维护一个可以支持区间历史最大值和区间加的线段树即可（CPU监控简化版）。

由于这个东西比较简单，就不细讲怎么维护了

注意一个小细节，若一个时间点有多次修改，要先加负数再加正数，不然历史最大值可能只加入一个时间点的部分操作，这样是不合法的。

这样时间复杂度是$O((n^2+q)logn)$的，(好像时间复杂度更高了)，但可喜可贺的是我们把询问从两个$log$变成了一个$log$。

考虑在这个算法的基础上继续进行优化。

可以发现对于一个询问，我们要将$1$到$l_1-1$所有操作插入（不维护历史最大值），并再将$l_1$到$r_1$的操作插入（在插入时要维护历史最大值），并区间询问历史最大值。

考虑线段树分治，假设当前线段树节点代表的区间为$l,r$，$mid=(l+r)/2$。

对于所有$l<=l_1<=r_1<=r$的询问，若$r_1<=mid$或者$l_1>mid$则交给儿子处理，否则就在当前点处理（不能把询问拆成$log$个，不然时间复杂度还是要起飞）。

我们假设$1$到$l-1$的操作已经加入到线段树中（注意区分维护历史最大值的线段树和线段树分治的线段树）。

考虑先处理右边的贡献，所以先把$l$到$mid$的操作插入（不求历史最大值），然后把所有当前点的询问按$r$从小到大排序，并依次插入操作（此时就要求历史最大值了）和进行询问，然后把$mid+1$到$r$的操作回退，并递归右子树（依然满足$1$到$l-1$的操作已被加入）。

然后考虑处理左边的贡献，按$l$从大到小排序，然后进行类似的操作并递归左子树即可。（这个处理的顺序不是固定的，你先遍历左子树再处理左边的贡献再遍历右子树再处理右边的贡献也是可以的）。

（前面那堆东西可能有点冗杂，但如果理解了前面的话再看看代码应该就没问题了）

这样时间复杂度就是$O(nlog^2n+qlogn)$了

三丶代码

因为lxl貌似并不希望有人抄代码所以去了头文件。

//W4P3R
#define N 500010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
ll n,m,q,ans[N];
struct TREE{ll maxn,hmax,tag1,tag2,res;};
struct ask{ll id,l,r,x,y;}a[N];
struct node{ll l,r,val;};vector<node>v[N];
vector<ask>que[N<<2];
struct Segement_Tree
{
	TREE t[N<<2];
	inline void addtag(ll x,ll v1,ll v2)
	{
		t[x].hmax=max(t[x].maxn+v2,t[x].hmax);t[x].maxn+=v1;
		t[x].tag2=max(t[x].tag1+v2,t[x].tag2);t[x].tag1+=v1;
	}//维护历史最大值
	inline void reset(ll x)
	{
		addtag(ls,t[x].tag1,t[x].tag2);addtag(rs,t[x].tag1,t[x].tag2);
		t[x].tag1=t[x].tag2=0;
		t[x].hmax=t[x].maxn;t[x].res=1;
	}//把历史最大值重置为当前最大值
	inline void pushdown(ll x)
	{
		if(t[x].res){reset(ls);reset(rs);t[x].res=0;}
		addtag(ls,t[x].tag1,t[x].tag2),addtag(rs,t[x].tag1,t[x].tag2);
		t[x].tag1=t[x].tag2=0;
	}
	inline void pushup(ll x)
	{
		t[x].maxn=max(t[ls].maxn,t[rs].maxn);
		t[x].hmax=max(t[ls].hmax,t[rs].hmax);
	}
	void update(ll l,ll r,ll x,ll left,ll right,ll val)
	{
		if(l==left&&right==r){addtag(x,val,val);return ;}
		pushdown(x);
		if(right<=mid)update(l,mid,ls,left,right,val);
		else if(left>mid)update(mid+1,r,rs,left,right,val);
		else update(l,mid,ls,left,mid,val),update(mid+1,r,rs,mid+1,right,val);
		pushup(x);
	}
	ll query(ll l,ll r,ll x,ll left,ll right)
	{
		if(l==left&&right==r)return t[x].hmax;
		pushdown(x);
		if(right<=mid)return query(l,mid,ls,left,right);
		else if(left>mid)return query(mid+1,r,rs,left,right);
		else return max(query(l,mid,ls,left,mid),query(mid+1,r,rs,mid+1,right));
	}
}T;//维护历史最大值的线段树
void add(ll x,ll l,ll r,ask p)
{
	if(p.l<=mid+1&&mid<=p.r){que[x].pb(p);return ;}//把询问加入当前点
	if(p.r<=mid)add(ls,l,mid,p);
	else add(rs,mid+1,r,p);
}
inline ll cmp(node a,node b){return a.val<b.val;}
inline ll cmp1(ask a,ask b){return a.r<b.r;}
inline ll cmp2(ask a,ask b){return a.l>b.l;}
inline void Up(ll x,ll opt)
{
	if(opt==1){for(auto p:v[x]){T.update(1,n,1,p.l,p.r,p.val);}}
	else {REP(i,v[x].size()-1,0)T.update(1,n,1,v[x][i].l,v[x][i].r,-v[x][i].val);}
}//1是加入操作，-1是回退操作
void Solve(ll x,ll l,ll r)
{
	FOR(i,l,mid)Up(i,1);//把l到mid的操作加入
	ll cnt=0,nowp=1;
	for(auto p:que[x])a[++cnt]=p;//将询问按r从小到大排序
	sort(a+1,a+cnt+1,cmp1);
	while(nowp<=cnt&&a[nowp].r==mid)nowp++;//r=mid的询问肯定跟右边的修改无关啦
	FOR(i,mid+1,r)
	{
		Up(i,1);//加入当前修改
		if(i==mid+1)T.reset(1);//1到mid的修改操作不应该求历史最大值
		while(a[nowp].r==i&&nowp<=cnt){ans[a[nowp].id]=max(ans[a[nowp].id],T.query(1,n,1,a[nowp].x,a[nowp].y));nowp++;}//正常的询问
	}
	REP(i,r,mid+1)Up(i,-1);//回退
	if(l!=r)Solve(rs,mid+1,r);//遍历右子树
	cnt=0,nowp=1;
	for(auto p:que[x])a[++cnt]=p;
	sort(a+1,a+cnt+1,cmp2);//将询问按l从大到小排序
	while(nowp<=cnt&&a[nowp].l==mid+1)nowp++;//同上
	REP(i,mid,l)
	{
		if(i==mid)T.reset(1);
		while(a[nowp].l==i&&nowp<=cnt){ans[a[nowp].id]=max(ans[a[nowp].id],T.query(1,n,1,a[nowp].x,a[nowp].y));nowp++;}
		Up(i,-1);
	}//同上
	if(l!=r)Solve(ls,l,mid);//遍历左子树
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(),m=read(),q=read();
	FOR(i,1,m)
	{
		ll l=read(),x=read(),r=read(),y=read(),val=read();
		v[l].pb((node){x,y,val});
		v[r+1].pb((node){x,y,-val});
	}
	FOR(i,1,q)
	{
		ll l=read(),x=read(),r=read(),y=read();
		add(1,1,n,(ask){(ll)i,l,r,x,y});
	}
	FOR(i,1,n)sort(v[i].begin(),v[i].end(),cmp);
	Solve(1,1,n);
	FOR(i,1,q)printf("%lld\n",ans[i]);
	return 0;
}

如果你觉得这篇题解对你有帮助，那你可以点个赞支持我一下qwq。如果你对题解有任何问题/认为我的题解有任何问题，可以私信/在评论区发出来，当然如果你对我的题解有任何意见/建议也欢迎指出。我会尽我全力把我题解写到最好的qwq