首先将修改操作差分为 \(l_1\) 时刻给 \([l_2,r_2]\) 中的值 \(+v\)，\(r_1+1\) 时刻给 \([l_2,r_2]\) 中的值 \(-v\)。这样第 \(i\) 行的状态相当于执行 \(1\sim i\) 时刻的操作后的状态。
猫树分治，把一个询问挂在线段树上满足 \(l\le l_1\le mid\le r_1\le r\) 的区间 \([l,r]\) 上。这样我们发现查询其实是一个历史最大值状物。具体来说我们维护一个历史最大值线段树，然后分治到 \([l,r]\) 时候执行以下操作：
- 将 \([l,mid]\) 中的修改加入线段树。
- 将每个节点的历史最大值设为 \(-\infty\)。
- 将这个节点上的询问挂在 \(r_1\) 上，然后从左往右依次加入 \([mid+1,r]\) 中的修改，加完 \(i\) 后的修改后处理挂在 \(i\) 上的询问，查一遍 \([l_2,r_2]\) 的历史最大值，更新这组询问的答案。
- 将 \([mid+1,r]\) 的修改撤销，然后递归右区间。
- 将每个节点的历史最大值设为 \(-\infty\)。
- 将这个节点上的询问挂在 \(l_1\) 上，然后从右往左依次撤销 \([l,mid]\) 中的修改，按照同样的方式处理询问即可。
然后就做完了，只需要魔改历史最大值线段树即可实现将历史最大值设为 \(-\infty\) 的操作。一个注意点是加入的时候应该先加负数后加正数，否则历史最大值会出错，撤销的时候则恰好相反。
总复杂度 \(O(n\log^2n)\)。
const int MAXN=5e5;
const int MAXQ=5e5;
int n,m,qu;ll res[MAXQ+5];
struct event{
int x,y,val;
event(){x=y=val=0;}
event(int _x,int _y,int _val){x=_x;y=_y;val=_val;}
};
struct qry{
int l,r,x,y,id;
qry(){l=r=x=y=id=0;}
qry(int _l,int _r,int _x,int _y,int _id){l=_l;r=_r;x=_x;y=_y;id=_id;}
};
vector<event>pv[MAXN+5];
vector<qry>qv[MAXN*4+5];
bool cmpv(event x,event y){return x.val<y.val;}
bool cmpl(qry x,qry y){return x.l>y.l;}
bool cmpr(qry x,qry y){return x.r<y.r;}
void ins(int k,int l,int r,int ql,int qr,qry v){
int mid=l+r>>1;
if((l==r)||(ql<=mid&&mid+1<=qr))return qv[k].pb(v),void();
if(qr<=mid)ins(k<<1,l,mid,ql,qr,v);
else if(ql>mid)ins(k<<1|1,mid+1,r,ql,qr,v);
else ins(k<<1,l,mid,ql,mid,v),ins(k<<1|1,mid+1,r,mid+1,qr,v);
}
namespace segtree{
struct node{int l,r;ll mx,hmx,lz1,lz2,clr;}s[MAXN*4+5];
void build(int k,int l,int r){
s[k].l=l;s[k].r=r;if(l==r)return;int mid=l+r>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void tag(int k,ll v1,ll v2){
s[k].hmx=max(s[k].mx+v2,s[k].hmx);s[k].mx+=v1;
s[k].lz2=max(s[k].lz1+v2,s[k].lz2);s[k].lz1+=v1;
}
void reset(int k){
tag(k<<1,s[k].lz1,s[k].lz2);tag(k<<1|1,s[k].lz1,s[k].lz2);
s[k].lz1=s[k].lz2=0;s[k].hmx=s[k].mx;s[k].clr=1;
}
void pushdown(int k){
if(s[k].clr)reset(k<<1),reset(k<<1|1),s[k].clr=0;
tag(k<<1,s[k].lz1,s[k].lz2);tag(k<<1|1,s[k].lz1,s[k].lz2);
s[k].lz1=s[k].lz2=0;
}
void modify(int k,int l,int r,int v){
if(l<=s[k].l&&s[k].r<=r)return tag(k,v,v),void();
pushdown(k);int mid=s[k].l+s[k].r>>1;
if(r<=mid)modify(k<<1,l,r,v);
else if(l>mid)modify(k<<1|1,l,r,v);
else modify(k<<1,l,mid,v),modify(k<<1|1,mid+1,r,v);
s[k].mx=max(s[k<<1].mx,s[k<<1|1].mx);
s[k].hmx=max(s[k<<1].hmx,s[k<<1|1].hmx);
}
ll query(int k,int l,int r){
if(l<=s[k].l&&s[k].r<=r)return s[k].hmx;
pushdown(k);int mid=s[k].l+s[k].r>>1;
if(r<=mid)return query(k<<1,l,r);
else if(l>mid)return query(k<<1|1,l,r);
else return max(query(k<<1,l,mid),query(k<<1|1,mid+1,r));
}
}using namespace segtree;
void solve(int k,int l,int r){
int mid=l+r>>1;
for(int i=l;i<=mid;i++)for(auto t:pv[i])modify(1,t.x,t.y,t.val);
sort(qv[k].begin(),qv[k].end(),cmpr);
for(int i=mid+1,j=0;i<=r;i++){
for(auto t:pv[i])modify(1,t.x,t.y,t.val);
if(i==mid+1)reset(1);
while(j<qv[k].size()&&qv[k][j].r==i){
chkmax(res[qv[k][j].id],query(1,qv[k][j].x,qv[k][j].y));
++j;
}
}
for(int i=r;i>=mid+1;i--){
for(int j=(int)(pv[i].size())-1;~j;j--)
modify(1,pv[i][j].x,pv[i][j].y,-pv[i][j].val);
}
if(l!=r)solve(k<<1|1,mid+1,r);
sort(qv[k].begin(),qv[k].end(),cmpl);
for(int i=mid,j=0;i>=l;i--){
if(i==mid)reset(1);
while(j<qv[k].size()&&qv[k][j].l==i){
chkmax(res[qv[k][j].id],query(1,qv[k][j].x,qv[k][j].y));
++j;
}
for(int j=(int)(pv[i].size())-1;~j;j--)modify(1,pv[i][j].x,pv[i][j].y,-pv[i][j].val);
}
if(l!=r)solve(k<<1,l,mid);
}
int main(){
scanf("%d%d%d",&n,&m,&qu);
for(int i=1,l,x,r,y,val;i<=m;i++){
scanf("%d%d%d%d%d",&l,&x,&r,&y,&val);
pv[l].pb(event(x,y,val));pv[r+1].pb(event(x,y,-val));
}
for(int i=1,l,x,r,y;i<=qu;i++){
scanf("%d%d%d%d",&l,&x,&r,&y);
ins(1,1,n,l,r,qry(l,r,x,y,i));
}
for(int i=1;i<=n;i++)sort(pv[i].begin(),pv[i].end(),cmpv);
build(1,1,n);solve(1,1,n);
for(int i=1;i<=qu;i++)printf("%lld\n",res[i]);
return 0;
}
/*
5 5 1
1 1 4 5 4
4 1 4 1 10
1 3 3 3 3
1 1 5 5 8
2 4 4 5 8
4 1 5 4
*/